树

树的基本概念和术语

定义

1、树(Tree)是n(n≥0)个结点的有限集T,n=0时称为空树，任意非空树

• (1)有且仅有一个特定的称为根(Root)的结点;
• (2)n>1时，除根结点外的其余结点可分为m(m≥0)个互不相交的子集1，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。

2、从逻辑上看，树形结构具有以下特点:

• (1)任何非空树中有且仅有一个结点没有前驱结点，这个结点就是树的根结点。
• (2)除根结点之外，其余所有结点有且仅有一个直接前驱结点。
• (3)包括根结点在内，每个结点可以有多个直接后继结点。
• (4)树形结构是一种具有递归特征的数据结构。
• (5)树形结构中的数据元素之间存在的关系通常是一对多，或者多对一的关系。

表示法

1、树形结构

2、嵌套结构

3、凹形表示法

4、广义表表示法
(A (B (E，(F (J, K))), c (G), D(H，I)))

广义表知识点

基本术语

• (1)结点的度:结点所拥有的子树的个数。如A的度为3，E的度为2。
• (2)树的度:树中结点度的最大值。如图所示的树的度为3。
• (3)叶子(终端结点):度为0的结点。如K，L，F，G，H，M，N，J都是叶子结点
• (4)分支结点（非终端结点)：度不为0结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。如B，C、D等结点是分支结点。
• (5)孩子:结点的直接后继（即结点的子树的根）。如B是A的孩子，N是I的孩子。
• (6)双亲:结点的直接前趋。如B的双亲是A，N的双亲是I。
• (7)兄弟:同一双亲的孩子互为兄弟。如B、c，D互为兄弟，M，N互为兄弟。
• (8)子孙:一棵树上的任何结点（不包括根结点）称为根的子孙。如图中其它结点都是根结点A的子孙。
• (9)祖先:从根结点开始到该结点连线上的所有结点（除该结点）都是该结点的祖先。如N的祖先是I，C，A.
• (10)路径:若树中存在一个结点序列a1，k2，...，ki，使得ki是ki+1的双亲(1≤ i < j)，则称该结点序列是从k1到kj的一条路径或道路。路径的长度指路径所经过的边（即连接两个结点的线段）的数目，等于j-1。如：结点A到K有一条路径ABEK，路径长度为3

注意：
若一个结点序列是路径，则在树的树形图表示中，该结点序列"自上而下"地通过路径上的每条边。
从树的根结点到树中其余结点均存在一条唯一的路径。

• (11)结点的层:设根结点的层数为1，其余结点的层数等于双亲结点的层数加1。如B的层数是2，N的层数是4。
• (12)树的高度(或深度)﹔树中所有结点层数的最大值。图所示的树的高度为4。
• (13)有序树和无序树:将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树；否则称为无序树。
• (14)森林:是m(m≥0)棵互不相交的树的集合。树和森林的概念相近，删去一棵树的根，就得到一个森林;反之，加上一个结点作树根，森林就变为一棵树。

树的性质

性质一： 非空树中的结点总数等于树中所有结点的度之和加1。
证明

根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个双亲结点，即每个结点与指向它的一个分支结点——对应，因而除了树的根结点之外的结点数等于树中所有结点的分支数（度数），由此可得知树中的结点总数应为所有结点的度之和加1。

性质二： 度为k的非空树的第i层最多有k^i-1个结点（i≥1)。

性质三： 深度为h的k叉树最多有 $ \frac{k^ - 1}{k - 1} $ 个结点

证明：

显然，只有当深度为h的k叉树上的每一层都达到该层最大结点总数时，该树的结点,总数将达到最大，因此，有
k⁰ + k¹ + k² + ... + k^h-1 = $\frac{k^ - 1}{k - 1}$

二叉树

定义

二叉树(Binay Tree)是n(n≥0)个结点的有限集，它或者是空集(a=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。这是一个递归定义。

二叉树的五种基本形态

二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。二叉树的五种基本形态如下图所示。

二叉树与树的关系

(1)二叉树与无序树不同

二叉树中，每个结点最多只能有两棵子树，并且有左右之分。
二叉树并非是树的特殊情形，它们是两种不同的数据结构。

(2)二叉树与度数为2的有序树不同

在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

图(a)，它是一棵度为2的有序树，由于根结点的子树没有左右之分，所以它不是二叉树。另外，具有三个结点的度为2的有序树有一种形态，如图(b)所示。具有三个结点的树有两种形态，如图(b）和(c)所示。具有三个结点的二叉树有五种形态，如图(b)、(d)、(e)、(f)、(g)所示。

二叉树性质

性质一： 二叉树第i(i≥1)层最多有2^i-1个结点。

证明：用数学归纳法

(1)当i=1时，有2^i-1=2⁰=1。因为第1层上只有一个根结点，所以命题成
(2) 假设对所有的j(1≤j<i)命题成立，即第j层上至多有2^j-1个结点。
(3）根据归纳假设，第i-1层上至多有2^i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2x2^i-2=2^i-1个结点，故命题成立。

性质二： 深度为k(k≥1)的二叉树，最多有2^k-1个结点。
证明：

在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为:
2⁰+2¹+…+2^k-1=2^k-1 故命题正确。

性质三： 任意非空二叉树中，若叶结点的数目为n0，度为2的结点数目为n2，则有关系n0=n2 + 1。
证明：

设度为1的结点数目为n1，二叉树的结点总数为n，有n=n0 + n1 + n2
设B表示分支数，具有n个结点的二叉树的分支总数为n-1。则有B=n - 1
而所有这些分支不是来自于度为1的结点就是来自于度为2的结点，即每一个度为1的结点发出一个分支，每一个度为2的结点发出两个分支。于是有B=n₁ +2n₂
联立上面三个等式可以得到n0=n2 +1 故命题正确。

满二叉树

一棵深度为k且有2^k-1个结点的二又树称为满二叉树。

满二叉树的特点：

• (1)每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。满二叉树的结点总数一定是奇数。
• (2)满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且叶结点都在最下一层上。

完全二叉树：

若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

完全二叉树的特点：

• (1)满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
• (2)在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
• (3)在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

性质四： 具有n个结点的完全二叉树的深度为k=[log₂n] + 1或[log₂(n+1)]

证明：

设所求完全二叉树的深度为k。由完全二叉树定义可得:
深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2^k-1-1个结点
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数:
n>2^k-1-1
另一方面，由性质2可得：
n≤2^k - 1
即：2^k-1 - 1 < n ≤ 2^k - 1
由此可推出:2^k-1≤n<2^k，取对数后有:k-1≤log2n<k
又因k-1和k是相邻的两个整数，故有k=[log₂n]+1

性质五： 如果将一棵有n个结点的完全二叉树按层从1开始编号，则对任一编号为i(1≤i≤n)的结点x有:

若i=1，则结点X是根，若i>1，则X的双亲的编号为[i /2]。
若2i>n，则结点X无左孩子(且无右孩子)﹔否则，X的左孩子编号为2i。
若2i+1>n，则结点x无右孩子;否则，X的右孩子的编号为2i+1。