initialize

4 files changed, 492 insertions, 0 deletions

diff --git a/c/dataStructure/tree/1.c b/c/dataStructure/tree/1.c
new file mode 100755
index 0000000..3b2364a
--- /dev/null
+++ b/c/dataStructure/tree/1.c
@@ -0,0 +1,268 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<stdbool.h>
+#define MAXSIZE 10
+typedef int elemtype;
+typedef struct node {
+  elemtype e;
+  struct node * left;
+  struct node * right;
+} Node;
+
+typedef Node * LLP;
+
+typedef struct tree {
+  Node * root;
+  int size;
+} Tree;
+
+typedef struct pair {
+  Node * parent;
+  Node * child;
+} Pair;
+
+typedef int ElemType;
+
+typedef struct data {
+    ElemType * elem;
+    int length;
+} Elem;
+
+typedef struct stack {
+    LLP data;
+    struct stack * next;
+} S;
+typedef S * Stack;
+
+void InitS(Stack * s)
+{
+    *s = NULL;
+}
+
+void Push(LLP e, Stack * s)
+{
+    Stack new = (Stack ) calloc (1,sizeof(S));
+    if (!new)
+    {
+        fprintf(stderr,"failed to allocate memory for stack!\n");
+        exit(1);
+    }
+    new->data = e;
+    new->next = *s;
+    *s = new;
+}
+
+void Pop(LLP * e, Stack * s)
+{
+    Stack p = *s;
+    *e = (*s)->data;
+    *s = (*s)->next;
+    free(p);
+}
+
+void DestroyS(Stack * s)
+{
+    Stack p;
+
+    if (*s)
+    {
+        p = *s;
+        *s = (*s)->next;
+        free(p);
+    }
+}
+
+bool EmptyS(Stack * s)
+{
+    if (!*s)
+        return true;
+    return false;
+}
+
+void InitList(Elem * L)
+{
+    L->elem = (ElemType *) malloc (sizeof(ElemType) * MAXSIZE);
+
+    if (!(L->elem))
+    {
+        fprintf(stderr,"Initialization Failed\nPlease run as debug mode\n");
+        exit(EXIT_FAILURE);
+    }
+
+    L->length = 0;
+}
+
+void AddElem(Elem * L, Node * nd)	//recursive
+{
+    Stack p;
+    InitS(&p);
+
+    Node * n = nd;
+
+    while (n || !EmptyS(&p))
+    {
+        if (n)
+        {
+             Push(n,&p);
+             n = n->left;
+        }
+        else
+        {
+            Pop(&n,&p);
+            L->elem[L->length++] = n->e;
+            n = n->right;
+        }
+    }
+    DestroyS(&p);
+}
+
+void DestroyList(Elem * L)
+{
+    if (L->elem)
+        free(L->elem);
+    else
+        printf("Sequence list is not exist!\n");
+}
+
+int binarySearch(int e, Elem * L)
+{
+    int l = 0, r = L->length;
+    int n;
+
+    while (l < r)
+    {
+        n = (l+r)/2-1;
+        if (L->elem[n] == e)
+            return n;
+        else if (L->elem[n] < e)
+                l = n+1;
+        else
+                r = n;
+    }
+    return -1;
+}
+
+void InitTree(Tree * tr)
+{
+  tr->root = NULL;
+  tr->size = 0;
+}
+
+static bool ToLeft(const elemtype e, const elemtype tree_e)
+{
+  return e < tree_e;
+}
+
+static bool ToRight(const elemtype e, const elemtype tree_e)
+{
+  return e > tree_e;
+}
+
+static Pair SeekItem(const elemtype e, Tree * ptr)
+{
+  Pair look = {NULL,ptr->root};
+  
+  while (look.child)
+  {
+    if (ToLeft(e,look.child->e))
+    {
+      look.parent = look.child;
+      look.child = look.child->left;
+    }
+    else if (ToRight(e,look.child->e))
+    {
+      look.parent = look.child;
+      look.child = look.child->right;
+    }
+    else
+      break;
+  }
+  
+  return look;
+}
+
+static bool AddNode(Node * new, Node * nd)
+{
+  if (ToLeft(new->e,nd->e))
+  {
+    if (nd->left == NULL)
+      nd->left = new;
+    else
+      AddNode(new,nd->left);
+  }
+  else if (ToRight(new->e,nd->e))
+  {
+    if (nd->right == NULL)
+      nd->right = new;
+    else
+      AddNode(new,nd->right);
+  }
+  else return false;
+  return true;
+}
+
+void MidPrint(const Node * nd)	//recursive
+{
+  if (nd->left)
+    MidPrint(nd->left);
+  printf("  %d", nd->e);
+  if (nd->right)
+    MidPrint(nd->right);
+}
+
+bool AddItem(const elemtype e, Tree * ptr)
+{
+  Node * new;
+  
+  if (SeekItem(e, ptr).child)
+    return false;
+  
+  new = (Node *) calloc (1,sizeof(Node));
+  if (!new)
+    return false;
+  
+  new->e = e;
+  
+  if (!ptr->root)
+    ptr->root = new;
+  else
+    AddNode(new, ptr->root);
+  return true;
+}
+
+bool ReleaseTree(Node * nd)
+{
+  Node * tmp = nd;
+  if (tmp->right)
+    ReleaseTree(tmp->right);
+  if (tmp->left)
+    ReleaseTree(tmp->left);
+  free(tmp);
+  return true;
+}
+
+int main(void)
+{
+  int num;
+  Tree btree;
+  Elem list;
+  int position;
+  InitTree(&btree);
+  InitList(&list);
+  
+  for (int i = 0; i < 10; i++)
+  {
+    scanf("%d", &num);
+    AddItem(num,&btree);
+  }
+  
+  MidPrint(btree.root);	//recursive
+  AddElem(&list, btree.root);
+  putchar('\n');
+  printf("%d\n",binarySearch(21,&list));
+  
+  ReleaseTree(btree.root);
+  DestroyList(&list);
+  
+  return 0;
+}
diff --git a/c/dataStructure/tree/btree.c b/c/dataStructure/tree/btree.c
new file mode 100755
index 0000000..c40db30
--- /dev/null
+++ b/c/dataStructure/tree/btree.c
@@ -0,0 +1,166 @@
+#include "btree.h"
+
+void InitTree(Tree * ptree)
+{
+    ptree->root = NULL;
+    ptree->size = 0;
+}
+
+bool EmptyTree(const Tree * ptree)
+{
+    return !ptree->root?true:false;
+}
+
+int CountItem(const Tree * ptree)
+{
+    return ptree->size;
+}
+
+typedef struct pair {
+    Node * parent;
+    Node * child;
+} Pair;
+
+
+static bool ToLeft(ElemType e1, ElemType e2)
+{
+    return e1 < e2;
+}
+static bool ToRight(ElemType e1, ElemType e2)
+{
+    return e1 > e2;
+}
+static bool AddNode(Node * new, Node * root)
+{
+    if (ToLeft(new->e, root->e))
+    {
+        if (root->left == NULL)
+            root->left = new;
+        else
+            AddNode(new,root->left);
+    }
+    else if (ToRight(new->e,root->e))
+    {
+        if (root->right == NULL)
+            root->right = new;
+        else
+            AddNode(new,root->right);
+    }
+    else
+        return false;
+    return true;
+}
+
+static Pair SeekNode(Node * root, const ElemType e)
+{
+    Pair look;
+    look.parent = NULL;
+    look.child = root;
+
+    if (look.child == NULL)
+        return look;
+
+    while (look.child != NULL)
+    {
+        if (ToLeft(e, look.child->e))
+        {
+            look.parent = look.child;
+            look.child = look.child->left;
+        }
+        else if (ToRight(e,look.child->e))
+        {
+            look.parent = look.child;
+            look.child = look.child->right;
+        }
+        else
+            break;
+    }
+
+    return look;
+}
+
+bool AddItem(const ElemType e, Tree * ptree)
+{
+    Node * new = (Node *) calloc (1,sizeof(Node));
+    if (!new)
+        return false;
+    if(SeekNode(ptree->root,e).child)
+        return false;
+
+    new->e = e;
+    
+    ptree->size++;
+
+    if (!ptree->root)
+        ptree->root = new;
+    else
+        AddNode(new,ptree->root);
+
+    return true;
+}
+
+static void DeleteNode(Node ** ptr)
+{
+    Node * tmp;
+
+    if ((*ptr)->left == NULL)
+    {
+        tmp = *ptr;
+        *ptr = (*ptr)->right;
+        free(tmp);
+    }
+    else if ((*ptr)->right == NULL)
+    {
+        tmp = *ptr;
+        *ptr = (*ptr)->left;
+        free(tmp);
+    }
+    else
+    {
+        for (tmp = (*ptr)->left;tmp->right != NULL; tmp = tmp->right)
+            continue;
+        tmp->right = (*ptr)->right;
+        tmp = *ptr;
+        *ptr = (*ptr)->left;
+        free(tmp);
+    }
+}
+
+bool DeleteItem(const ElemType e, Tree * ptree)
+{
+    Pair look;
+
+    look = SeekNode(ptree->root, e);
+    if (look.child == NULL)
+        return false;
+
+    if (look.parent == NULL)
+        DeleteNode(&ptree->root);
+    else if (look.parent->left == look.child)
+        DeleteNode(&look.parent->left);
+    else
+        DeleteNode(&look.parent->right);
+    ptree->size--;
+
+    return true;
+}
+
+bool ResTree(Node * root)
+{
+    Node * pnode = root;
+    if (pnode->right)
+        ResTree(pnode->right);
+    if (pnode->left)
+        ResTree(pnode->left);
+    free(pnode);
+    return true;
+}
+
+void PrintTree(const Node * root)
+{
+    printf("%c",root->e);
+    if (root->left)
+        PrintTree(root->left);
+    if (root->right)
+        PrintTree(root->right);
+}
diff --git a/c/dataStructure/tree/btree.h b/c/dataStructure/tree/btree.h
new file mode 100755
index 0000000..3acf818
--- /dev/null
+++ b/c/dataStructure/tree/btree.h
@@ -0,0 +1,28 @@
+#ifndef _BTREE_H
+#define _BTREE_H
+
+#include<stdio.h>
+#include<stdbool.h>
+#include<stdlib.h>
+
+typedef char ElemType;
+typedef struct node {
+    ElemType e;
+    struct node * left;
+    struct node * right;
+} Node;
+
+typedef struct tree {
+    Node * root;
+    int size;
+} Tree;
+
+void InitTree  (Tree * ptree);
+bool EmptyTree (const Tree * ptree);
+int  CountItem (const Tree * ptree);
+bool AddItem   (const ElemType e, Tree * ptree);
+bool DeleteItem(const ElemType e, Tree * ptree);
+bool ResTree   (Node * pnode);
+void PrintTree (const Node * root);
+
+#endif
diff --git a/c/dataStructure/tree/main.c b/c/dataStructure/tree/main.c
new file mode 100755
index 0000000..846c9e1
--- /dev/null
+++ b/c/dataStructure/tree/main.c
@@ -0,0 +1,30 @@
+#include "btree.h"
+
+int main(void)
+{
+    Tree btree;
+
+    ElemType e;
+    InitTree(&btree);
+
+    int size = 10;
+    char a[] = {'a','b','c','d','e','A','B','C','D','E'};
+
+    if (EmptyTree(&btree))
+        printf("It's empty\n");
+
+    for (int i = 0; i < size; i++)
+        AddItem(a[i],&btree);
+    
+    printf("Tree content: %d\n", CountItem(&btree));
+
+    PrintTree(btree.root);
+    putchar('\n');
+    DeleteItem('c',&btree);
+    PrintTree(btree.root);
+    putchar('\n');
+
+    ResTree(btree.root);
+
+    return 0;
+}