二叉查找树

添加评论[ 分类：所有文章 ]

什么样的树是二叉查找树呢(Binary Search Tree)?

来自<<算法导论>>中的定义:

简单的说，每个节点的左子树都比该节点的值要小，且右子树节点的数值全部比这个节点都要大。这样的树就是二叉查找树.每个节点的关键字都不一样。

这种数据结构支持的操作有:插入一个节点，删除一个节点，查找一个节点，求出这个数的最大值，求出这个数的最小值。按照中序遍历整个数组，求出这个节点的后继和前驱。

一个典型的二叉查找树！

给出自己实现的一个二叉搜索树，其中实现了二叉搜索树的插入，二叉搜素树的删除，这两个部分比较重要.二叉查找树比较重要的性质:若按照中序遍历来输出这个二叉树，我们发现，已经对这个二叉树进行了排序。

若按照中序遍历这个二叉树，一个节点的后继的左子树必定为空，一个节点的前驱的右子树也必然为空！

插入算法:输入:一个二叉树的根节点指针，和要插入的关键字！

输出：已经插入二叉树后的根节点(不需要显示返回！

根据二叉查找树的特点，我们知道，每个节点的左子树都比该节点都小，右子树都比其大。因此可以很容易的递归实现其插入算法！

删除算法:分为三种情况: 1.删除的节点没有左子树。这可以直接删除该节点，用其中子树代替其原来的位置

2.删除的节点没有右子树，这个可以直接删除这个节点，用其中的左子树代替其原来的位置。

3.被删除的节点两个子节点都有。可以从图中看出来。一种是按照中序遍历找到这个要被删除的后继，或者是前驱，然后将这个后继或前驱代替这个节点并且删除这个后继或者是前驱的节点(根据按照中序遍历得到的后继必然是没有左子节点的，而前驱是没有右子节点的。

第一种情况:

第三种情况

依据wikipedia:给出其实现的一种：

#include<iostream>
using namespace std;
struct BSTree
{
        int data;
        struct BSTree *leftchildren;
        struct BSTree *rightchildren;

};
void insert_BST(BSTree *&root,int key)
{
        //没有根节点，我们创建一个根节点
        if(root==NULL)
        {
                BSTree *tmp = new BSTree;//创建一个新的节点
                tmp–>leftchildren =NULL;
                tmp–>rightchildren =NULL;
                tmp–>data = key;
                root = tmp;// 根节点改变了，所以要传入引用！
        }
        else
        {
                if(root–>data>key)
                {

                        if(root–>leftchildren!=NULL)
                                insert_BST(root–>leftchildren,key);
                        else
                        {
                                BSTree *tmp1 =new BSTree;
                                tmp1–>data = key;
                                tmp1–>leftchildren=NULL;
                                tmp1–>rightchildren = NULL;

                                root–>leftchildren=tmp1;
                        }
                }
                else
                {
                        if(root–>rightchildren!=NULL)
                                insert_BST(root–>rightchildren,key);
                        else
                        {
                                BSTree *tmp2=new BSTree;
                                root–>rightchildren = tmp2;
                                tmp2–>data =key;
                                tmp2–>leftchildren =NULL;
                                tmp2–>rightchildren =NULL;

                                root–>rightchildren =tmp2;
                        }
                }

        }
}
//根据二叉树的特点，我们可以递归的找到要找到的关键值！
bool search_BST(BSTree *root,int key)
{
        BSTree *tmp = root;
        if(tmp==NULL)
                return false;
        else if(tmp–>data == key)
                return true;
        else
        {
                if(tmp–>data < key)
                {
                        search_BST(tmp–>rightchildren,key);
                }
                else
                {
                        search_BST(tmp–>leftchildren,key);
                }
        }
        return true;

}

//按照中序遍历打印这颗二叉树！
void inorder_BST(BSTree *root)
{
        if(root!=NULL)
        {
            inorder_BST(root–>leftchildren);
            cout<<root–>data<<” “;

            inorder_BST(root–>rightchildren);
        }
        cout<<“n”;

}

void deletion_BST(BSTree *&root,int key)
{
        if(root==NULL)
                cout<<“error!”<<endl;
        else if(root–>data < key)
        {
            deletion_BST(root–>rightchildren,key);

        }
        else if(root–>data > key)
        {
                deletion_BST(root–>leftchildren,key);
        }
        else
        {
                if(root–>leftchildren==NULL)
                {
                        BSTree *tmp = root–>rightchildren;
                        delete root;
                        root = tmp;
                }
                else if(root–>rightchildren == NULL)
                {
                        BSTree *tmp1 = root–>leftchildren;
                        delete root;
                        root = tmp1;
                }
                else
                {
                        BSTree *parent = NULL;
                        BSTree *tmp3 = root–>rightchildren;
                        while(tmp3–>leftchildren!=NULL)
                        {
                            parent = tmp3;
                            tmp3 = tmp3–>rightchildren;
                        }
                        root–>data = tmp3–>data;
                        if(parent!=NULL)
                                deletion_BST(parent–>rightchildren,parent–>rightchildren–>data);
                        else
                                deletion_BST(root–>rightchildren,root–>rightchildren–>data);

                }
        }
}
int main()
{
        int n;
        cout<<“this pragram is produced by BruceChen(http://www.brucechen1.tk)”<<endl;
        BSTree *root =NULL;
        cout<<“please input the key you want to build:(-1 ends)n”;
        while(1)
        {
                cin>>n;
                if(n==–1)
                        break;
                insert_BST(root,n);

        }
        inorder_BST(root);
        cout<<“please input the key you want to delete:n”;
        int key;
        cin>>key;
        deletion_BST(root,key);
        cout<<“after deletion:n”;
        cout<<“按照中序遍历输出:n”;
        inorder_BST(root);

        return 0;

}