资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

BST二叉搜索树

1、二叉搜索树

创新互联建站-专业网站定制、快速模板网站建设、高性价比墨江网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式墨江网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖墨江地区。费用合理售后完善,10余年实体公司更值得信赖。

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

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

  (3)、满足:左孩子数据 < 根结点数据 < 右孩子数据;根(父)结点比左孩子的大,比右孩子的小;

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

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

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

如图:

BST二叉搜索树

3、搜索二叉树上的操作

  全部用C++实现的。

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

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

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

BST二叉搜索树

  (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>找右子树最小的数字,覆盖要删除的数字,在往右子树找这个数字删除-->递归!

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

BST二叉搜索树

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

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

BST二叉搜索树

代码如下:

    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_

#include
using namespace std;

#define MIN_NUMBER    -8937589
#define MAX_NUMBER    99999999


template
class BSTree;

template
class 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;
};

template
class 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)、测试结果:

BST二叉搜索树


网页名称:BST二叉搜索树
转载来于:http://www.cdkjz.cn/article/peiccc.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220