数据结构之二叉树

淩亂°似流年 2022-06-15 01:14 202阅读 0赞

## 树 ##

定义：满足以下条件的就是树：   
1. 有且仅有一个特定的称为根Root的结点。   
2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每个集合本身又是一个棵树，并称为根的子树。

树是[数据结构][Link 1]中一种常见的数据结构，比如我们排序中常见的二叉树，红黑树等。最常见的是树形表示法和广义表表示法。树的结构示意图如下所示：   
![这里写图片描述][SouthEast]

## 二叉树 ##

二叉树是一种特殊的顺序树，它有左右两个孩子子树，即左右孩子顺序不能替换。二叉树的结点数为大于0小于等于2。常见的二叉树结构如下：   
![这里写图片描述][SouthEast 1]

### 二叉树的性质 ###

性质1 在二叉树的第i层上至多有个结点(i>=1)   
由数据归纳法即可证明，   
i=1，结点数为1   
i=2，结点数为2   
i=3，结点数为4   
i=4，结点数为8   
I=n, 结点数为.   
性质2 深度为K的二叉树至多有-1个结点(k >=1)   
换言之，如果二叉树的深度确定，则其最大的结点数也是确定的。   
证明（可以利用性质1）   
深度为K的二叉树的结点个数=二叉树中每一层结点个数的总和。即为：   
= 1 + 2 + 4 + 8 + … + =-1（等比公式）   
性质3 二叉树中，终端结点个数与度为2的结点个数有如下关系：   
N0= N2 + 1   
性质4：结点数为n的完全二叉树，其深度为(向下取整)+ 1   
由性质2及完全二叉树的定义有：   
性质5：在按层序编号的n个结点的完全二叉树中，任意一个结点i()有：   
(1) i = 1时，结点i是树的根，否则(i> 1)，结点i的双亲为i/2(向下取整),如   
,取i = 2.   
(2) 2i > n时，结点i无左孩子，为叶结点，否则结点i的左孩子为结点2i   
(3) 2i+1 > n时，结点i无右孩子，否则结点i的右孩子为结点2i +1.   
性质6: 含有n个结点的二叉链表中，有n + 1个空链域。   
![这里写图片描述][SouthEast 2]

[Link 1]: http://lib.csdn.net/base/datastructure
[SouthEast]: /images/20220615/1e53528e15df4b4b9075ebcbad2b04a3.png
[SouthEast 1]: /images/20220615/d374ace33e7a4098bae9c6529bbc7a07.png
[SouthEast 2]: /images/20220615/bd65f29e106649fc82b10aaa80b6a97b.png