BST二叉搜索树

1、二叉搜索树

(1)、逼近折半查找的查找算法；

(2)、一般不允许出现重复数字，不然没法存储；

(3)、满足：左孩子数据 < 根结点数据 < 右孩子数据；根(父)结点比左孩子的大，比右孩子的小；

(4)左子树和右子树也是二叉搜索树；

2、为什么叫二叉搜索树？

如果对一颗二叉搜索树进行中序遍历，可以按从小到大的顺序输出，此时又叫做二叉排序树。

如图：

3、搜索二叉树上的操作

全部用C++实现的。

(1)、之前学习二叉树，并没有说什么插入，删除操作，那是因为，没有规律而言，怎么进行操作呢？搜索二叉树的规律如此明显，那么插入，删除必是重中之中！

(2)、我们输入相同的数字，但是顺序不同的话，生成的搜索二叉树是不一样的！

例：int ar[] = {3, 7, 9, 1, 0, 6, 4, 2,}; 和int ar[] = {7, 3, 9, 1, 0, 6, 4, 2,}; 生成的搜索二叉树不一样。

(3)插入函数：

重分利用搜索二叉树的性质：

    void insert(BSTreeNode *&t, const Type &x){        if(t == NULL){            t = new BSTreeNode(x);            return;        }else if(x < t->data){            insert(t->leftChild, x);        }else if(x > t->data){            insert(t->rightChild, x);        }else{            return;        }        }

(4)、删除函数：

思想：要删除一个有左孩子或右孩子或是叶子结点，看成一种情况，做法：保存要删除的结点,因为传的是引用，可以直接修改上一个结点的左孩子或右孩子，使其跨过当前的直指下一个结点，在释放当前的结点空间。

第二种情况：就是要删除的既有左子树，又有右子树，此时可以有两种做法：i>找左子树最大的数字，覆盖要删除的数字，在往左子树找这个数字删除-->递归！ii>找右子树最小的数字，覆盖要删除的数字，在往右子树找这个数字删除-->递归！

第一种情况图形想法如下：

删除左边和删除右边，还有是叶子结点，想法一样。

第二种情况图形想法如下：

代码如下：

    bool remove(BSTreeNode *&t, const Type &key){        if(t == NULL){  //t传的是引用，每次可以进行直接更改!            return false;        }        if(key < t->data){            remove(t->leftChild, key);        }else if(key > t->data){            remove(t->rightChild, key);        }else{            if(t->leftChild != NULL && t->rightChild != NULL){  //第二种情况                BSTreeNode *p = t->rightChild;                while(p->leftChild != NULL){                    p = p->leftChild;                }                t->data = p->data;                remove(t->rightChild, p->data);  //在右树找p->data的数字进行删除;            }else{     //第一种情况                BSTreeNode *p = t;                if(t->leftChild == NULL){                    t = t->rightChild; //引用的好处体现出来了;                }else{                     t = t->leftChild;  //引用的好处体现出来了;                }                    delete p;            }        }                return true;    }/*  以下这个代码是先想到的，比较容易，上面这个是经过思考的，将三种情况看成一种情况来处理。    bool remove(BSTreeNode *&t, const Type &key){        if(t == NULL){            return false;        }        if(key < t->data){            remove(t->leftChild, key);        }else if(key > t->data){            remove(t->rightChild, key);        }else{  //以下三种情况可以看成一种；            if(t->leftChild == NULL && t->rightChild == NULL){                delete t;                t = NULL;            }else if(t->leftChild != NULL && t->rightChild == NULL){                BSTreeNode *p = t;                t = t->leftChild;                delete p;            }else if(t->leftChild == NULL && t->rightChild != NULL){                BSTreeNode *p = t;                t = t->rightChild;                delete p;            }else{                BSTreeNode *p = t->rightChild;                while(p->leftChild != NULL){                    p = p->leftChild;                }                t->data = p->data;                remove(t->rightChild, p->data);            }        }                return true;    }*/

4、搜索二叉树的完整代码、测试代码、测试结果

(1)、完整代码：

#ifndef _BSTREE_H_#define _BSTREE_H_#includeusing namespace std;#define MIN_NUMBER    -8937589#define MAX_NUMBER    99999999templateclass BSTree;templateclass BSTreeNode{    friend class BSTree;public:    BSTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}    BSTreeNode(Type d, BSTreeNode *left = NULL, BSTreeNode *right = NULL)         : data(d), leftChild(left), rightChild(right){}    ~BSTreeNode(){}private:    Type data;    BSTreeNode *leftChild;    BSTreeNode *rightChild;};templateclass BSTree{public:    BSTree() : root(NULL){}    BSTree& operator=(const BSTree &bst){        if(this != &bst){            root = copy(bst.root);        }        return *this;    }    ~BSTree(){}public:    void insert(const Type &x){        insert(root, x);    }    void inOrder()const{        inOrder(root);    }    Type Min()const{        return Min(root);    }    Type Max()const{        return Max(root);    }    BSTreeNode* find(const Type &key)const{        return find(root, key);    }    BSTreeNode *copy(const BSTreeNode *t){        if(t == NULL){            return NULL;        }        BSTreeNode *tmp = new BSTreeNode(t->data);        tmp->leftChild = copy(t->leftChild);        tmp->rightChild = copy(t->rightChild);        return tmp;    }    BSTreeNode* parent(const Type &key)const{        return parent(root, key);    }    bool remove(const Type &key){        return remove(root, key);    }protected:    bool remove(BSTreeNode *&t, const Type &key){        if(t == NULL){     //重点：传的是引用            return false;        }        if(key < t->data){            remove(t->leftChild, key);        }else if(key > t->data){            remove(t->rightChild, key);        }else{            if(t->leftChild != NULL && t->rightChild != NULL){                BSTreeNode *p = t->rightChild;                while(p->leftChild != NULL){                    p = p->leftChild;                }                t->data = p->data;                remove(t->rightChild, p->data);            }else{                BSTreeNode *p = t;                if(t->leftChild == NULL){                    t = t->rightChild;  //可以直接更改左右孩子                }else{                    t = t->leftChild;   //可以直接更改左右孩子                }                    delete p;            }        }                return true;    }/*      bool remove(BSTreeNode *&t, const Type &key){        if(t == NULL){            return false;        }        if(key < t->data){            remove(t->leftChild, key);        }else if(key > t->data){            remove(t->rightChild, key);        }else{  //以下三种情况可以看成一种；            if(t->leftChild == NULL && t->rightChild == NULL){                delete t;                t = NULL;            }else if(t->leftChild != NULL && t->rightChild == NULL){                BSTreeNode *p = t;                t = t->leftChild;                delete p;            }else if(t->leftChild == NULL && t->rightChild != NULL){                BSTreeNode *p = t;                t = t->rightChild;                delete p;            }else{                BSTreeNode *p = t->rightChild;                while(p->leftChild != NULL){                    p = p->leftChild;                }                t->data = p->data;                remove(t->rightChild, p->data);            }        }                return true;    }*/    BSTreeNode* parent(BSTreeNode *t, const Type &key)const{        if(t == NULL || t->data == key){            return NULL;        }        if(t->leftChild->data == key || t->rightChild->data == key){            return t;        }        if(key < t->data){            return parent(t->leftChild, key);        }else{            return parent(t->rightChild, key);        }    }    BSTreeNode* find(BSTreeNode *t, const Type &key)const{        if(t == NULL){            return NULL;        }        if(t->data == key){            return t;        }else if(key < t->data){            return find(t->leftChild, key);        }else{            return find(t->rightChild, key);        }    }    Type Max(BSTreeNode *t)const{        if(t != NULL){            while(t->rightChild){                t = t->rightChild;            }            return t->data;        }        return MAX_NUMBER;    }    Type Min(BSTreeNode *t)const{        if(t != NULL){            while(t->leftChild){                t = t->leftChild;            }            return t->data;        }        return MIN_NUMBER;    }    void inOrder(BSTreeNode *t)const{        if(t != NULL){            inOrder(t->leftChild);            cout<data<<" ";            inOrder(t->rightChild);        }    }    void insert(BSTreeNode *&t, const Type &x){        if(t == NULL){            t = new BSTreeNode(x);            return;        }else if(x < t->data){            insert(t->leftChild, x);        }else if(x > t->data){            insert(t->rightChild, x);        }else{            return;        }        }private:    BSTreeNode *root;};#endif

(2)测试代码：

#include"bstree.h"int main(void){    int ar[] = {3, 7, 9, 1, 0, 6, 4, 2,};    int n = sizeof(ar) / sizeof(int);    BSTree bst;    for(int i = 0; i < n; i++){        bst.insert(ar[i]);    }    bst.inOrder();    cout< *p = bst.find(6);    BSTreeNode *q = bst.parent(4);    printf("%p %p\n", p, q);    bst.remove(0);    bst.inOrder();    cout<
(3)、测试结果：