4. 第五章 串

4.1 字符串

串：又称字符串，是由零个或多个字符组成的有限序列。

字符串通常用双引号括起来，例如S=“abcdef”，S为字符串的名字，双引号里面的内容为字符串的值。

串长：串中字符的个数，例如S的串长为6。

空串：零个字符的串，串长为0。

子串：串中任意个连续的字符组成的子序列，称为该串的子串，原串称为子串的主串。例如T=“cde”，T是S的子串。子串在主串中的位置，用子串的第一个字符在主串中出

现的位置表示。T在S中的位置为3，如图所示。

注意：空格也算一个字符，例如X=“abc fg”，X的串长为6。

空格串：全部由空格组成的串为空格串。

注意：空格串不是空串。

1）字符串的顺序存储

顺序存储是用一段连续的空间存储字符串。可以预先分配一个固定长度Maxsize的空间，在这个空间中存储字符串。

顺序存储又有3种方式。

• （1）以'\0'表示字符串结束：在C、C++、Java语言中，通常用'\0'表示字符串结束，'\0'不算在字符串长度内，如图所示。

• 
• 这样做有一个问题：如果想知道串的长度，需要从头到尾遍历一遍，如果经常需要用到串的长度，每次遍历一遍复杂性较高，因此可以考虑将字符串的长度存储起来以使用。

• （2）在0空间存储字符串的长度：下标为0的空间不使用，因此可以预先分配Maxsize+1的空间，在下标为0的空间中存储字符串长度，如图所示。

• （3）结构体变量存储字符串的长度
• 静态分配空间的方法

typedef struct {
    char ch[Maxsize]; //字符型数组
    int length; //字符串的长度
}SString；

例如，字符串S=“abdefgc”，其存储结构如图所示。

这样做也有一个问题，串的运算如合并、插入、替换等操作，容易超过最大长度，出现溢出。为了解决这个问题，可以采用动态分配空间的方法，其结构体定义如下。

typedef struct {
    char *ch; //指向字符串指针
    int length; //字符串的长度
}SString；

例如，字符串S=“abcdef”，其存储结构如图4-5所示。

2）字符串的链式存储

顺序存储的串在插入和删除操作时，需要移动大量元素，因此也可以采用链表的形式存储

单链表存储字符串时，虽然插入和删除非常容易，但是这样做也有一个问题：一个节点只存储一个字符，如果需要存储的字符特别多，会浪费很多空间。因此也可以考虑一个节点存储多个字符的形式，例如一个节点存储3个字符，最后一个节点不够3个时用#代替，如图所示。

4.2 模式匹配BF算法

模式匹配：子串的定位运算称为串的模式匹配或串匹配。

假设有两个串S、T，设S为主串，也称正文串；T为子串，也称模式。在主串S中查找与模式T相匹配的子串，如果查找成功，返回匹配的子串第一个字符在主串中的位置。最笨的办法就是穷举所有S的所有子串，判断是否与T匹配，该算法称为BF（BruteForce[1]）算法。

算法步骤

1）从S第1个字符开始，与T第1个字符比较，如果相等，继续比较下一个字符，否则转向下一步；

2）从S第2个字符开始，与T第1个字符比较，如果相等，继续比较下一个字符，否则转向下一步；

3）从S第3个字符开始，与T第1个字符比较，如果相等，继续比较下一个字符，否则转向下一步；

……

4）如果T比较完毕，则返回T在S中第一个字符出现的位置；

5）如果S比较完毕，则返回0，说明T在S中未出现。

完美图解

例如：S=“abaabaabeca”，T=“abaabe”，求子串T在主串S中的位置。

1）从S第1个字符开始：i=1，j=1，如图1所示。比较两个字符是否相等，如果相等，则i++，j++；如果不等，则转向下一步，如图2所示。

2）i回退到i−j+2的位置，j回退到1的位置，即i−j+2=6−6+2=2，即i从S第2个字符开始，j从T第1个字符开始。比较两个字符是否相等，如果相等，则i++，j++；如果不等则转向下一步，如图所示。

解释：为什么i要回退到i−j+2的位置呢？如果本趟开始位置是a，那么下一趟开始的位置就是a的下一个字符b的位置，这个位置正好是i−j+2，如图所示。

3）i回退到i−j+2的位置，i=2−1+2=3，即从S第3个字符开始，j=1，如图1所示。比较两个字符是否相等，如果相等，则i++，j++；如果不等，则转向下一步，如图2所示。

4）i回退到i−j+2的位置，i=4−2+2=4，即从S第4个字符开始，j=1，如图1所示。比较两个字符是否相等，如果相等，则i++，j++；此时T比较完了，执行下一步，如图2所示。

5）T比较完毕，返回子串T在主串S中第1个字符出现的位置，即i−m=10−6=4，m为T的长度。

因为串的模式匹配没有插入、合并等操作，不会发生溢出，因此可以采用第2种字符串顺序存储方法，用0空间存储字符串长度。例如，T的顺序存储方式如图所示。

算法复杂度分析

设S、T串的长度分别为n、m，则BF算法的时间复杂度分为以下两种情况。

（1）最好情况

在最好情况下，每一次匹配都在第一次比较时发现不等，如图4-17～图4-20所示。

假设第i次匹配成功，则前i−1次匹配都进行了1次比较，一共i−1次，第i次匹配成功时进行了m次比较，则总的比较次数为i−1+m。在匹配成功的情况下，最多需要n−m+1次匹配，即模式串正好在主串的最后端。假设每一次匹配成功的概率均等，概率pi =1/(n−m+1)，则在最好情况下，匹配成功的平均比较次数为：

最好情况下的平均时间复杂度为O(n+m)。

（2）最坏情况

在最坏情况下，每一次匹配都比较到T的最后一个字符发现不等，回退重新开始，这样每次匹配都需要比较m次，如图4-21～图4-23所示。

假设第i次匹配成功，则前i−1次匹配都进行了m次比较，第i次匹配成功时也进行m次比较，则总的比较次数为i×m。在匹配成功的情况下，最多需要n−m+1次匹配，即模式串正好在主串的最后端。假设每一次匹配成功的概率均等，概率pi=1/(n−m+1)，则在最坏情况下，匹配成功的平均比较次数为：

最坏情况下的平均时间复杂度为O(n×m)。

4.3 模式匹配KMP算法

例如：S=“abaabaabeca”，T=“abaabe”，求子串T在主串S中的位置。

完全没必要从S的每一个字符开始穷举每一种情况

从S第1个字符开始：i=1，j=1，如图4-24所示。比较两个字符是否相等，如果相等，则i++，j++；第一次匹配不相等，如图4-25所示。

按照BF算法，如果不等，则i回退到i−j+2，j回退到1，即i=2，j=1，如图4-26所示。

其实i不用回退，让j回退到第3个位置，接着比较即可，如图4-27所示。

是不是像T向右滑动了一段距离？

为什么可以这样？为什么让j回退到第3个位置？而不是第2个？或第4个？

因为T串中开头的两个字符和i指向的字符前面的两个字符一模一样，如图4-28所示。这样j就可以回退到第3个位置继续比较了，因为前面两个字符已经相等了，如图4-29所

示。

那怎么知道T中开头的两个字符和i指向的字符前面的两个字符一模一样？难道还要比较？我们发现i指向的字符前面的两个字符和T中j指向的字符前面两个字符一模一样，因为它们一直相等， i++、j++才会走到当前的位置，如图4-30所示。

也就是说，我们不必判断开头的两个字母和i指向的字符前面的两个字符是否一样，只需要在T本身比较就可以了。假设T中当前j指向的字符前面的所有字符为T′，只需要比较T′的前缀和T′的后缀即可，如图4-31所示。

前缀后缀next[ ]

前缀是从前向后取若干个字符，后缀是从后向前取若干个字符。注意：前缀和后缀不可以取字符串本身。如果串的长度为n，前缀和后缀长度最多达到n−1，如图4-32所示。

判断T′=“abaab”的前缀和后缀是否相等，并找相等前缀后缀的最大长度。

1）长度为1：前缀“a”，后缀“b”，不等　 ×

2）长度为2：前缀“ab”，后缀“ab”，相等　 √

3）长度为3：前缀“aba”，后缀“aab”，不等　×

4）长度为4：前缀“abaa”，后缀“baab”，不等　×

相等前缀后缀的最大长度为l=2，则j就可以回退到第l+1=3个位置继续比较了。因此，当i、j指向的字符不等时，只需要求出T′的相等前缀后缀的最大长度l，i不变，j回退到l+1的位置继续比较即可，如图4-33和图4-34所示。

现在可以写出通用公式，next[j]表示j需要回退的位置， ，则：

根据公式很容易求出T=“abaabe”的next[]数组，如图4-35所示。

解释如下。

1）j=1：根据公式next[1]=0。

2）j=2：T′=“a”，没有前缀和后缀，next[2]=1。

3）j=3：T′=“ab”，前缀为“a”，后缀为“b”，不等，next[3]=1。

4）j=4：T′=“abc”，前缀为“a”，后缀为“a”，相等且l=1；前缀为“ab”，后缀为“ba”，

不等；因此next[4]=l+1=2。

5）j=5：T′=“abaa”，前缀为“a”，后缀为“a”，相等且l=1；前缀为“ab”，后缀为“aa”，不等；前缀为“aba”，后缀为“baa”，不等；因此next[5]=l+1=2。j=6：T′=“abaab”，前缀为“a”，后缀为“a”，相等且l=1；前缀为“ab”，后缀为“ab”，相等且l=2；前缀为“aba”，后缀为“aab”，不等；前缀为“abaa”，后缀为“baab”，不等；取最大长度2，因此next[6]=l+1=3。

可以用动态规划递推

首先大胆假设，我们已经知道了 那么T′的相等前缀、后缀最大长度为k−1，如图4-36所示。

那么next[j+1]=?

考查以下两种情况。

1） ：那么 ，即相等前缀和后缀的长度比 多1，如图4-37所示。

2） ：当两者不相等时，我们又开始了这两个串的模式匹配，回退找 的位置，比较 与 是否相等，如图4-38所示。

如果 与 相等，则 。

如果 与 不相等，则继续回退找 ，比较 与 是否相等，如图4-39所示。

如果 与 相等，则 。

如果 与 不相等，继续向前找，直到找到next[1]=0停止。

求解求出T=“abaabe”的next[ ]数组

解释如下。

1）初始化时next[1]=0，j=1，k=0，进入循环，判断满足k==0，则执行代码next[++j]=++k，即next[2]=1，此时j=2、k=1。

2）进入循环，判断满足T[j]==T[k]，T[2]≠T[1]，则执行代码k=next[k]，即k=next[1]=0，此时j=2、k=0。

3）进入循环，判断满足k==0，则执行代码next[++j]=++k，即next[3]=1，此时j=3、k=1。

4）进入循环，判断满足T[j]==T[k]，T[3]=T[1]，则执行代码next[++j]=++k，即next[4]=2，此时j=4、k=2。

5）进入循环，判断满足T[j]==T[k]，T[4]≠T[2]，则执行代码k=next[k]，即k=next[2]=1，此时j=4、k=1。

6）进入循环，判断满足T[j]==T[k]，T[4]=T[1]，则执行代码next[++j]=++k，即next[5]=2，此时j=5、k=2。

7）进入循环，判断满足T[j]==T[k]，T[5]=T[2]，则执行代码next[++j]=++k，即next[6]=3，此时j=6、k=3。

8）j=T[0]，循环结束。

有了next[ ]数组，就很容易进行模式匹配了，当S[i]≠T[j]时，i不动，j回退到next[ j ]的位置继续比较即可。

算法复杂度分析

设S、T串的长度分别为n、m。KMP算法的特点是：i不回退，当S[i]≠T[j]时，j回退到next[j]，重新开始比较。最坏情况下扫描整个S串，其时间复杂度为O(n)。计算next[]数

组需要扫描整个T串，其时间复杂度为O(m)，因此总的时间复杂度为O(n+m)。

需要注意的是，尽管BF算法最坏情况下时间复杂度为O(n×m)，KMP算法的时间复杂度为O(n+m)。但是在实际运用中，BF算法的时间复杂度一般为O(n+m)，因此仍然有很多

地方用BF算法进行模式匹配。只有在主串和子串有很多部分匹配的情况下，KMP才显得更优越。

4.4 改进的KMP算法

在KMP算法中， 求解非常方便、迅速，但是也有一个问题：当 时，j回退到 ，然后 与 比较。这样的确没错，但是如果 ，这次比较就没必要了，因为刚才就是因为 才回退的，那么肯定 ，完全没必要再比了，如图4-41所示。

再向前回退，找下一个位置 ，继续比较就可以了。当 时，本来应该j回退到 ， 与 比较。但是如果 ，则不需要比较，继续回退到下一个位置 ，减少了一次无效比较，如图4-42所示。

算法复杂度分析

设S、T的长度分别为n、m。改进的KMP算法只是在求解next[]从常数上的改进，并没

有降阶，因此其时间复杂度仍为O(n+m)。

3种算法的运行结果比较如下。

S：　a　a　b　a　a　a　b　a　a　a　a　b　e　a

T：　a　a　a　a　b

BF算法运行结果：

一共比较了21次。主串和子串在第8个字符处首次匹配。

KMP算法运行结果：

-----next[]-------

0　1　2　3　4

一共比较了19次。主串和子串在第8个字符处首次匹配。

改进的KMP算法运行结果：

-----next[]-------

0　0　0　0　4

一共比较了14次。主串和子串在第8个字符处首次匹配。

4.5 字符串小结

串解题时需要注意几个问题。

1）空格也算一个字符。空串是指没有任何字符，空格串不是空串。

2）串中位序和下标之间的关系。如果下标从0开始，则第i个字符的下标为i−1。

3）充分理解KMP算法中的next[]求解方法。

4）熟练利用字符串模式匹配解决实际问题。

5. 数组与广义表

5.1 数组的顺序存储

数组是由相同类型的数据元素构成的有限集合。

一维数组可以看作一个线性表，如图所示。

二维数组也可以看作一个线性表 ，只不过每一个数据元素 也是一个线性表，如图所示。

于是，二维数组也可以看作一个线性表 ，只不过每一个数据元素 也是一个线性表，如图所示。

数组一般采用顺序存储结构，因为存储单元是一维的，而数组可以是多维的，如何用一组连续的存储单元来存储多维数组呢？以二维数组为例，可以按行序存储，即先存第一行，再存第二行……也可以按列序存储，先存第一列，再存第二列……现在比较流行的C语言，Java都是按行序存储的。

1)按行序存储

如果按行序存储，怎么找到 的存储位置呢？

先看看存储 之前，前面已经存储了多少个元素，如图所示。

从图可以看出，在 之前一共有i×n+j个元素，如果每个元素占用L字节，那么共需要(i×n+j)×L字节，只需要用基地址加上这些字节就可以得到 的存储地址了。按行序存储， 的存储地址为：

表示第一个元素的存储地址，即基地址， 表示 的存储地址。

2)按列序存储

如果按列序存储，怎么找到 的存储位置呢？

先看看存储 之前，前面已经存储了多少个元素，如图所示。

从图可以看出，在 之前一共有j×m+i个元素，如果每个元素占用L字节，那么共需要(j×m+i)×L字节，只需要用基地址加上这些字节就可以得到 的存储地址了。按列序存储， 的存储地址为：

表示第一个元素的存储地址，即基地址， 表示aij的存储地址。

注意：如果二维数组的下标是从1开始的，那么情形就变了。

先看看存储 之前，前面已经存储了多少个元素，如图所示。

从图可以看出，行数和个数都少1，在aij之前一共有(i−1)×n+j−1个元素，如果每个元素占用L字节，那么共需要((i−1)×n+j−1)×L字节，只需要用基地址加上这些字节就可以得到 的存储地址了。如果二维数组下标从1开始，按行序存储， 的存储地址为：

存储地址计算秘籍：

的存储地址等于第一个元素的存储地址，加上前面的元素个数乘以每个元素占用的字节数。计算公式为：

5.2 特殊矩阵的压缩存储

在很多科学工程计算问题中，经常遇到一些特殊的矩阵，这些矩阵的很多值是相同的，有的很多元素是0，为了节省空间，可以对这类矩阵进行压缩存储。

什么是压缩存储？给多个相同的元素分配一个存储空间，元素为0的不分配空间。

什么样的矩阵能够压缩？一些特殊矩阵，如对称矩阵、三角矩阵、对角矩阵、稀疏矩阵等。

什么叫稀疏矩阵？矩阵中非零元素的个数较少，怎样才算是较少呢？一般认为非零元素个数小于5%的矩阵为稀疏矩阵。

5.2.1 对称矩阵

对称矩阵比较特殊，其数据元素沿着对角线对称，即：

那么，因为上三角和下三角是一样的，因此只存储其中的一个就可以了。如果用一维数组存储下三角，则只需要n(n+1)/2个空间，比全部存储需要n^2个空间少了很多。

如果按行序存储下三角，那么怎么找到aij的存储位置呢？

先看看存储下三角中的 之前，前面已经存储了多少个元素，如图所示。

如果将对称矩阵的下三角（i>= j）存储在一维数组s[ ]中，那么下三角中 的下标就是i(i−1)/2+j−1，如图所示。

而上三角的元素（i<j），根据对称性， ，可以直接读取下三角中的 ，因此按行序存储下三角时， 的下标为：

存储下标计算秘籍：如果用一维数组s[ ]存储（下标从0开始），则 的存储下标k等于 前面的元素个数。

如果一维数组的下标从1开始呢？——公式后面再加1就行了。上面的公式是计算一维数组存储的下标，如果给了基地址（a11的存储地址），那么 的存储地址为：

5.2.2 三角矩阵

三角矩阵比较特殊，分为下三角矩阵和上三角矩阵，下三角矩阵是指矩阵的下三角有数据，而其余的都是常数c或者为0，如图5-11所示。上三角矩阵也是如此，如图所示。

在下三角矩阵存储时，只需要存储其下三角中的元素，最后一个空间存储常数c即可。如果上面全为0，则不需要存储；下三角也是如此。

三角矩阵如果按行序存储，怎么找到 的存储位置呢？

先看看存储 之前，前面已经存储了多少个元素，如图所示。

如果一维数组的下标从零开始，那么下三角中 的下标就是i(i−1)/2+j−1。而上三角的元素因为全是常数c或者为0，最后一个空间（下标为n(n+1)/2）存储常数c即可，如果是0，则不需要存储。因此下三角矩阵按行序存储时， 的下标为：

上三角矩阵如果按行序存储，怎么找到aij的存储位置呢？

先看看存储 之前，前面已经存储了多少个元素，如图所示。

如果一维数组的下标从0开始，那么上三角中 的下标就是(i−1)(2n−i+2)/2+j−i。而下三角的元素全是常数c或者为0，最后一个空间（下标为n(n+1)/2）存储常数c即可。因此上三角矩阵按行序存储时， 的下标为：

5.2.3 对角矩阵

对角矩阵又称为带状矩阵，是指在n×n的矩阵中非零元素集中在主对角线及其两侧，共L（奇数）条对角线的带状区域内，称为L对角矩阵，如图所示。

很明显，L对角矩阵的带宽为L，半带宽d=(L−1)/2。例如，5对角矩阵的半带宽d=2。当|i−j| d时， ≠0，为对角矩阵的带状区域元素。当|i−j|>d时， =0，为对角矩阵的带状区域之外的元素。

1）L对角矩阵非零元素个数

L对角矩阵一共有多少个非零元素呢？

首先将每一行以对角线为中心进行补零，让每一行都达到L个元素，如图所示。一共补了多少个零呢？第一行补d个0，第二行补d−1个0左上角补零个数为d (d+1)/2。同理，右下角补零个数也为d(d+1)/2，总的补零个数为d(d+1)。那么每行按L个元素计算，再减去补零元素个数即可，即带状区域元素个数为L×n−d(d+1)。因为d=(L−1)/2，即L=2d+1，所以带状区域元素个数也可以表达为(2d+1)×n−d(d+1)。

2）按行序存储

补零后每行都有L个元素，需要L×n个空间。为了节省空间，第一行前面和最后一行后面的d个0可以不存储，“掐头去尾”，需要L×n−2d个空间。如图所示，阴影部分就是要存储的元素。

如果按行序，用一维数组s[]（下标从0开始）存储上图中的5对角矩阵，如下图所示。

怎么找到 的存储位置呢？

首先找到 的存储位置，因为 是对角线上的元素，以对角线为中心，左右两侧都是d个元素，如图5-20所示。 之前有i−1行，每行L个元素， 所在行左侧有d个元素，因此 之前有(i−1)×L+d个元素。因为第一行前面的d个0“掐头去尾”没有存储，所以 之前有(i−1)×L个元素。 的存储位置为：(i−1)×L。而 和 相差j−i个元素，也就说， 的存储位置为：(i−1)×L+j−i。

在上图中， 在 的右侧（i<j），它们之间相差j−i个元素。如果 在 的左侧（i>j）呢？它们之间相差i−j个元素。只需要计算出 的存储位置，减去它们之间的差值就可以了。即 的存储位置为(i−1)×L−(i−j)=(i−1)×L+j−i。也就是说 在 的左侧或右侧，存储位置计算公式是一样的。

公式总结

按行序，用一维数组（下标从0开始）存储L对角矩阵，aij的存储位置为：

3对角矩阵中 的存储位置为k=3(i−1)+j−i=2i+j−3。

5对角矩阵中 的存储位置为k=5(i−1)+j−i=4i+j−5。

如果一维数组的下标从1开始，公式后面再加1即可。

3）按对角线存储

对角矩阵还有一种按对角线的顺序存储方式，如图所示。

即对角线作为0行，左侧分别为1, 2, …, d行，右侧分别为−1, −2, …, −d行。相当于行转换为i′=i−j，列值j不变，把n×n的L对角矩阵转换为L×n的矩阵，如图5-22所示。在图中，（a）矩阵中的 对应（b）矩阵中的 ，其中 。

在图（b）所示的矩阵中，将其他位置补零，如图5-23所示。用一维数组s[ ]（下标从0开始）按行序存储，仍然采用“掐头去尾”，第一行前面和最后一行后面的d个0不存储，如图5-24所示。

怎么找到 的存储位置呢？

首先看n×n的L对角矩阵按对角线转换后的L×n的矩阵，如图5-25所示。 之前有 行，每行有n个元素， 所在行左侧有j−1个元素，因此 之前有 个元素。因为第一行前面的d个0“掐头去尾”没有存储，所以 之前有 个元素。 的存储位置为： 。

如果用一维数组（下标从0开始）按行序存储， 的下标为：

又因为 ，因此对角矩阵中的 下标为：

公式总结

按对角线存储，对角矩阵中的 下标为：

5.2.4 稀疏矩阵

稀疏矩阵是指非零元素个数较少，且分布没有规律可言，

那么少到什么程度才算稀疏呢？

一般认为非零元素小于5%时，属于稀疏矩阵。当然也没那么绝对，只要非零元素个数远远小于矩阵元素个数，就可以认为是稀疏矩阵，如图所示。

稀疏矩阵如何存储呢？

为了节省空间，只需要记录每个非零元素的行、列和数值即可，这就是三元组存储法，如图所示。

5.3 广义表

广义表是线性表的推广，也称为列表。它是 个表元素组成的有限序列，记作 。 是表名， 是表元素，它可以是表（称为子表），也可以是数据元素(称为原子)。 为表的长度， 的广义表为空表。

广义表最常见的操作就是求表头和表尾。

表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表。

表尾GetTail(L)：删除表头元素后余下的元素所构成的表。表尾一定是一个表。

例如， ，表长为 ，表头为 ，表尾为 ，如图所示。

5.4 数组与广义表小结

虽然矩阵压缩有多种，但存储地址计算有一个通用公式。

存储地址计算秘籍： 的存储地址等于第一个元素的存储地址，加上前面的元素个数乘以每个元素占用的字节数。计算公式为：

:表示第一个元素的存储地址，即基地址， 表示 的存储地址。

存储下标计算秘籍：如果用一维数组s[ ]存储（下标从0开始），则aij的存储下标k等于 前面的元素个数。计算公式为：

只需要掌握这两个计算秘籍，结合画图，很快就可以计算出来。

6. 第四章：树

6.1 树的基本概念

6.1.1 树是递归定义的结构

树（tree）是n（n>=0）个节点的有限集合，当n=0时，为空树；n>0时，为非空树。任意一棵非空树，满足以下两个条件：

1）有且仅有一个称为根的节点；

2）除根节点以外，其余节点可分为m（m＞0）个互不相交的有限集 ，其中每一个集合本身又是一棵树，并且称为根的子树（subtree）。

该定义是从集合论的角度给出的树的递归定义，即把树的节点看作一个集合。除了树根以外，其余节点分为m个互不相交的集合，每一个集合又是一棵树。

6.1.2 结点

• 根节点：树只有一个根结点
• 结点的度：结点拥有的子树的数量

• 度为0：叶子结点或者终端结点
• 度不为0：分支结点或者非终端结点
• 分支结点除去根结点也称为内部结点

6.1.3 树的度：树中所有结点的度数的最大值

6.1.4 结点关系

• 祖先结点

• 根结点到该结点的唯一路径的任意结点

• 子孙结点

• 节点的子树中的所有节点都称为该节点的子孙。

• 双亲结点

• 根结点到该结点的唯一路径上最接近该结点的结点

• 孩子结点

• 节点的子树的根称为该节点的孩子

• 兄弟结点

• 有相同双亲结点的结点

6.1.5 层次，高度，深度，树的高度

• 层次：根为第一层，它的孩子为第二层，以此类推
• 结点的深度：根结点开始自顶向下累加
• 结点的高度：叶节点开始自底向上累加
• 树的高度（深度）：树中结点的最大层数

6.1.6 树的性质

有序树——节点的各子树从左至右有序，不能互换位置。

无序树——节点各子树可互换位置。

森林——由m（m>=0）棵不相交的树组成的集合。

• 1.树中的结点数等于所有结点的度数加1。

• 证明：不难想象，除根结点以外，每个结点有且仅有一个指向它的前驱结点。也就是说每个结点和指向它的分支一一对应。假设树中一共有b个分支，那么除了根结点，整个树就包含有b个结点，所以整个树的结点数就是这b个结点加上根结点，设为n，则n=b+1。而分支数b也就是所有结点的度数，证毕。

• 2.度为m的树中第i层上至多有m^(i−1)个结点（i≥1）。

• 证明：（数学归纳法）首先考虑i=1的情况：第一层只有根结点，即一个结点，i=1带入式子满足。假设第i-1层满足这个性质，第i-1层最多有m^(i-2)个结点。..........i-1层………又因为树的度为m,所以对于第i-1层的每个结点，最多有m个孩子结点。所以第i层的结点数最多是i-1层的m倍，所以第i层上最多有m^(i-1)个结点。

• 3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点
• 4.具有n个结点的m叉树的最小高度为