Day 7 树笔记(1)

Oishi

2026-07-20 19:58:29

发布于：广东

12阅读

0回复

0点赞

树

树是一种非线性结构，可以有效描述有分支和层次特性的数据集合。
树由 $n ( n≥0 )$ 个结点组成的有限集合中，除根结点以外的其他结点划分为 $m ( m≥0 )$ 个互不相交的有限集 $T_0, T_1, T_2 ··· T_ (m-1)$ ；其中, 每个集合本身又是一棵树，我们称它为根结点的子树。

人话：把根结点和其他结点连接的分支砍掉，剩下几部分的就是子树。

                                A-------------->root根结点
                              /   \
                         _______________
                        |   B   |   C   |
                        |  / \  |  / \  |
             子树1 <----| D   E | F   G |------>子树2
                         ----------------

我们可以把树看成一张族谱以方便理解。

树结点的度：
-该结点拥有的子树数，相当于族谱中某个人拥有的后代数。
-如果某个树结点的度为 $0$ （该成员没有任何后代），那么该结点为叶子结点，否则为分支结点。
-一棵树的度定义为所有结点中的最大值（家族中谁的后代多取谁的值）。

前驱&后继&祖先结点：
-前驱：除根结点外，其余树结点有一个唯一的前驱点，被称作父亲（双亲）。
-后继：每个结点可以有 $0$ 个或多个后继结点（就像一个人有 $0$ 或多个后代）；拥有同一个前驱（拥有同一个父亲）的多个结点叫做兄弟节点。
-祖先结点：沿根结点到某一结点的路径上的所有结点都是这个结点的祖先结点

                                A------------->root 根结点      |1
                              /   \                             |2
                            B       C                           |3  <-高度/深度
                           / \     / \                          |4
                                _______                         |5
     A和B都是D的祖先<-----D   E | F   G |------>F和G是兄弟结点    |6
                         ---    --------

树的存储方法：

方法1：孩子存储法（vector动态扩容）
存储每个结点的孩子编号

const long long N=1e6+10;//数据范围
vector<long long> son[N];
//定义动态数组son存储孩子信息   son[i]存储结点i的孩子
//需要输出 i 的子结点, 直接输出son[i]
/**例:
*son[1] = { 2, 3 }
*son[2] = { 4 }
*son[3] = { 5, 6 }
*son[4] = { 7, 8, 9 }
*···
*/

方法2：父亲存储法
存储每个结点i的父亲

const long long N=1e6+10;
int father[N] = { 0 ,0 ,1 ,1 ,2 ,3 ,3 ,4 ,4 ,4 };//father[i]存储第i个结点的父亲
int value[N] = { 0, 8, 5, 6, 9,  1, 2, 3, 7, 4 };//value[i]存储第i的结点的值