考研笔记-计算机之数据结构:层次结构-树(基本概念)

——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。

树：n（n≥0）个结点的有限集，且满足：

1）n>0时，有且仅有一个根结点；

2）n>1时，除根外的其余结点可分为m（m>0）个互不相交的有限集T₁，T₂，…，T_m，其中每个集合本身又是一棵树（递归定义），并且称为根的子树。

抽象数据类型树：

1）数据对象D：D为具有相同特性的数据元素的集合。

2）数据关系R：a)根；b)与根直接相关的关系；c)子树中的关系（递归定义）。

3）基本操作P：关键操作为遍历（即每个结点均被“访问”一次，且仅被“访问”一次，访问不仅仅是到达，而是在到达的基础上有其他操作，如插入新结点）。

树的表示形式：

1）嵌套集合：集合的集体，其中任意两个集合或者不相交，或者一个包含另一个。

2）广义表：根作为由子树森林组成的表的名字写在表的左边。

3）凹入表示法：类似书的目录。

树中的结点：（树的结点（分支结点（根结点，内部结点），终端【叶子】结点））。

树的结点的度：结点拥有的子树数。

树的度：树中各结点的度的最大值。

有序树：树中结点的各个子树看成从左至右是有次序（即不能互换）的。

无序树：树中结点的各个子树看成是无次序（即可以互换）的。

树的性质：

1）度为k的树的结点总数n=n₀+ n₁+…+ n_k（n_k为度为k的结点的个数，），且n-1=0 n₀+1 n₁+…+ kn_k（所有结点的度数之和（即分支总数）等于结点总数减1，因为除根结点外，每个结点均对应树的一度，即有一个分支进入），故n₀=1+1 n₂+2 n₃+…+(k-1) n_k。

2）度为k的树中第i层上至多有k^i-1个结点。（助记：首项为1的等比数列。）

3）高度为h的k叉树至多（即满k叉树）有(k^h-1)/(k-1)个结点。（助记：等比数列的和。）

4）具有n个结点的k叉树的最小高度（即完全k叉树）为。

森林：m（m≥0）棵互不相交的树的集合。

就逻辑结构而言，任何一棵树是一个二元组Tree=(root,F)，其中，root是数据元素，称作树的根结点；F是m（m≥0）棵树的森林，F=(T₁,T₂,…,T_m)，其中，T_i=(r_i,F_i)称作根root的第i棵子树；当m≠0时，树根和其子树森林之间存在下述关系RF={<root,r_i>|i=1,2,…,m,m>0}。该定义有助于得到森林和树与二叉树之间转换的递归定义。

二叉树：1）度为2的有序树；或2）空树。

二叉树的性质：

1）对于任意一棵二叉树，n₀= n₂+1（因为n=n₀+ n₁+ n₂，n-1=0 n₀+1 n₁+2n₂）。

2）二叉树的第i层上至多有2^i-1个结点。

3）高度为h的二叉树至多（即满二叉树）有(2^h-1)个结点。

4）具有n个结点的二叉树的最小高度（即完全二叉树）为。（因为，即，故，又因为h为整数，所以）

5）如果对一棵有n个结点的完全二叉树（其高度为）的结点按层序编号（从第1层到第层，每层从左到右），则对任一结点i(1≤i≤n)，有

a)若i=1，则结点i是二叉树的根，无双亲；若i>1，则其双亲是结点；

b)若2i>n，则结点i无左孩子（结点i为叶子结点）；若2i≤n，则其左孩子是结点2i；

c)若2i+1>n，则结点i无右孩子；若2i+1≤n，则其右孩子是结点2i+1。

（证明：结点i在完全二叉树中所处的层次为，结点i所处层的满二叉树的结点总数为，结点i所处层的上一层的满二叉树的结点总数为，与结点i处于同一层且位于其前面的结点总数为，则这些结点的孩子结点共有，所以结点i的左孩子结点（若存在）的编号为）。

树的计数

树的计数是指具有n个结点的不同形态的有序树有多少棵。

二叉树T₁和T₂相似是指二者都为空树，或者二者均不为空树，且它们的左右子树分别相似。

二叉树T₁和T₂等价是指二者不仅相似，而且所有对应结点上的数据元素均相同。

二叉树的计数问题就是讨论具有n个结点、互不相似的二叉树的数目。

具有n个结点的互不相似的二叉树有棵。

（证明：因为先序遍历序列和中序遍历序列或后序遍历序列和中序遍历序列均可唯一确定一棵二叉树，则当先序或后序序列固定时，中序序列与二叉树便一一对应。假设对二叉树的n个结点从1到n加以编号，且令其前序序列为123…n，则不同的二叉树所得中序序列不同。因此不同形态的二叉树的数目恰好是前序序列均为123…n的二叉树所能得到的中序序列的数目。而中序遍历的过程实质上是一个结点（根）进栈和出栈的过程。二叉树的形态确定了其结点进栈和出栈的顺序，也确定了其结点的中序序列。由此，由前序序列123…n所能得到的中序序列的数目恰为数列123…n按不同顺序进栈和出栈所能得到的排列的数目，该数目为。公式证明：n次进栈和n次出栈的排列等价于n个1和n个0的排列，且任意0前面的1的个数不能少于0的个数，其中1表示进栈，0表示出栈。n个1和n个0的排列，且存在0前面的1的个数少于0的个数的排列，等价于n-1个1和n+1个0的排列。）

一棵树可以转换成唯一的一棵没有右子树的二叉树，反之亦然。则具有n个结点的不同形态的树的数目和与其对应的具有n个结点的不同形态的没有右子树的二叉树的数目相同，而具有n个结点的不同形态的没有右子树的二叉树的数目和其具有n-1个结点的不同形态的左子树的的数目相同，进而可推得具有n个结点的不同形态的树的数目和具有n-1个结点的互不相似的二叉树的数目相同。

树的遍历