initialize

1 files changed, 166 insertions, 0 deletions

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);
+}