我们在之前学习了通用树的相关知识,那么通用树的结构实现相对来说比较复杂,有没有一种比较简单的树呢?我们在之前的通用树结构中使用的是<强>双亲孩子表示法,<强>每个结点都有一个指向其双亲的指针,每个结点都有若干个指向其孩子的指针强。结构如下图所示
那么还有另一种树结构模型——<强>孩子兄弟表示法强。每个结点都有<强>一个指向其第一个孩子的指针,每个结点都有一个指向其第一个右兄弟的指针强。结构如下图所示
孩子兄弟表示法的特点:<强> 1,能够表示任意的树形结构;2,每个结点包含一个数据成员和两个指针成员;3,孩子结点指针和兄弟结点指针构成了“树杈”。
下来我们来看看二叉树的定义:二叉树是由n (n祝辞=0)个结点组成的有限集合,该集合或者为空,或者是由一个根结点加上两颗分别称为左子树和右子树的,互不相交的二叉树组成。二叉树有以下5种形态
下来我们来看看两种特殊的二叉树:<强>满二叉树(满二叉树)和完全二叉树(完全二叉树)。
1,满二叉树:如果二叉树中所有分支结点的度数都为2,且叶子结点都在同一层次上,则称这类二叉树为满二叉树。
2,完全二叉树:如果一颗具有n个结点的高度为K的二叉树,它的每一个结点都与高度K的满二叉树中编号为1,n的结点一一对应。则称这颗二叉树为完全二叉树(从上到下从左到右编号)。
完全二叉树的相关特性:<强> a>同样结点数的二叉树,完全二叉树的高度最小;b>完全二叉树的叶结点仅出现在最下面两层:最底层的叶结点一定出现在左边,倒数第二层的叶结点一定出现在右边,完全二叉树中度为1的结点只有左孩子强。如下图所示
下来我们来看看二叉树的几个性质:
<强> 1,在二叉树的第我层最多有个结点(我在=1)。
第一层最多有个结点;
第二层对多有个结点;
第三层最多有个结点;
……
<强> 2,高度为k的二叉树最多有个结点(k祝辞=0)。
如果有一层,最多有1==1个结点;
如果有二层,最多有1==3个结点;
如果有三层,最多有1==7个结点;
……
<强> 3,对任何一颗二叉树,如果其叶结点有个,度为2的非叶结点有个,则有。
证明:假设二叉树中度1的结点有个且总结点为n个,则:;
假设二叉树中连接父结点与子结点间的边为e条,则:;
所以:
<强> 4,具有n个结点的完全二叉树的高度为((X)表示不大于X的最大整数)。
证明:假设这n个结点组成的完全二叉树高度为k,则:;
因为n为整数,所以:;
取对数;
因为k为整数,所以:
<强> 5,一颗有n个结点的完全二叉树(高度为),按层次对结点进行编号(从上到下,从左到右),对任意结点我有:
如果我=1,则结点我是二叉树的根,如果我比;1,则其双亲结点为[i/2];
如果我& lt; 2=n,则结点我的左孩子为2我;如果2我比;n,则结点我无左孩子;
如果2 i + 1 & lt;=n,则结点我的右孩子为2 + 1,如果2 i + 1比;n,则结点我无右孩子;
通过对二叉树的学习总结如下:<强>
