数据结构之排序二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构之排序二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

排序二叉树

基本概念

二叉树是一种从上往下的树状结构的数据结构，从根节点开始每个节点最多有两个子节点，左边的为左子节点，右边的为右子节点。

排序二叉树–有顺序，且没有重复元素的二叉树。顺序为：

对每个节点而言：

1）如果左子树不为空，则左子树上的所有节点都小于该节点；

2）如果右子树不为空，则右子树上的所有节点都大于该节点；

数据结构之排序二叉树,高手面试,数据结构,算法

如图，根节点为5，左边的节点都小于5，右边的节点都大于5。

插入操作

首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是：新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节点，则到左子树中寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。

数据结构之排序二叉树,高手面试,数据结构,算法

删除操作

删除操作主要分为三种情况，即要删除的节点无子节点，要删除的节点只有一个子节点，要删除的节点有两个子节点。

对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点。
对于要删除的节点有两个子节点，则首先找该节点的替换节点（即右子树中最小的节点），接着替换要删除的节点为替换节点，然后删除替换节点。

数据结构之排序二叉树,高手面试,数据结构,算法

查询操作

查找操作的主要流程为：先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。

遍历操作

排序二叉树可以方便的按序遍历，用递归的方式。如下图的例子，先访问根节点的左子树，一直到最左边的节点–1，1没有右子树

，返回上一层，访问3，然后访问3的右子树，4没有左子树，所以访问4，然后4的右子树6，以此类推。1–3--4–6--7–8--9

数据结构之排序二叉树,高手面试,数据结构,算法

不用递归的方式，也可以实现按序遍历：第一个节点为最左边的节点，从第一个节点开始，依次找后继节点，找其后继节点的算法为：

1）如果该节点有右子节点，则后继节点为右子树中的最小节点；

2）如果该节点无右子节点，则后继节点为父节点或者某个祖先节点，从当前节点往上找，如果它是父节点的右孩子，则继续找父节点，直到它不是右孩子或父节点为空，第一个非右孩子节点的父节点就是后继节点，如果找不到这样的祖先节点，则后继为空，遍历结束。文章来源地址https://www.toymoban.com/news/detail-783475.html

到了这里，关于数据结构之排序二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！