二叉搜索树

二叉搜索树的性质

当前二叉搜索树上的结点的值大于其左孩子结点的值，小于等于其右孩子结点的值

---

二叉搜索树的输出

struct node {
    node *left;
    int key;
    node *right 
};


void firstorder_tree_walk(node *x) { //先序遍历
    if(x != NULL) {
        printf("%d ",key);
        inorder_tree_walk(x->left);
        inorder_tree_walk(x->right);
    }
}


void inorder_tree_walk(node *x) { //中序遍历
    if(x != NULL) {
        inorder_tree_walk(x->left);
        printf("%d ",key);
        inorder_tree_walk(x->right);
    }
}

void afterorder_tree_walk(node *x) { //后序遍历
    if(x != null) {
        inorder_tree_walk(x->left);
        inorder_tree_walk(x->right);
        printf("%d ",key);
    }
}

---

查找

typedef struct node {
    node *left;
    int key;
    node *right 
    node *parent;
} *NODE;


NODE tree_search(NODE x, int k) { //搜索k值
    while(x->key != k && x != NULL) {
        if(x->key < k ) {
            x = x->right;
        }
        else {
            x = x->left;
        }
    }
    return x;
}

NODE tree_search_min(NODE x) { //搜索最小值
    while(x != NULL) {
            x = x->left;
    }
    return x;
}

NODE tree_search_max(NODE x) { //搜索最大值
    while(x != NULL) {
            x = x->right;
    }
    return x;
}


NODE tree_successor(NODE x) { //查找后继，没有任何关键字的比较。如果使用关键字，则使用中序即可
    if(x->right != NULL) {
        x = x->right;
        tree_search_min(x);
    }
    y = x->parent;
    while(x == y->right || y != NULL) {
        x = y;
        y = y->parent;
    }
    return y;
}

---

插入

typedef struct node {
    node *left;
    int key;
    node *right 
    node *parent;
} *NODE;


NODE tree_insert(NODE T, NODE Z) { //T表示数的根结点,插入
    NODE y, x;
    x = T;
    whike(x != NULL) {
        y = x;
        if(x->key <= z->key) {
            x = x->right;
        }
        else {
            x = x->left;
        }
    }
    z->parent = y;
    if(y == NULL) {
        T = z;
    }
    else if(x->key <= z->key) {
        x->right = z;
    }
    else {
        x->left = z;
    }
}

---

删除

typedef struct node {
    node *left;
    int key;
    node *right 
    node *parent;
} *NODE;

void transplant(NODE T, NODE u, NODE v) { //把v节点与u结点整合，并且把u结点删去
    if(u->parent == NULL) {
        T = v;
    }
    if(u->parent->left == u) {
        u->parent->left = v;
    }
    else if(u->parent->right == u) {
        u->parent->right = v;   
    }
    if(v != NULL) {
        v->parent = u->parent;
    }
}

void tree_delete(NODE T, NODE x) { //删除
    if(x->left == NULL) { //要删除的结点没有左孩子
        transplant(T, x, x->left);
    }
    else if(x->right == NULL) { //要删除的结点没有右孩子
        transplant(T, x, x->right);
    }
    else { //要删除的结点有右孩子，也有右孩子，则需要将后继点移植到删除的结点处
        y = tree_search_min(x->right); //找后继点，一定是右子树中的,后继点肯定没有左孩子
        if(x != y->parent) { //后继点不是要删除结点的孩子
            transplant(T, y, y->right);
            x->right->parent = y;
            y->right = x->right;
        }
        transplant(T, x, y);
        y->left = x->left;
        x->left->parent = y;
    }
}