二叉排序树 删除根节点_二叉排序树的删除_二叉排序树的删除图解(3)

前序遍历

中序遍历

后序遍历

我们以如图的两棵二叉排序树进行遍历的算法演示。

若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。（简记为：VLR）

前序遍历树a：10 5 4 3 6 15 16

前序遍历树b：5 3 2 4 8 7 9

若二叉树为空，则空操作返回，否则从根节点开始，中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。（简记为：LVR）

前序遍历树a：3 4 5 6 10 15 16

前序遍历树b：2 3 4 5 7 8 9

二叉排序树的中序遍历刚好输出一个非递减的有序序列。

若树为空，则返回空操作，否则从左到右先叶子后节点的方式遍历访问左右子树，左右子树都访问结束，才访问根节点。（简称LRV）

后序遍历树a：3 4 6 5 16 15 10

后序遍历树b：2 4 3 7 9 8 5

对于一棵二叉排序树，中序遍历时刚好可以输出一个非递减的序列。例如前序遍历图九树a：3 4 5 6 10 15 16，则可称：

4是5 前驱节点，6是5的后继节点

6是10的前驱节点，15是10的后继节点

一个节点的前驱节点有3种情况：

它有左子树，则左子树根节点为其前驱节点

它没有左子树，且它本身为右子树，则其父节点为其前驱节点

它没有左子树，且它本身为左子树，则它的前驱节点为“第一个拥有右子树的父节点”

同样的，一个节点的后继节点也有三种情况：

它有右子树；则其后继节点为其右子树的最左节点

它没有右子树，但它本身是一个左孩子，则后继节点为它的双亲

它没有右子树，但它本身是一个右孩子，则其后继节点为“具有左孩子的最近父节点”

删除二叉排序树的某个节点有三种情况：

被删除节点同时有左子树与右子树。

被删除节点只有左子树或只有右子树。

被删除节点没有子树。

对于第一种情况，我们的处理方式是将前驱节点的值保存在当前结点，继而删除前驱节点。

对于第二种情况，我们直接用子树替换被删节点。

对于第三种情况，我们可以直接删除节点。

删除节点的代码：

我们可以递归或非递归地进行元素的查找。元素的查找过程与元素的插入过程一致，也是在不断地与当前结点进行比较，若值比当前节点的值大，则在右子树进行查找，若值比当前节点的值小，则在左子树进行查找，可以看到这是一个很适合递归操作的过程。而由于二叉排序树这种左小右大的节点特征，也很容易进行非递归查找。

二叉排序树的最小值位于其最左节点上；最大值位于其最右节点上：

使用后序遍历递归销毁二叉树

运行结果：

在github上存放了二叉排序树的vs项目工程。这是二叉排序树的源代码：

https://github.com/huanzheWu/Data-Structure/blob/master/BSTree/BSTree/BSTree.h

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29834-3.html