【C++】二叉搜索树（上）-阿里云开发者社区

【C++】二叉搜索树（上）

2023-05-25 62

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【C++】二叉搜索树

二叉搜索树的查找规则

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

最多查找高度次，走到到空，还没找到，这个值不存在

二叉搜索树(二叉排序树)性质

非空左子树的所有值小于根节点的值

非空右子树的所有值大于根节点的值

左右子树都是二叉搜索树

第一个不满足，因为值为5的节点在值为10的节点的右边，正常来说10的右边都应该比10大

二叉搜索树的中序遍历

遍历，一定可以得到一个递增的序列中序为：1 3 4 6 7 8 10 13 14

二叉搜索树的实现 (非递归)

插入

分为两种情况

若插入的值在二叉树中不存在，则通过比较进行插入

若插入11，因为11比8大，所以跟10比较，而11比10大，所以走10的右子树14，14与11比较，因14>11，所以走14的左子树13，11与13比较，因13>11，故作为13的左子树，遇见NULL指针停止

若插入的值，在二叉树中存在

因为插入值13与二叉树中的值13相等，则直接返回false

实际上创建节点后，需要与二叉搜索树进行连接，去当前创建节点的上一个节点parent，

通过判断cur节点是parent节点左子树还是右子树进行连接

bool Insert(const K& key)
    {
        if (_root = nullptr)//若root根节点为nullptr
        {
            _root = new Node(key);
            return true;
        }
        Node* cur = _root;
        Node* parent = NULL;//用于接收cur之前的节点
        while (cur != NULL)
        {
            if (cur->_key > key)//若插入的值比cur值小
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_key < key)//若插入的值比cur值大
            {
                parent = cur;
                cur = cur->_right;
            }
            else//若相等，则直接返回false
            {
                return false;
            }
        }
        //遇见空指针，连接新节点
        //由于不知道parent的左还是右连接key，所以需要判断
        cur = new Node(key);
        if (parent->_key > key)
        {
            parent->_left = cur;
        }
        else
        {
            parent->_right = cur;
        }
        return true;
    }

中序遍历

inorder需要传根，但是由于_root是类的私有成员变量，所以没办法从.c文件传过来

若将inorder函数设为缺省值，不可以通过编译

缺省值必须是常量或者全局变量，而root不是全局变量/常量，所以不能用缺省值

访问成员变量需要用this指针，而此时_root并没有this指针去指向

所以采用嵌套一层函数的方式，这样调用inorder函数时，不用传参数过来也可以解决问题

查找

bool Find(const K& key)
    {
        Node* cur = _root;
        while (cur != NULL)
        {
            if (cur->_key > key)
            {
                cur = cur->_left;
            }
            else if (cur->_key < key)
            {
                cur = cur->_right;
            }
            else
            {
                return true;
            }
        }
        return false;
    }