C++二叉搜索树

2019-11-20 0 条评论 191 次阅读 0 人点赞
  • 概念

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

    • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
    • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
    • 它的左右子树也分别为二叉搜索树
  • 二叉搜索树的查找

    过程如图:

    搜索过程

主体框架代码:

#include <vector>
#include <stack>
#include <iostream>
using namespace std;

namespace km {
    template<class T>
    class TreeNode{
      T m_data;
      TreeNode<T> * m_left;
      TreeNode<T> * m_right;
    public:
        TreeNode(const T &val = T()):
            m_data(val),
            m_left(nullptr),
            m_right(nullptr) {

        }

        template <class U>
        friend class BinarySortTree;

    };
template <class T>
    class BinarySortTree {
        TreeNode<T> * m_root;

        void destory(TreeNode<T> * root){
            if(root){
                destory(root->m_left);
                destory(root->m_right);
                delete root;
            }
        }
    public:
        BinarySortTree():
            m_root(nullptr){
        }

        ~BinarySortTree(){
            destory(m_root);
        }
    };
  • 二叉搜索树的插入

    插入的具体过程如下:
    a. 树为空,则直接插入
    b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

//插入
        bool insert(const T &val){
            //无根直接创建根
            if(m_root == nullptr){
                m_root = new TreeNode<T>(val);
                return true;
            }

            TreeNode<T> * cur = m_root;
            TreeNode<T> * pre = m_root;

            while (cur){
                //val比data小进左子树, 反之进右子树,相等则false无法插入
                if(val < cur->m_data){
                    pre = cur;
                    cur = cur->m_left;
                } else if (val > cur->m_data){
                    pre = cur;
                    cur = cur->m_right;
                } else {
                    return false;
                }
            }
            //根没有子树

            cur = new TreeNode<T>(val);
            if(val < pre->m_data){
                pre->m_left = cur;
            } else {
                pre->m_right = cur;
            }
            return true;
        }
  • 二叉搜索数的删除

    看是不是有左右子树:
    1.左右子树都有
    a、左子树没有右孩子
    直接让左孩子继承自己的右孩子和父亲

    b、左子树有右孩子
    一路向右,找到最后的一个右孩子,然后将这个孩子的左子树挂在它父亲的右子树上,然后让它继承要删除节点的人际关系(左右子树和父亲)
    当要删除的节点是根节点时,不用继承父亲关系,但要修改根节点指向。

    2.只有左子树
    直接让左子树继承自己的父亲关系,如果要删的是根,那么直接换根即可。

3.其他
直接让右子树(或者空)继承自己的父亲关系,其他同上

        bool erase(const T &val){
            if(m_root == nullptr){
                return false;
            }
            //先找到要删除的节点
            TreeNode<T> * cur = m_root;
            TreeNode<T> * pre = m_root;

            while (cur){
                if(val < cur->m_data){
                    pre = cur;
                    cur = cur->m_left;
                } else if (val > cur->m_data){
                    pre = cur;
                    cur = cur->m_right;
                } else {
                    break;
                }
            }

            if (cur == nullptr){
                return false;
            }

            //找到以后有三种情况
            if (cur->m_left && cur->m_right){//左右子树都有的时候有两种做法:
#if 1
            TreeNode<T> * cur2 = cur->m_left;
            TreeNode<T> * pre2 = cur;

            if(cur2->m_right){ //左子树有右孩子
                //则一路向右找到最后一个右子树
                for(; cur2->m_right; pre2 = cur2, cur2 = cur2->m_right);
                //最后的一个右孩子,将这个孩子的左子树挂在它父亲的右子树上
                pre2->m_right = cur2->m_left;
                //继承关系
                cur2->m_left = cur->m_left;
            }

            cur2->m_right = cur->m_right;

            if(cur == pre){//是否换根
                m_root = cur2;
            } else {
                if(cur->m_data < pre->m_data){
                    pre->m_left = cur2;
                } else {
                    pre->m_right = cur2;
                }
            }
            delete cur;
#else
            //直接将最后右子树节点赋值给要删除结点, 删除最后一个右子树节点即可
            TreeNode<T> * cur2 = cur->m_left;
            TreeNode<T> * pre2 = cur;

            if(cur2->m_right){
                for(; cur2->m_right; pre2 = cur2, cur2 = cur2->m_right);
                pre2->m_right = cur2->m_left;
            }
            cur->m_data = cur2->m_data;

            delete cur2;
#endif
            } else if (cur->m_left){
                if(cur == pre){
                    m_root = cur->m_left;
                } else {
                    if (cur->m_data < pre->m_data){
                        pre->m_left = cur->m_left;
                    } else {
                        pre->m_right = cur->m_left;
                    }
                }
                delete cur;
            }
        }

        std::vector<T> InOrder() {
            std::stack<TreeNode<T> *> s;
            std::vector<T> res;
            TreeNode<T> * cur = m_root;

            while (cur || !s.empty()){
                for (; cur; cur = cur->m_left){
                    s.push(cur);
                }
                if (!s.empty()){
                    cur = s.top();
                    res.push_back(cur->m_data);
                    s.pop();

                    cur = cur->m_right;
                }
            }

            return res;
        }
  • 二叉搜索树性能分析

对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的
深度的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树, 如完全二叉树或右单支
最优情况下,二叉搜索树为完全二叉树,其平均比较次数为:logN
最差情况下,二叉搜索树退化为单支树,其平均比较次数为:N / 2

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)