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

由于二叉树每个节点最多有两个孩子，故第(i+1)层上的节点数最多是第i层的两倍。

即：第i+1层上节点数最多为: 2* 2^(i-1) = 2 ^ i

故假设成立，命题得证。

证明：二叉树节点数最多时，每层的节点树都必须最多。

根据性质一，深度为k的二叉树的节点数最多为: 2^0 + 2^1 +....+2^(k-1) = 2 ^ k -1

证明：二叉树节点度数最大为2，则 ： n = n0 + n1 + n2 (等式一)

从孩子个数角度出发： 度为0的节点没有孩子， 度为1的节点没有1个孩子，度为2的节点有2个孩子，孩子总数为 n00 + n11 +n2 2 = n1+2n2；树的所有节点中，只有根不是任何节点的孩 子，因此有 n -1 = n1 + 2* n2 ,即 n = n1 + 2* n2 + 1. （等式二）

由等式一等式而可以推出 n0 = n2 +1

证明：高度为h的二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。

如果i=1 ，则节点为根节点，没有双亲。

如果2 * i > n ，则节点i没有左孩子 ；否则其左孩子节点为2*i . （n为节点总数）

如果2 * i+1>n ，则节点i没有右孩子；否则其右孩子节点为2*1+1

二叉查找树的定义我们已经知道。要维护二叉查找树的特性，比较复杂的是删除节点操作，我们将进行重点的解析。不过我们先来看看二叉查找树的节点结构定义与类定义。

value:节点的值，也即是上文的key，类型由模板参数决定

lchild :指向节点的左孩子

rchild:指向节点的右孩子

parent: 指向节点的双亲

这里我们定义了二叉排序树的类型BSTree。它包含了：

BSTree的根节点root，这是唯一的数据成员

操作的外部接口与内部实现接口。例如 preOrder()为提供给用户使用的接口，接口声明为public；而preOrder(LTreeNode* pnode)是类内部为了递归操作所使用的接口，接口声明为private。

提供的其他接口都有相应的备注说明。

假设我们要为数组 a[] = {10 ， 5 ， 15 ， 6 ， 4 ， 16 }构建一个二叉排序树，我们按顺序逐个插入元素。

插入过程是这样的：

如果是空树，则创建一个新节点，新节点作为根，因此以元素10构建的节点为该二叉查找树的根。

插入5，5比10小，与10的左孩子节点进行比较，10的左孩子节点为空，进行插入。

插入15，15比10大，与10的右孩子节点进行比较，10的右孩子节点为空，进行插入。

插入6，6比10小，与10的左孩子节点5比较；6比5大，与5的右孩子节点进行比较，5的右孩子为空，进行插入。

插入4，4比10小，与10的左孩子节点5比较；4比5小，与5的左孩子节点进行比较，5的左孩子为空，进行插入。

插入16，16比10大，与10的右孩子节点15比较；16比15大，与15的右孩子节点进行比较，15的右孩子为空，进行插入。

从这个过程我们可以总结出插入新元素的步骤：

寻找元素合适的插入位置：新元素与当前结点进行比较，若值大于当前结点，则从右子树进行寻找；否则从左子树进行寻找.

找到插入位置之后，以元素的值构建新节点，插入二叉排序树中

该过程的实现代码：

将构建出来的新节点插入二叉排序树时，需要修改链接指针的指向。

遍历平衡二叉树，就是以某种方式逐个“访问”二叉树的每一个节点。“访问”是指对节点的进行某种操作，例如输出节点的值。

平衡二叉树是有序树，严格区分左子树与右子树，如果规定左子树先于右子树的次序，我们有三种方式遍历二叉树：

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