浙江龙网

  1. 首页 > 生活百科 > >

二叉搜索树 - C++ 实现

生活百科

二叉搜索树 - C++ 实现概述 Overview二叉查找树（英语：Binary Search Tree, 后文中简称 BST）, 也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree）,是在 20 世纪 60 年代为解决标记数据的高效存储问题而设计的, 由 Conway Berners-Lee 和 David Wheeler 发明.
具体指的是一棵空树或者具有下列性质的二叉树:

  1. 若任意节点的左子树不空, 则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空, 则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；
简单来说, 二叉搜索树中的每一个节点都满足: 左子树中的所有元素均小于该节点元素; 右子树中的所有元素均大于该节点元素. \(左子树元素 \le 本节点元素 \le 右子树元素\). 左小右大.
这种结构上的设计使得 BST 可以以二分查找思路实现 \(\Omega(\log n)\) （不是大o, 而是下限在logn）级别的快速增, 删, 查等操作, 因为在树中的每一步操作都能排除一半的元素. 完成一颗二叉搜索树的建立之后, 我们还可以以中序遍历的方式得到排序后的序列, 这也是二叉搜索树被称为排序二叉树的原因.
需要注意的是, 二叉搜索树的效率与在建立时输入的元素顺序有很大的关系. 在最坏情况下, 二叉搜索树会退化成链表. 树层数大大增加使得查找等操作需要消耗更多的时间）此时, 需要对树进行额外的优化 - 平衡, 来保证高效的运行效率. 在本文中我们不作讨论, 本文仅介绍朴素的二叉搜索树.
如果看完之后还是不太理解的话, 可以看看这个美国旧金山大学CS做的一个算法可视化. Binary Search Tree Visualization (usfca.edu) 在这个网站上详细地看到 BST 每一步的操作.做的很好, 不妨去玩玩!
基本操作 Operations和其他的数据结构类似, 二叉搜索树也有着这样的几个基本操作.
搜索 Search?根据元素值直接搜索节点假设要搜素的节点的元素值为 item.
那么搜索就是要从数的根节点 root 开始, 逐节点遍历该树.
若当前扫描到的节点的元素值小于 item, 则往右走; 若元素值大于 item 则左走. 直到扫描到目标节点或遇到 nil 节点时（未找到该元素）停止搜索, 返回结果.
具体的代码实现如下.
void insert(const int item){TreeNode *scan = root;TreeNode *prev = root;while (scan != nullptr){prev = scan;scan = item < scan->data ? scan->left : scan->right;}TreeNode *newNode = new TreeNode(item);if (root){(item < prev->data ? prev->left : prev->right) = newNode;newNode->parent = prev;}else{root = newNode;}return;}? 找节点的前驱/后继前驱节点指的是树在中序遍历的序列中, 目标结点的前一个结点(类似链表中前驱的定义).（当目标结点为第一个结点是返回nil）
e.g. 如一颗树的中序遍历序列为: {1, 2, 3, 4, 5}, 那么元素值为 2 的节点的前驱就是元素值为 1 的节点; 元素值为 1 的节点的前驱就是 nil.
在BST中, 因为BST 的定义, 其中序遍历序列就是树中所有元素按元素值大小排序而输出的序列.
因此, 前驱节点也可以被定义成所有小于目标元素的所有元素中的最大值 \(\max( \{item\ |\ item \in tree\and item < target\})\).
根据此定义我们来完成搜索前驱节点的算法.
由 BST 的定义我们可以得到一个结论,
设有一个节点 node, 在中序遍历的序列中:
  1. 如果 node 是父节点的左节点
    左子树中的所有节点 < node < 父节点
  2. 如果 node 是父节点的右节点
    父节点 < node < 左子树中的所有节点
(光这样子讲可能有点抽象, 想象一下把一颗 BST 拍扁, 得到的序列就是中序遍历的序列, 容易得到以上结论)
基于上面的结论, 请考虑以下这两种 case.
  • case 01/ 有左子树. 所有有可能的 node 的均在左子树
    那就意味着, 我们只需要找到 node 左子树中最大的那个节点即可.
  • case 02/ 无左子树. 需要一直向祖先追溯. 直到找到第一个比 node 小的节点.
    第一个找到的节点就是在中序遍历中最接近 node 节点的节点. 也就是 node 的前驱结点.
    若找不到, 就说明 node 就是中序遍历中最小的元素, 返回 nil 节点.
具体代码实现如下.
TreeNode *p_pred(int item){TreeNode *itemNode = p_find(item);if (!itemNode)return nullptr;if (itemNode->left){return p_max(itemNode->left);}else{TreeNode *scan = itemNode->parent;while (scan && scan->left == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;}}

推荐阅读


上一篇：生成海报， 生成有特色的头像 小程序利用canvas 绘制图案

下一篇：c++ 关于引用变量你不知道的东西