树的基本知识

· · 个人记录

树

定义：

树：树是一个n(n>=0)个结点的有序合集，由n-1条边连接。

性质：

  1. 树是递归定义的。

  2. 一棵树中至少有一个结点。

  3. 除根节点外，其他所有结点都拥有前驱；除叶结点外，其他所有结点都拥有后继。

  4. 树只能有一个前驱，可以有多个后继。

结点：（又称节点）指树中元素。

结点的度：指树中某元素的子树个数。

树的度：指树中最大的结点度。

叶节点：指无子树的结点。

根节点：指无父节点的结点。

深度：指最长父子关系（最大父子关系的长度），根节点深度为1（或 0）。

结点深度：指某结点与子树的最长父子关系（最大父子关系的长度）

高度：指最长父子关系（最大父子关系的长度），叶节点高度为1（或0）。

结点高度：指某结点与子树的最长父子关系（最大父子关系的长度）

二叉树：

定义：任何一个结点最多拥有2个子节点，分别称为这个根的左子树和右子树。

性质：

  1. 二叉树的第i层最多有2^{i-1}个结点

    证明：当i=1时绝对成立；现在假设i-1层时由推断成立，即第i-1层最多有2^(i-2)个结点。根据「二叉树的定义」，则第i层的节点数为i-1层的二倍，即为2^(i-2)*2=2^(i-1)。

  2. 深度为k的二叉树最多有2^{k}-1个结点

    证明：深度相同的两棵二叉树，当每一层节点数为最大时，节点数最多。根据「性质1」可得深度为k的二叉树节点数最多为：
2^0+2^1+2^2+……+2^(k-1)+2^k整合即为：2^k-1

  3. 对于任意一棵二叉树，如果度为0的结点（叶节点）数量为n_{0}，度为2的结点数量为n_{2}，则一定满足n_{0}=n_{2}+1

    证明：因为「二叉树的定义」，所以n=n_0+n_1+n_2（n为结点总数，暂时将此式记为「式1」）
又得知，树中结点总数为孩子结点数+根节点
孩子结点数即为：n_1+2n_2
即n=n_1+2n_2+1（暂时将此式记为「式2」）

根据「式1」与「式2」，我们又双叒叕可以得到：
∵「式1」
∴n_0=n-n_1-n_2
将「式2」代入，得出：
n_0=n_1+2n_2+1-n_1-n_2
   =n_2+1

  4. 具有n个结点的完全二叉树，深度为⌊log_2^n⌋+1 

    证明：设树深度为k，根据完全二叉树的定义（后文有写到），1~(k-1)层一定是满的，所以节点数n>2^(k-1)-1，但n又需满足n<=2^k-1，所以2^(k-1)-1<n<=2^k-1，即为2^(k-1)<=n<2^k
加入log运算后：
k-1<=log2(n)<k，但k是整数，log2(n)是实数，所以k=floor(log2(n)+1)，即为k=⌊log2(n)⌋+1

满二叉树：

每个非叶节点的结点都拥有左子树与右子树，且叶节点都在同一层。简单地说，深度为k且有2^{k}-1个结点。

满二叉树性质：

  1. 每层上的节点数都是最大节点数。

完全二叉树：

深度为k，有n个结点的二叉树当且晋档其每一个结点都与深度为k的满二叉树中从1~n的结点一一对应时。简单地说，编号为i的结点左子树为2i，右子树为2i+1。

二叉树的遍历：

  1. 先序遍历（先根遍历）：（递归定义）根->左子树->右子树

  2. 中序遍历（中根遍历）：（递归定义）左子树->根->右子树

  3. 后序遍历（后根遍历）：（递归定义）左子树->右子树->根

见图片

霍夫曼树（Huffman）：

霍夫曼树（哈夫曼树），又称最优二叉树，用于建造Huffman编码。Huffman编码是一种前缀编码；Huffman编码是建立在Huffman树的基础上进行的，因此为了进行Huffman编码，必须先构建Huffman树；编码的路径长度是每个叶节点到根节点的路径之和；带权路径长度是每个叶节点的路径长度w_{i}之和

构建方法：直接上图，懒得解释

构成Huffman编码后，原本权值高的数编码短；原本权值低的数编码长

树的直径： 树的直径，又称树的最长链，定义为一棵树上最远的两个节点的路径，即树上一条不重复经过某一条边的最长的路径。树的直径也可以代指这条路径的长度。

习题：

树（含盖下面所有题目的题单）

基础二叉树结构练习：P4715 【深基16.例1】淘汰赛

求二叉树的深度：P4913 【深基16.例3】二叉树深度

Huffman：练习题目：P2168 [NOI2015] 荷马史诗

树上搜索：P1364 医院设置

树的遍历：P1305 新二叉树

树的遍历：P1030 [NOIP2001 普及组] 求先序排列

树上距离，LCA（最近公共祖先），树上搜索：P3884 [JLOI2009]二叉树问题

树上搜索（爆料：N%K Problem）：P3915 树的分解

树上搜索：P2052 [NOI2011] 道路修建

树形dp：P1122 最大子树和