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

数据结构系列文章

树是一种数据结构，它是n(n>=0)个节点的有限集。n=0时称为空树。n>0时，有限集的元素构成一个具有层次感的数据结构。

区别于线性表的元素关系，树中的节点是一对多的关系。树具有以下特点：

n>0时，根节点是唯一的，不可能存在多个根节点。

每个节点有零个至多个子节点；除了根节点外，每个节点有且仅有一个父节点。根节点没有父节点。

树有许多相关的术语与概念，在学习树的结构之前，我们要熟悉这些概念。二叉排序树的删除

子树：除了根节点外，每个子节点都可以分为多个不相交的子树。（图二）

孩子与双亲：若一个结点有子树，那么该结点称为子树根的"双亲"，子树的根是该结点的"孩子"。在图一中，B、H是A的孩子，A是B、H的双亲。

兄弟：具有相同双亲的节点互为兄弟，例如B与H互为兄弟。

节点的度：一个节点拥有子树的数目。例如A的度为2，B的度为1，C的度为3.

叶子：没有子树，也即是度为0的节点。

分支节点：除了叶子节点之外的节点，也即是度不为0的节点。

内部节点：除了根节点之外的分支节点。

层次：根节点为第一层，其余节点的层次等于其双亲节点的层次加1.

树的高度：也称为树的深度，树中节点的最大层次。

有序树：树中节点各子树之间的次序是重要的，不可以随意交换位置。

无序树：树种节点各子树之间的次序是不重要的。可以随意交换位置。

森林：0或多棵互不相交的树的集合。例如图二中的两棵树为森林。

二叉树或者为空集，或者由一个根节点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。从定义可以看出一棵二叉树：

二叉树是有序树，区分左子树与右子树，不可以随意交换子树位置。

一个节点的子树数量取值范围为0，1，2。0代表该节点是叶子节点，1代表该节点只有左子树或只有右子树，2代表该节点有左右子树。

根据定义，一棵二叉树有5中基本形态：

所有节点都只有左子树的二叉树叫做左斜树，所有节点都只有右子树的二叉树叫做右斜树。左斜树和右子树统称为斜树。

斜树已经退化成线性结构，二叉树在查找上表现出来优异性能在斜树得不到体现。

满二叉树要满足两个条件：

所有的节点都同时具有左子树和右子树。

所有的叶子节点都在同一层上。

在同样深度的二叉树中，满二叉树的节点数目是最多的，叶子数也是最多的。二叉排序树的删除

在一棵二叉树中，只有最下两层的度可以小于2，并且最下一层的叶子节点集中出现在靠左的若干位置上。

或者这样定义：对一棵具有n个节点的二叉树按层序从左到右编序，二叉树树某个节点的编序与同样位置的满二叉树节点的编序相同如果所有节点都满足这个条件，则二叉树为完全二叉树。

从定义可以看出： 满二叉树一定是完全二叉树；完全二叉树不一定是满二叉树。

二叉排序树也称为二叉搜索树或二叉排序树。二叉排序树的节点包含键值key。二叉排序树或者是一棵空树，否则要求：

若它的左子树不为空，那么左子树上所有节点的key都小于根节点的key

若它的右子树不为空，那么右子树上所有节点的key都大于根节点的key

它的左右子树也分别为二叉排序树

根据定义，二叉查找树中没有重复key的节点。

在实际的应用中，二叉排序树的应用比较多，我们后面要讲的L树本身也是一种二叉排序树。

证明：利用数学归纳法进行证明

当i==1时，第1层节点数目为2^(i-1) = 2^(1-1) = 2^0 = 1。显然成立，此时二叉树只有根节点。

假设i>1时，第i层的节点数目为2^(i-1)。

根据假设，只需证明第i+1层节点数为2^i 即可。

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