数据结构——树和二叉树

Dear 丶 2022-09-13 16:11 248阅读 0赞

# 1.树的定义 #

树(Tree)是n(n>=0)个结点的有限集，它或为空树(n= 0); 或为非空树，对于非空树T:  
(1)有且仅有一个称之为根的结点；  
(2)除根结点以外的其余结点可分为m(m>0）个互不相交的有限集T1,T2, …,Tm，其中每  
一个集合本身又是一棵树， 并且称为根的子树(SubTree)。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_18_color_FFFFFF_t_70_g_se_x_16][]

# 2.树的基本术语 #

**(1) 结点**：树中的一个独立单元。包含一个数据元素及若于指向其子树的分支，如图5.1  
(b) 中的A 、B 、C 、D 等。（下面术语中均以图5.1 (b) 为例来说明）

**(2)结点的度**：结点拥有的子树数称为结点的度。例如，A的度为3, C的度为l, F的度  
为0。

**(3)树的度**： 树的度是树内各结点度的最大值。图5.1 (b) 所示的树的度为3。

**(4) 叶子**：度为0 的结点称为叶子或终端结点。结点K 、L 、F 、G 、M 、I 、J都是树的  
叶子。

**(5)** **非终端结点**：度不为0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点  
也称为内部结点。

**(6)双亲和孩子**：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例  
如，B的双亲为A, B的孩子有E和F。

**(7) 兄弟**：同一个双亲的孩子之间互称兄弟。例如，H 、I 和J互为兄弟。

**(8) 祖先**：从根到该结点所经分支上的所有结点。例如， M 的祖先为A 、D 和H。

**(9) 子孙**：以某结点为根的子树中的任一结点都称为该结点的子孙。如B 的子孙为E 、K 、L  
和F。

**(10) 层次**：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的  
层次等千其双亲结点的层次加l。

**(11)堂兄弟**：双亲在同一层的结点互为堂兄弟。例如，结点G 与E 、F、H 、I 、J互为堂兄弟。

**(12)树的深度**：树中结点的最大层次称为树的深度或高度。图5.1 (b)所示的树的深度  
为4。

**(13 )有序树和无序树**：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），  
则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的  
称为最后一个孩子。

**(14)森林**：是m (m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即  
为森林。由此，也可以用森林和树相互递归的定义来描述树。

# 3. 二叉树的定义 #

**二叉树(Binary Tree)**是n(n>=0)个结点所构成的集合，它或为空树(n=0); 或为非空树，  
对于非空树T:  
(1) 有且仅有一个称之为根的结点；  
(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子  
树，且T1和T2本身又都是二叉树。

二叉树与树一样具有递归性质，**二叉树与树的区别**主要有以下两点：  
(1 )二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）；  
(2). 二叉树的子树有左右之分，其次序不能任意颠倒。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16][]

# 4.满二叉树和完全二叉树 #

**满二叉树**：深度为k 且含有![2^\{k\}-1][2_k_-1]个结点的二叉树。

图5.6(a)所示是一棵深度为4 的满二叉树。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

**满二叉树的特点**是：

*  每一层上的结点数都是最大结点数，即每一层l的结点数都具有最大值![2^\{i\}-1][2_i_-1]。

可以对满二叉树的结点进行连续编号， 约定编号从根结点起， 自上而下， 自左至右。由此可引出完全二叉树的定义。

**完全二叉树**：深度为k的， 有n个结点的二叉树， 当且仅当其每一个结点都与深度为K的满  
二叉树中编号从1至n的结点一一对应时， 称之为完全二叉树。图5.6(b)所示为一棵深度为4  
的完全二叉树。

**完全二叉树的特点是**：

*  (1)叶子结点只可能在层次最大的两层上出现；
 *  (2)对任一结点， 若其右分支下的子孙的最大层次为L, 则其左分支下的子孙的最大层次必为lL或L+ 1。图5.6 中(c)和(d) 不是完全二叉树。

# 5.二叉树的性质和存储结构 #

符号说明：符号![\\sqsubset x\\sqsupset][sqsubset x_sqsupset]表示不大于x的最大整数， ![\\subset x\\supset][subset x_supset]表示不小于x的最小整数。

二叉树具有下列重要**特性**：  
(1) 在二叉树的第i层上至多有![2^\{i-1\}][2_i-1]个结点（i>=1)。

(2) 深度为k的二叉树至多有![2^\{k-1\}][2_k-1]个结点(k>=1)。

(3) 对任何一棵二叉树T, 如果其终端结点数为n，度为2的结点数为m，则n = m+1。

(4) 具有n 个结点的完全二叉树的深度为![\\sqsubset log2^\{n\}\\sqsupset +1][sqsubset log2_n_sqsupset _1] 。

(5) 如果对一棵有n 个结点的完全二叉树（其深度为![\\sqsubset log2^\{n\}\\sqsupset +1][sqsubset log2_n_sqsupset _1] ) 的结点按层序编号（从  
第1 层到第![\\sqsubset log2^\{n\}\\sqsupset +1][sqsubset log2_n_sqsupset _1] 层， 每层从左到右）， 则对任一结点i(![1\\leqslant i\\leqslant n][1_leqslant i_leqslant n]), 有:

*  (1 )如果i =1 , 则结点l是二叉树的根，无双亲；如果i>1 , 则其双亲PARENT(i)是结点![\\sqsubset i/2\\sqsupset][sqsubset i_2_sqsupset]。
 *  ( 2 )如果2i>n, 则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD1( )是结点2i。
 *  (3)如果2i+1>n, 则结点i无右孩子；否则其右孩子RCHILD(i )是结点2i+1。

结点与编号的对应关系如下图：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

# 6.二叉树的存储结构 #

类似线性表，二叉树的存储结构也可采用顺序存储和链式存储两种方式。

## 6.1. 顺序存储结构 ##

//-----二叉树的顺序存储表示－－－－－
    #define MAXTSIZE 100                    ／／二叉树的最大结点数
    typedef TElemType SqBiTree [MAXTSIZE];  //0号单元存储根结点
    SqBiTree bt;

顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反  
映出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。

对千完全二叉树，只要从根起按层序存储即可，依次自上而下、自左至右存储结点元素， 即  
将完全二叉树上编号为i 的结点元素存储在如上定义的一维数组中下标为i-1的分量中。例如，  
图5.8 (a)所示为图5.6 (b)所示完全二叉树的顺序存储结构。

对千一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量  
中，图5.6 (C)所示二叉树的顺序存储结构如图5.8 (b)所示，图中以"O"表示不存在此结点。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

由此可见， 这种顺序存储结构仅适用于完全二叉树。因为， 在最坏的情况下， 一个深度为K  
且只有K个结点的单支树（树中不存在度为2 的结点）却需要长度为![2^\{k\}-1][2_k_-1]的一维数组。这造成了  
存储空间的极大浪费， 所以对于一般二叉树，更适合采取下面的链式存储结构。

## 6.2 链式存储结构 ##

设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义得知，二叉树的结点（见图5.9 (a))由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3 个域：数据域和左、右指针域，如图5.9 (b) 所示。有时， 为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域，如图5.9 (C)所示。利用这两种结点结构所得二叉树的存储结构分别称之为二叉链表和三叉链表，如图5.10 所示。链表的头指针指向二叉树的根结点。容易证得，在含有n个结点的二叉链表中有n+l 个空链域。在5.5 节中将会看到可以利用这些空链域存储其他有用信息，从而得到另一种链式存储结构一线索链表。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/cc0355f730d946949be9814e18535b7c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/44831d9ddf854097bdbdaa1d39ed2514.png
[2_k_-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bk%7D-1
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/7dd410446af94a98931d01b7c220717e.png
[2_i_-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bi%7D-1
[sqsubset x_sqsupset]: https://latex.codecogs.com/gif.latex?%5Csqsubset%20x%5Csqsupset
[subset x_supset]: https://latex.codecogs.com/gif.latex?%5Csubset%20x%5Csupset
[2_i-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bi-1%7D
[2_k-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bk-1%7D
[sqsubset log2_n_sqsupset _1]: https://latex.codecogs.com/gif.latex?%5Csqsubset%20log2%5E%7Bn%7D%5Csqsupset%20&plus;1
[1_leqslant i_leqslant n]: https://latex.codecogs.com/gif.latex?1%5Cleqslant%20i%5Cleqslant%20n
[sqsubset i_2_sqsupset]: https://latex.codecogs.com/gif.latex?%5Csqsubset%20i/2%5Csqsupset
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/21444d97c165457b9851f11b83946f12.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/c328c34f7cbf4ab2b307b39ee560c28d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQWxsZW4gUm9zb24_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/d8803fee5fdc4780bf67c65947439a40.png