什么是树形结构？

在现实生活中有很多体现树的逻辑的例子，比如企业里的职级关系，就是一个树。

树的定义

对于树的定义还需要注意两点：

1.n>0 时，根结点是唯一的，不可能存在多个根结点。

​ 2.m>0 时，子树的个数没有限制，但它们一定是互不相交的。如图中的两个结构就不符合树的定义，因为它们都有相交的子树。

树的相关概念

根结点

例：A

分支结点：度不为 0 的结点

例：A B D F

叶子：度为 0 的结点

例：E J G H I C

孩子：一个结点子树的根

例：G H I 是 D 的孩子

双亲：如果 B 是 A 的孩子，那么 A 是 B 的双亲

例：D 是 G H I 的双亲

兄弟：同一双亲的孩子间互称兄弟

例：G H I 互为兄弟

祖先：从根到某个结点所经过的分支上的所有结点称为该结点的祖先

例：J 的祖先有：A B F

子孙：某结点子树中所有结点都是该结点的子孙 例：B 的子孙有 E F J

**度指的是一个结点的子结点的数量，一 棵树的度是指树中最大的结点度**

例：结点 B 的度为 2，结点 D 的度为 3，树的度为 3。

课堂例题找树根和孩子

题目解析：

1.tr[y] = x 表示 y 的双亲结点为 x。

2.由于结点编号未必连续，因此每出现一个结点都需要标记。

3.mp[x] 记录 x 的子结点数量。

参考程序：

#include <iostream>#include <map>using namespace std;const int N = 110;int n, m;int tr[N];bool book[N];map<int, int> mp;int main() {    cin >> n >> m;    while(m--){        int x, y;        cin >> x >> y;        tr[y] = x;        mp[x]++;        book[x] = true;        book[y] = true;    }    for(int i = 1;  i < N; i++){        if(tr[i] == 0 && book[i]){            cout << i << endl;            break;        }    }       int cnt = -1, p = -1;    for(auto x: mp){        if(x.second > cnt){            cnt = x.second;            p = x.first;        }    }    cout << p << endl;    for(int i = 1; i < N; i++)        if(tr[i] == p)            cout << i << " ";    return 0;}

题目解析：

首先要对建树的过程有一个了解。对于当前被处理的单词和当前树：在根结点的子结点中找单词的第一位字母，若存在则进而在该结点的子结点中寻找第二位……

如此下去直到单词结束，即不需要在该树中添加结点；或单词的第 n 位不能被找到，即将单词的第 n 位及其后的字母依次加入单词查找树中去。

**但，本问题只是问你结点总数，而非建树方案，且有 32K 文件，可以考虑能不能不通过建树就直接算出结点数？**

为了说明问题的本质，我们给出一个定义：一个单词相对于另一个单词的差：设单词 2 的长度为 L，且与单词 1 从第 N 位开始不一致，则说单词 2 相对于单词 1 的差为 L-N+1，这是描述单词相似程度的量。

可见，将一个单词加入单词树的时候，须加入的结点数等于该单词树中与已有单词的差的最小值。

单词的字典顺序排列后的序列则具有类似的特性，即在一个字典顺序序列中，第 m 个单词相对于第 m-1 个单词的差必定是它对于前 m-1 个单词的差中最小的。于是，得出建树的等效算法：

① 读入数据；

② 对单词列表进行字典顺序排序；

③ 依次计算每个单词对前一单词的差，并把差累加起来。注意：第一个单词相对于空的差为该单词的长度；

④ 累加和再加上1（根结点），输出结果。

就给定的样例，按照这个算法求结点数的过程如下表：

数据结构：

先确定 32K（32*1024=32768字节）的文件最多有多少单词和字母。当然应该尽可能地存放较短的单词。

因为单词不重复，所以长度为 1 的单词（单个字母）最多26个；

长度为2的单词最多为26*26=676个；因为每个单词后都要一个换行符（换行符在计算机中占 2 个字节），所以总共已经占用的空间为：（1+2）*26+（2+2）* 676=2782 字节；

剩余字节（32768-2782=29986字节）分配给长度为 3 的单词（长度为 3 的单词最多有 26*26*26=17576个）有 29986/(3+2）≈ 5997。

所以单词数量最多为 26+676+5997=6699。

定义一个数组：string words[7000]；把所有单词连续存放起来，用选 sort 进行排序。

参考程序：

#include <iostream>#include <string>#include <algorithm>using namespace std;string words[7000];int n = 1;int main() {    while(cin >> words[n++]);    n--;    sort(words + 1, words + n + 1);    int res = words[1].size();    for(int i = 2; i <= n; i++){        int j = 0;        while(j < words[i - 1].size()){            if(words[i][j] != words[i - 1][j])                break;            j++;        }        res += words[i].size() - j;    }    cout << res + 1 << endl;    return 0;}