树与二叉树

1.树的基本概念

基本术语

考虑结点K

K的祖先：根A到结点K的唯一路径上的任意结点

子孙：结点B是结点K的祖先,而结点K是结点B的子孙

双亲与孩子：路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子

兄弟：有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟

结点的度：树中一个结点的孩子个数，树中结点的最大度数称为树的度

分支结点（非终端结点）：度大于0的结点

叶子结点（终端结点）：度为0（没有子女结点）的结点

节点的层次从树根开始定义，根节点为第一层。树的高度（深度）是树中节点的最大层数。

路径和路径长度∶树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数

树中的路径从上向下，同一双亲的两个孩子之间不存在路径。

森林∶森林是n棵互不相交的树的集合

只要把树的根结点删去就成了森林

给n棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树

树的性质

1).树中的节点数nnn等于所有节点的度数之和加111。

2).度为mmm的树中第iii层上至多有mi−1m^{i-1}mi−1个节点(i≥1)(i≥1)(i≥1)。

3).高度为hhh的mmm叉树至多有(mh−1)/(m−1)(m^h-1)/(m-1)(mh−1)/(m−1)个节点。

4).具有nnn个节点的mmm叉树的最小高度为⌈logm(n(m−1)+1)⌉\lceil log{_m}{(n(m-1)+1)}\rceil⌈logm​(n(m−1)+1)⌉。由(mh−1)(m−1)≥n\frac{(m^h-1)}{(m-1)}≥n(m−1)(mh−1)​≥n推导出。

总节点数=n0+n1+n2+⋯+nm总节点数=n_0+n_1+n_2+\dots+n_m总节点数=n0​+n1​+n2​+⋯+nm​.

总分支数=1n1+2n2+⋯+mnm总分支数=1n_1+2n_2+\dots+mn_m总分支数=1n1​+2n2​+⋯+mnm​（度为mmm的节点引出mmm条分支）。

总结点数=总分支数+1总结点数=总分支数+1总结点数=总分支数+1.

2.二叉树的概念

二叉树的定义及其主要特征

二叉树与度为2的树：二叉树是概念，度为2的树是实体。

特殊的二叉树

满二叉树

一颗高为h，且含有2h−12^h-12h−1个节点的二叉树称为满二叉树，即树中的每层都含有最多的节点。

对于编号为iii的结点，若有双亲，则其双亲为⌊i/2⌋\lfloor i/2\rfloor⌊i/2⌋，若有左孩子，则左孩子为2i2i2i；若有右孩子，则右孩子为2i+12i+12i+1。

完全二叉树

当且仅当其每个结点都与高度为hhh的满二叉树中编号为[1,n][1,n][1,n]的结点一一对应时，称为完全二叉树。

其特点如下:

1).若i≤⌊n/2⌋i≤\lfloor n/2\rfloori≤⌊n/2⌋，则结点iii为分支结点，否则为叶子结点。

2).若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子，n为偶数n1=1，n为奇数n1=0n为偶数n_1=1，n为奇数n_1=0n为偶数n1​=1，n为奇数n1​=0，由4)可推出。

3).按层序编号后，一旦出现某结点(编号为iii)为叶子结点或只有左孩子，则编号大于iii的结点均为叶子结点。

4).若nnn为奇数，则每个分支结点都有左孩子和右孩子;若nnn为偶数，则编号最大的分支结点（编号为n/2n/2n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。（完全二叉树的性质可以根据结点树确定n1n_1n1​的个数）

二叉排序树

左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字;

左子树和右子树又各是一棵二叉排序树。

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过111。

二叉树的性质

1).非空二叉树上的叶子结点数等于度为222的结点数加111，即n0=n2+1n_0=n_2+1n0​=n2​+1。
n0+n1+n2=n1+2n2+1n_0+n_1+n_2=n_1+2n_2+1n0​+n1​+n2​=n1​+2n2​+1

2).非空二叉树上第kkk层上至多有2k−12^{k-1}2k−1个结点(k≥1)(k≥1)(k≥1)。

3).高度为hhh的二叉树至多有2h−12^h-12h−1个结点(h≥1)(h≥1)(h≥1)。
n=1+2+22+⋯+2h−1n=1+2+2^2+\dots+2^{h-1}n=1+2+22+⋯+2h−1

4).具有nnn个(n>0)(n>0)(n>0)结点的完全二叉树的高度为⌈log2(n+1)⌉或⌈log2n⌉+1\lceil log_2(n+1)\rceil或\lceil log_2n\rceil+1⌈log2​(n+1)⌉或⌈log2​n⌉+1。

从高度为h的树有几个结点出发(mh−1)(m−1)≥n\frac{(m^h-1)}{(m-1)}≥n(m−1)(mh−1)​≥n推导出

二叉树的存储结构

顺序存储

这种存储结构建议从数组下标111开始存储树中的结点，若从数组下标000开始存储，则不满足性质4的描述（计算出其孩子结点在数组中的位置是有偏差)，这是考生在书写程序时容易忽略的。

链式存储

在含有n个结点的二叉链表中,含有n+1个空链域

struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {} 
};

3.二叉树的遍历和线索二叉树

二叉树的遍历

先序遍历

void PreOrder(TreeNode* root, vector& ans) {if (!root)return;ans.push_back(root->val);if (root->left)PreOrder(root->left, ans);if (root->right)PreOrder(root->right, ans);
}

void preorder(TreeNode* root, vector& ans) {stack s;while (root != NULL || !s.empty()) {if (root != NULL) {ans.push_back(root->val);s.push(root);root = root->left;}else {root = s.top(); s.pop();root = root->right;}}
}

中序遍历

void InOrder(TreeNode * root,vector& ans) {if (!root)return;if (root->left)InOrder(root->left,ans);ans.push_back(root->val);if (root->right)InOrder(root->right,ans);
}

void inorder(TreeNode* root, vector& ans) {stack s;while (root!=NULL || !s.empty()) {if (root!=NULL) {//当前节点不是空节点s.push(root);//将当前节点入栈root = root->left;//当前节点指向左儿子}else {//如果当前节点是空节点root = s.top(); s.pop();//从栈中取出一个节点作为当前节点ans.push_back(root->val);//中序遍历root = root->right;//当前节点无左儿子，访问其右儿子}}
}

后序遍历

void PostOrder(TreeNode* root, vector& ans) {if (!root)return;if (root->left)PostOrder(root->left, ans);if (root->right)PostOrder(root->right, ans);ans.push_back(root->val);
}

void postorder(TreeNode* root, vector& ans) {stack s;TreeNode* prev = NULL;while (root != NULL || !s.empty()) {if (root != NULL) {s.push(root);root = root->left;}else {root = s.top(); s.pop();if (root->right == NULL || root->right == prev) {ans.push_back(root->val);prev = root;root = NULL;}else {s.push(root);root = root->right;}}}
}

层次遍历

void LevelOrder(TreeNode* root, vector>& ans) {if (!root)return;//空树退出queue q;q.push(root);while (!q.empty()) {vector temp;int nowsize = q.size();for (int i = 1; i <= nowsize; i++) {TreeNode* u = q.front(); q.pop();temp.push_back(u->val);if (u->left)q.push(u->left);if (u->right)q.push(u->right);}ans.push_back(temp);}
}

由遍历序列确定二叉树

二叉树的先序和中序可以唯一确定一颗二叉树

二叉树的后序和中序可以唯一确定一颗二叉树

线索二叉树

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息
只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。

引入线索二叉树正是为了加快查找结点前驱和后继的速度。

先序线索二叉树

后继节点：

如果有左孩子，则左孩子就是其后继;

如果无左孩子但有右孩子，则右孩子就是其后继;

如果为叶结点，则右链域直接指示了结点的后继。

中序线索二叉树

在中序线索二叉树中找结点后继的规律是：若其右标志为”1“，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。

后续线索二叉树

后继节点：

在后序线索二叉树中找结点的后继较为复杂，可分3种情况:

①若结点x是二叉树的根，则其后继为空;

②若结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲;

③若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

4.树、森林

树的存储结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QPfJEShH-1668563317723)(C:\Users\13645\AppData\Roaming\Typora\typora-user-images\image-20220512200239395.png)]

注意：区别树的顺序存储结构与二叉树的顺序存储结构。

在树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系。

而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。

当然，二叉树属于树，因此二叉树都可以用树的存储结构来存储，但树却不都能用二叉树的存储结构来存储。

1.双亲表示法

这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4rPlwDhf-1668563317724)(C:\Users\13645\AppData\Roaming\Typora\typora-user-images\image-20220512200334586.png)]

该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时需要遍历整个结构。

2.孩子表示法

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时的结点就有n个孩子链表（叶子结点的孩子链表为空表)。
这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ptnwtJQd-1668563317725)(C:\Users\13645\AppData\Roaming\Typora\typora-user-images\image-20220512201133567.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NSGbyhkP-1668563317725)(C:\Users\13645\AppData\Roaming\Typora\typora-user-images\image-20220512201052192.png)]

3.孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。

孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点)。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZecrRWbj-1668563317726)(C:\Users\13645\AppData\Roaming\Typora\typora-user-images\image-20220512201541431.png)]

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等,但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。

树、森林与而叉树的转化

将森林转换为二叉树的规则与树类似。

先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树必空，将所有森林转化为二叉树的根顺序排列，再虚拟一个根与所有根节点相连再转换一次，就可以将森林转换为二叉树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Amam0c7J-1668563317726)(C:\Users\13645\AppData\Roaming\Typora\typora-user-images\image-20220512201842242.png)]

树、森林的遍历

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式:

1）先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。

2）后根遍历。若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

森林的两种遍历方法。

1）先序遍历森林。若森林为非空，则按如下规则进行遍历:
访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林。
先序遍历除去第一棵树之后剩余的树构成的森林。

2）中序遍历森林。森林为非空时，按如下规则进行遍历:.

中序遍历森林中第一棵树的根结点的子树森林。

访问第一棵树的根结点。

中序遍历除去第一棵树之后剩余的树构成的森林。

5.树与二叉树的应用

哈夫曼树和哈夫曼编码

带权路径长度

到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为

WPL=∑i=1nwiliWPL=\displaystyle \sum^{n}_{i=1}{w_il_i}WPL=i=1∑n​wi​li​

式中wi代表第i个叶结点所带的权值，li代表该叶节点到根结点的路径长度式中w_i代表第i个叶结点所带的权值，l_i代表该叶节点到根结点的路径长度式中wi​代表第i个叶结点所带的权值，li​代表该叶节点到根结点的路径长度

哈夫曼树

在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树。

给定nnn个权值分别为wi,w2,...,wnw_i,w_2,...,w_nwi​,w2​,...,wn​的结点，构造哈夫曼树的算法描述如下:

1).将这nnn个结点分别作为nnn棵仅含一个结点的二叉树，构成森林FFF。
2).构造一个新结点，从FFF中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3).从FFF中删除刚才选出的两棵树，同时将新得到的树加入FFF中。

4).重复步骤2)和3)，直至FFF中只剩下一棵树为止。

哈夫曼树的特点:

1).每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。

2).构造过程中共新建了n−1n-1n−1个结点（双分支结点)，因此哈夫曼树的结点总数为2n−12n-12n−1。

3).每次构造都选择222棵树作为新结点的孩子，因此哈夫曼树中不存在度为111的结点。

哈夫曼编码

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QEkFxyLj-1668563317727)(C:\Users\13645\AppData\Roaming\Typora\typora-user-images\image-20220512212846276.png)]

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

注意：

000和111究竟是表示左子树还是右子树没有明确规定。

左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度WPLWPLWPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但WPLWPLWPL必然相同且是最优的。

并查集

int father[N];//father[i]的值是节点i的父节点的标号
void init_set() {for (int i = 1; i <= N; i++) {father[i] = i;//每个节点的父亲是他自己}
}
int find_fa(int x) {//非递归版if(x!=father[x])father[x]=find_fa(father[x]);return father[x];
}
//合并
u = find_set(u);
v = find_set(v);
if (u != v) {//u和v不在一个集合内father[u] = v;//将u合并到v去
}