1. IT分享知识网首页

二叉搜索树详解（C++实现）

老牧童 • • 未分类 • 阅读 82

二叉搜索树详解（C++实现）二叉搜索树的定义二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；任意节点的左、右子树也分别为二叉查找树。没有键值相等的节点。二叉搜索数中序遍历为有序数组一、查找二叉搜索树中的某个元素在二叉搜…

大家好，欢迎来到IT知识分享网。

二叉搜索树的定义

二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

  2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

  3. 任意节点的左、右子树也分别为二叉查找树。

  4. 没有键值相等的节点。

二叉搜索数中序遍历为有序数组

这里写图片描述

一、查找二叉搜索树中的某个元素

在二叉搜索树b中查找x的过程为：
  • 若b是空树，则搜索失败，否则：
  • 若x等于b的根节点的数据域之值，则查找成功；否则：
  • 若x小于b的根节点的数据域之值，则搜索左子树；否则：
  • 查找右子树。

这里写图片描述

二、从有序数组构造一个二叉搜索树

这里写图片描述

三、往二叉搜索树中插入元素

向一个二叉搜索树b中插入一个节点s的算法，过程为：
  • 若b是空树，则将s所指结点作为根节点插入，否则：
  • 若s->data等于b的根节点的数据域之值，则返回，否则：
  • 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
  • 把s所指节点插入到右子树中。（新插入节点总是叶子节点）
    这里写图片描述

四、二叉搜索树的删除

二叉搜索树的结点删除比插入较为复杂，总体来说，结点的删除可归结为三种情况：

– 如果结点z没有孩子节点，那么只需简单地将其删除，并修改父节点，用NULL来替换z；
– 如果结点z只有一个孩子，那么将这个孩子节点提升到z的位置，并修改z的父节点，用z的孩子替换z；
– 如果结点z有2个孩子，那么查找z的后继y，此外后继一定在z的右子树中，然后让y替换z。

这里写图片描述

代码实现

二叉搜索树结构：

//the struct of BST
//K: the type of key
//V: the type of value
//K and V need overload operators < and > and ==
template<class K, class V> struct BSTreeNode { 
   
    BSTreeNode* lchild_; //left child;
    BSTreeNode* rchild_; //right child;
    K key_;              //key
    V value_;            //value

    BSTreeNode(const K& key, const V& value) //init
        :lchild_(NULL)
        ,rchild_(NULL)
        ,key_(key)
        ,value_(value)
    {}

};

二叉搜索数查找：

//BST Find
Node* Find(const K& key)
{
    return Find_(root_, key);
}

Node* Find_(Node* root, const K& key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (root->key_ > key) //find in leftchild
    {
        return Find_(root->lchild_, key);
    }
    else if (root->key_ < key)//find in rightchild
    {
        return Find_(root->rchild_, key);
    }
    else
    {
        return root;
    }
}

二叉搜索数插入：

//BST Insert
//Find the node and Insert
bool Insert(const K& key, const V& value)
{
    return Insert_(root_, key, value);
}

bool Insert_(Node*& root, const K& key, const V& value)
{
    if (root == NULL)
    {
        root = new Node(key, value);
        return true;
    }

    if (root->key_ > key)
    {
        return Insert_(root->lchild_, key, value);
    }
    else if(root->key_ < key)
    {
        return Insert_(root->rchild_, key, value);
    }
    else
    {
        return false;
    }
}

二叉搜索树删除：

//BST remove
bool Remove(const K& key)
{
    return Remove_(root_, key);
}

bool Remove_(Node*& root, const K& key)
{
    //There is no such node
    if (root == NULL)
    {
        return false;
    }
    //only one node
    if (root->lchild_ == NULL&&root->rchild_ == NULL)
    {
        if (root->key_ == key)
        {
            delete root;
            root = NULL;
            return true;
        }
        else
        {
            return false;
        }

    }


    if (root->key_ > key)
    {
        Remove_(root->lchild_, key);
    }
    else if (root->key_ < key)
    {
        Remove_(root->rchild_, key);
    }
    else
    {
        Node* del = NULL;

        if (root->lchild_ == NULL)      //just has rightchild
        {
            del = root;
            root = root->rchild_;
            delete del;
            del = NULL;
            return true;
        }
        else if (root->rchild_ == NULL) //just has leftchild
        {
            del = root;
            root = root->lchild_;
            delete del;
            del = NULL;
            return true;
        }
        else
        {
            Node* RightFirst = root->rchild_;
            //find the first In order node
            while (RightFirst->lchild_)
            {
                RightFirst = RightFirst->lchild_;
            }

            //swap RightFirst node with cur node
            swap(root->key_, RightFirst->key_);
            swap(root->value_, RightFirst->value_);


            Remove_(root->rchild_, key);
            return true;
        }
    }
}

完整代码：

#include<bits/stdc++.h>
using namespace std;


//the struct of BST
//K: the type of key
//V: the type of value
//K and V need overload operators < and > and ==
template<class K, class V>
struct BSTreeNode
{
    BSTreeNode* lchild_; //left child;
    BSTreeNode* rchild_; //right child;
    K key_;              //key
    V value_;            //value

    BSTreeNode(const K& key, const V& value) //init
        :lchild_(NULL)
        ,rchild_(NULL)
        ,key_(key)
        ,value_(value)
    {}

};



template<class K,class V>
class BSTree
{
    typedef BSTreeNode<K, V> Node;

public:
    BSTree()
        :root_(NULL)
    {}

    //BST Find
    Node* Find(const K& key)
    {
        return Find_(root_, key);
    }

    Node* Find_(Node* root, const K& key)
    {
        if (root == NULL)
        {
            return NULL;
        }

        if (root->key_ > key) //find in leftchild
        {
            return Find_(root->lchild_, key);
        }
        else if (root->key_ < key)//find in rightchild
        {
            return Find_(root->rchild_, key);
        }
        else
        {
            return root;
        }
    }



    //BST Insert
    //Find the node and Insert
    bool Insert(const K& key, const V& value)
    {
        return Insert_(root_, key, value);
    }

    bool Insert_(Node*& root, const K& key, const V& value)
    {
        if (root == NULL)
        {
            root = new Node(key, value);
            return true;
        }

        if (root->key_ > key)
        {
            return Insert_(root->lchild_, key, value);
        }
        else if(root->key_ < key)
        {
            return Insert_(root->rchild_, key, value);
        }
        else
        {
            return false;
        }
    }



    //BST remove
    bool Remove(const K& key)
    {
        return Remove_(root_, key);
    }

    bool Remove_(Node*& root, const K& key)
    {
        //There is no such node
        if (root == NULL)
        {
            return false;
        }
        //only one node
        if (root->lchild_ == NULL&&root->rchild_ == NULL)
        {
            if (root->key_ == key)
            {
                delete root;
                root = NULL;
                return true;
            }
            else
            {
                return false;
            }

        }


        if (root->key_ > key)
        {
            Remove_(root->lchild_, key);
        }
        else if (root->key_ < key)
        {
            Remove_(root->rchild_, key);
        }
        else
        {
            Node* del = NULL;

            if (root->lchild_ == NULL)      //just has rightchild
            {
                del = root;
                root = root->rchild_;
                delete del;
                del = NULL;
                return true;
            }
            else if (root->rchild_ == NULL) //just has leftchild
            {
                del = root;
                root = root->lchild_;
                delete del;
                del = NULL;
                return true;
            }
            else
            {
                Node* RightFirst = root->rchild_;
                //find the first In order node
                while (RightFirst->lchild_)
                {
                    RightFirst = RightFirst->lchild_;
                }

                //swap RightFirst node with cur node
                swap(root->key_, RightFirst->key_);
                swap(root->value_, RightFirst->value_);


                Remove_(root->rchild_, key);
                return true;
            }
        }
    }


    //BST print In Order
    void Output()
    {
        Output_(root_);
        cout << endl;
    }

    void Output_(Node* root)
    {
        if (root == NULL)
        {
            return;
        }

        Output_(root->lchild_);
        cout << root->key_ << " ";
        Output_(root->rchild_);
    }


    Node * self()
    {
        return root_;
    }

private:
    Node* root_;
};


void Test()
{
    BSTree<int, int> s;

    //测试插入
    s.Insert(5, 1);
    s.Insert(4, 1);
    s.Insert(3, 1);
    s.Insert(6, 1);
    s.Insert(1, 1);
    s.Insert(2, 1);
    s.Insert(0, 1);
    s.Insert(9, 1);
    s.Insert(8, 1);
    s.Insert(7, 1);

    //二叉搜索树按中序输出是有序的
    s.Output();

    //测试查找
    cout << s.Find(6)->key_ << endl;

    //测试删除
    s.Remove(4);
    s.Remove(6);
    s.Remove(3);
    s.Remove(1);
    s.Remove(2);

    //再次打印删除后的结果
    s.Output();

}

int main()
{
    Test();
    return 0;
}

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/10607.html

赞 (0)
老牧童老牧童
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信