本文包含树的定义,树的存储,树的遍历(包括定义,求法).
基础
-
定义
我们把 \(n\) 个点, \(n-1\) 条边的图称为树.
-
特别情况
对于树,存在部分情况,使其有着特殊的性质.
链:每个点只会链接一条边,我们称为链.
菊花图:点 \(u\) ,如果剩余的点都与 \(u\) 相连,我们称为菊花图.
二叉树:对于每一个节点,最多只有两个儿子,我们称为二叉树.又可以根据儿子的分布情况再次细分.等到后面再来介绍.
-
存储
- 记录父亲,适合底部到顶部,几乎不使用.因为可以使用的信息太少了.
- 记录与其相连的节点.一般用链式前向星,有O2也可以vector
链式前向星不会的可以看这篇教程
-
遍历
遍历分为先序,中序和后序.
注:这TM是二叉树,别搞混了!!!
先序:按照根,左,右来遍历.
中序:左,根,右
后序:左,右,根
还原: 根据这些遍历方式,我们可以通过遍历顺序推出原来的树.中序+前后序任意一个即可.前序+后序是不可以的!!!
我们令顶点为 \(root\). 可以发现,前序的第一个是 \(root\),后序最后一个是 \(root\).中序 \(root\) 在中间部分,左边为左儿子,右边为右儿子.我们先确定\(root\),然后再从中序中找到,再把左右儿子分别看成两颗新的树开始递归.递归完成即可.
除了序列遍历外,还可以通过 \(dfs\) 进行遍历.这样可以算出每一点的深度, \(dfs\) 序列等等...
标签：遍历,后序,中序,树论,基础,二叉树,root,可以 From： https://www.cnblogs.com/zhong114514/p/17087756.html