initialize

1 files changed, 268 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;
+}