1 files changed, 138 insertions, 0 deletions
diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.c b/Computer_Science/data_structures/chapter_4/binary_search_tree.c
new file mode 100644
index 0000000..fb61e7b
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.c
@@ -0,0 +1,138 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "binary_search_tree.h"
+#include "print_ascii_tree.h"
+
+struct TreeNode
+{
+    elem_t elem;
+    SearchTree left;
+    SearchTree right;
+};
+
+SearchTree make_empty(SearchTree t)
+{
+    if(t != NULL) {
+        make_empty(t->left);
+        make_empty(t->right);
+        free(t);
+    }
+
+    return NULL;
+}
+
+/**
+ *  find x or return NULL.
+ */
+Position find(elem_t x, SearchTree t)
+{
+    if(t != NULL) {
+        if(t->elem == x) return t;
+        else if(t->elem > x) return find(x, t->right);
+        else return find(x, t->left);
+    }
+
+    return NULL;
+}
+
+Position find_min(SearchTree t)
+{
+    if(t == NULL)
+        return NULL;
+    else if(t->left == NULL)
+        return t;
+    else
+        return find_min(t->left);
+}
+
+Position find_max(SearchTree t)
+{
+    if(t == NULL)
+        return NULL;
+    else if(t->right == NULL)
+        return t;
+    else
+        return find_max(t->right);
+}
+
+SearchTree insert(elem_t x, SearchTree t)
+{
+    if(t == NULL) {
+        t = malloc(sizeof(struct TreeNode));
+        t->elem = x;
+        t->left = NULL;
+        t->right = NULL;
+    } else if(x > t->elem)
+        t->right = insert(x, t->right);
+    else if(x < t->elem)
+        t->left = insert(x, t->left);
+    /* The t->elem = x need do nothing, already inserted */
+
+    return t;
+}
+
+SearchTree delete(elem_t x, SearchTree t)
+{
+    Position p, tmp;
+
+    p = find(x, t);
+
+    if(p == NULL) {
+        /* elem x not found */
+        printf("x not found!(do nothing)\n");
+    } else if(p->left == NULL && p->right == NULL) {
+        free(p);
+    } else if(p->left == NULL) {
+        tmp = p;
+        p = p->right;
+        free(tmp);
+    } else if(p->right == NULL) {
+        tmp = p;
+        p = p->left;
+        free(tmp);
+    } else {
+        /* replace and delete */
+        tmp = find_min(p->right);
+        p->elem = tmp->elem;
+        t->right = delete(p->elem, t->right);
+    }
+
+    return t;
+}
+
+elem_t retrieve(Position p)
+{
+
+}
+
+void print_tree_pre_order(SearchTree t)
+{
+    if(t == NULL)
+        return;
+    print_tree_pre_order(t->left);
+    printf("%d ", t->elem);
+    print_tree_pre_order(t->right);
+}
+
+void test()
+{
+    SearchTree t = NULL;
+    t = make_empty(t);
+    t = insert(1, t);
+    insert(4, t);
+    insert(3, t);
+    insert(2, t);
+    insert(10, t);
+
+    print_tree_pre_order(t);
+    printf("\n");
+    print_ascii_tree(t);
+}
+
+int main()
+{
+    test();
+    return 0;
+}