BST示例代碼如下：

#include<iostream>
using namespace std;
class Node {
public:
    int data;
    Node *lchild, *rchild, *father;
    Node(int _data, Node *_father = NULL) {
        data = _data;
        lchild = NULL;
        rchild = NULL;
        father = _father;
    }
    ~Node() {
        if (lchild != NULL) {
            delete lchild;
        }
        if (rchild != NULL) {
            delete rchild;
        }
    }
    void insert(int value) {
        if (value == data) {
            return;
        } else if (value > data) {
            if (rchild == NULL) {
                rchild = new Node(value, this);
            } else {
                rchild->insert(value);
            }
        } else {
            if (lchild == NULL) {
                lchild = new Node(value, this);
            } else {
                lchild->insert(value);
            }
        }
    }
    Node* search(int value) {
        if (data == value) {
            return this;
        } else if (value > data) {
            if (rchild == NULL) {
                return NULL;
            } else {
                return rchild->search(value);
            }
        } else {
            if (lchild == NULL) {
                return NULL;
            } else {
                return lchild->search(value);
            }
        }
    }
    Node* predecessor() {
        Node *temp = lchild;
        while (temp != NULL && temp->rchild != NULL) {
            temp = temp->rchild;
        }
        return temp;
    }
    Node* successor() {
        Node *temp = rchild;
        while (temp != NULL && temp->lchild != NULL) {
            temp = temp->lchild;
        }
        return temp;
    }

};
class BinaryTree {
private:
    Node *root;
public:
    BinaryTree() {
        root = NULL;
    }
    ~BinaryTree() {
        if (root != NULL) {
            delete root;
        }
    }
    void insert(int value) {
        if (root == NULL) {
            root = new Node(value);
        } else {
            root->insert(value);
        }
    }
    bool find(int value) {
        if (root->search(value) == NULL) {
            return false;
        } else {
           return true;
        }
    }
};
int main() {
    BinaryTree binarytree;
    int arr[10] = { 8, 9, 10, 3, 2, 1, 6, 4, 7, 5 };
    for (int i = 0; i < 10; i++) {
        binarytree.insert(arr[i]);
    }
    int value;
    cin >> value;
    if (binarytree.find(value)) {
        cout << "search success!" << endl;
    } else {
        cout << "search failed!" << endl;
    }
    return 0;
}

BST的元素刪除

BST節(jié)點(diǎn)的前驅(qū)與后繼搜索

某個(gè)BST節(jié)點(diǎn)的前驅(qū)，即為值比它小的最大的一個(gè)節(jié)點(diǎn)——進(jìn)入該節(jié)點(diǎn)的左子樹(shù)，然后不斷搜索左子樹(shù)的右孩子，找到最后的節(jié)點(diǎn)即可

Node* predecessor(){
    Node* temp=lchild;
    while(temp!=NULL&&temp->lchild!=NULL){
        temp=temp->lchild;
    }
    return temp;
}

后繼也是一樣，完全相反即可，此處略

刪除度數(shù)為0或者1的節(jié)點(diǎn)

對(duì)于一個(gè)非空的節(jié)點(diǎn)，首先檢查它是否有左孩子或者右孩子——因?yàn)樵摴?jié)點(diǎn)度數(shù)為0或者1，所以最多只能有一個(gè)孩子
對(duì)于節(jié)點(diǎn)delete_node的孩子temp，首先孩子的父親設(shè)置為delete_node的父親，然后斷開(kāi)其與delete_node的聯(lián)系
接下來(lái)判斷delete_node是其父節(jié)點(diǎn)的左孩子還是右孩子，確認(rèn)之后把temp換上
最后直接刪除delete_node
代碼如下：

void remove_node(Node* delete_node){ //delete_node的度為0或者1
        Node* temp=NULL;
        if(delete_node->lchild!=NULL){
            temp=delete_node->lchild;
            temp->father=delete_node->father;
            delete_node->lchild=NULL;
        }
        if(delete_node->rchild!=NULL){
            temp=delete_node->rchild;
            temp->father=delete_node->father;
            delete_node->rchild=NULL;
        }
        if(delete_node->father->lchild==delete_node){
            delete_node->father->lchild=temp;
        }
        else{
            delete_node->father->rchild=temp;
        }
        delete delete_node;
    }

刪除度數(shù)為2的節(jié)點(diǎn)

首先找到待刪除的節(jié)點(diǎn)
如果節(jié)點(diǎn)的左孩子存在，就把delete_node設(shè)置為節(jié)點(diǎn)的前驅(qū)
右孩子存在則設(shè)定為后繼
都不存在則設(shè)定為節(jié)點(diǎn)自身（此時(shí)待刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)）
把delete_node的data值賦給原本待刪除的節(jié)點(diǎn)——相當(dāng)于將待刪除的節(jié)點(diǎn)與delete_node調(diào)換
最后直接刪除delete_node

bool delete_tree(int value){
    Node *delete_node,*current_node;
    current_node=search(value);
    if(current_node==NULL){
          return false;
    }
    if(current_node->lchild!=NULL){
        delete_node=current_node->predecessor();
    }
    else if(current_node->rchild!=NULL){
        delete_node=current_node->successor();
    }
    else{
        delete_node=current_node;
    }
    current_node->data=delete_node->data;
    remove_node(delete_node);
    return true;
}