欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

高级数据结构］深入探索二叉树：二叉搜索树概念及其高效实现 - II.

最编程 2024-10-03 19:54:01
...

2.1 二叉搜索树的基本单位 

template<class K>
    struct  BSTreeNode
    {
        BSTreeNode(const K& key = K())
            :_left(nullptr)
                , _right(nullptr)
                , _key(key)
            {}

        BSTreeNode<K>* _left;
        BSTreeNode<K>* _right;
        K _key;

    };

2.2 实现二叉搜索树的基本框架 

template<class K>
    class  BSTree
    {
        public:
        //类型名字太长，不方便
        typedef BSTreeNode<K> Node;

        private:
        Node* _root = nullptr;
    };

在这里插入图片描述

上面图示以物理结构数组int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13}创建出来的逻辑结构二叉搜索树的数据结构。

2.3 二叉搜索树的查找

二叉搜索树查找步骤:

  • 规定一个关键值key
  • 从根开始开始比较查找，key比根大则往右边走查找，key比根小则往左边走查找
  • 最多查找高度次，走到到空，还没有找到，这值不存在
  • 在插入接口中，虽然查找合适位置代码逻辑差不多，但是存在个别逻辑差异，注意识别
bool Find(const K& key)
{
    Node* cur = _root->_key;
    while (cur)
    {
        if (key < cur->_key)
        {
            cur = cur->_left;
        }
        else if(key > cur->_key)
        {
            cur = cur->_right;
        }
        else
        {
            return true;
        }
    }
    return  false;
}

2.4 二叉搜索树的插入

插入具体过程:

  • 树为空，则直接新增节点，赋值给root指针
  • 树不为空，按二叉搜索树性质插入位置，插入新节点

在这里插入图片描述

bool Insert(const K& key)
{
    if (_root == nullptr)
    {
        _root = new Node(key);
        return true;
    }

    Node* parent = nullptr;
    //这里cur是临时变量
    Node* cur = _root;

    while (cur)
    {
        if (cur->_key < key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
           return false;
        }
    }

    cur = new Node(key);

    if (parent->_key < key)
    {
        parent->_right = cur;
    }
    else if (parent->_key > key)
    {
        parent->_left = cur;
    }
    return true;
}

插入具体过程细节处理:

  • 需要判断树是否为空树，如果为空，创建节点赋值给_root
  • 创建两个指针parent和cur保证节点的连接
  • 通过不同比较大小，直到cur找到为空的位置，创建节点
  • 该节点需要满足二叉搜索树的特性，需要再次判断，选择连接

2.5 二叉搜索树的删除(难点)

2.5.1 删除该子树根节点情况分析

首先查找元素是否在二叉搜索树中，如果不存在则返回false，否则要删除的节点可能分为下面三种情况。先到需要被删除的节点，这里就不重复实现了。

删除节点情况划分：

  1. 要删除的节点无孩子节点
  2. 要删除的节点只有一个孩子节点
  3. 要删除的节点有左、右孩子节点

2.5.2 删除第一、二情况节点

这里第一种和第一种情况可以归类为同一种情况。无论被删除节点是否有无真实存在的孩子节点，都可以看成要删除的节点只有一个孩子节点，将第一种情况看成第二种情况，被删除节点有空孩子节点。

在这里插入图片描述

if (cur->_left == nullptr)
{
    if (parent->_left == cur)
    {
        parent->_left = cur->_right;
    }
    else if (parent->_right == cur)
    {
        parent->_right = cur->_right;
    }
    delete cur;
}
else if (cur->_right == nullptr)
{
    if (parent->_left == cur)
    {
        parent->_right = cur->_left;
    }
    else if (parent->_right == cur)
    {
        parent->_left = cur->_left;
    }
    delete cur;
}

在这里插入图片描述

关于数据结构学习，我们需要借助具体的逻辑结构去实现"抽象"的物理结构。接下我也希望你们可以借助图和文字进行对代码的解读。

  1. 第一个判断分支决定，parent指向另外一个可能为空的节点。

在这里插入图片描述

  1. 第二个分支判断被删除节点相对parent节点的位置

判断结束后，parent节点进行连接操作进行删除操作。

  1. 小总结：判断被删除节点位置与被删除节点可能不为空孩子位置，进行连接即可。

草稿说明，上面是优化版本说明:

有了上面两个信息的话，比如通过parent->_left == cur需要被删除的节点是左节点，并且cur->_left == nullptr该节点左孩子节点为空，那么parent->_left = cur->_right;。parent->_left 是根据第一个条件，该parent->_left需要重新连接新节点，那么新节点是谁？通过cur->_left == nullptr判断，该左孩子为空，肯定连接右孩子节点。

2.5.3 第三种情况（替换法）

使用替换法删除，简单回顾

  • 左子树上所有节点的值都小于根节点的值
  • 右子树上所有节点的值都大于根节点的值

在这里插入图片描述

被替换的节点需要满足左子树最大节点或者右字数的最小节点其中之一即可。比如满足左子树最大节点，进行交换，该节点满足比左子树都要大，比右子树都要小。

替换法删除的具体流程:

  • 先找到需要被删除节点和被替换节点，进行swap交换数字
  • 通过第一、二种情况进行删除操作
  • 那么需要设置两个指针去需要被替换节点
Node* RightMinParent = cur;
Node* RightMin = cur->_right;

//找到右子树最小的值
while (RightMin->_left)
{
    RightMinParent = RightMin;
    RightMin = RightMin->_left;
}
//找到
swap(cur->_key, RightMin->_key);

if (RightMinParent->_left == RightMin)
{
    RightMinParent->_left = RightMin->_right;
}
else
{
    RightMinParent->_right = RightMin->_right;
}
delete RightMin;
}
return true;

实现该逻辑的具体细节:

  • 这里我选择找到右子树的最小节点，那么只需要关注左边的情况就行了，这也是为什么是while (RightMin->_left)
  • 首先就是第一、二种情况删除的做法
  • RightMinParent不能设置为空指针当删除根节点就会有问题，直接设置为cur

以上三种情况都需要考虑需要被删除节点为根节点

在这里插入图片描述

2.6 采用中序遍历二叉搜索树 

void InOrder()
{
    _InOrder(_root);
    cout << endl;
}

private:
void _InOrder(Node* root)
{
    if (root == nullptr)
    {
        return;
    }

    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}

中序遍历能够按顺序输出树中所有节点的值。从根节点开始，中序遍历的顺序是【左子树 , 根节点 , 右子树】这一过程在BST中恰好能保证节点按从小到大的顺序排列。将内部实现放在private部分，可以避免外部代码错误地调用内部方法，导致程序行为不可预测或出错。通过控制访问权限。外部代码不应该直接操作树的节点，而应该通过公开的接口方法来访问和操作树。

上一篇： Python+Matplotlib 显示通用函数、变换和函数的简单示例

下一篇： Pycharm关于Interpreter问题：ModuleNotFoundError：没有名为

推荐阅读