树的回顾（1）

1.什么是树？

树就是树哈哈 一棵树 有树干 树枝 叶子 而树这个数据结构 就有类似的根 先拿一个图来看吧这是我随便找的一个图 哲理可以看出来是从R出发 此时 R就是这个树的根节点而A、B、C就是R的孩子R就是A、B、C就是双亲 且ABC互称兄弟节点而途中没有孩子的节点 就是叶子节点而每个节点有几个孩子就有几个度 树的度就是整个树孩子最多节点的度 树的层：R开始是第一层 依次往下树的深度（高度）：树的总层数

树还有有序树和无序树 将树中节点从左至右是有次序的不能互换就为有序树反之无序树

1.2什么是森林？

森林就是有很多树嘛 就是互不相交树的集合这就是森林

2.树的存储结构

其实由图可以看出来树需要指向这个操作来链接孩子与双亲这里有双亲表示法、孩子表示法、孩子兄弟表示法

先说双亲表示法 就是记录每个节点的双亲位置 从下到上就能知道树的结构是什么样子 我觉得这个方法还是可以的 因为每个节点只有一个双亲 只需要指向单一节点 想起来比较简单 结合代码看一下当然也有缺陷 就是想要找到节点孩子必须遍历整个树 这里开始我还不知道为什么 问了豆包 说是因为只能将所有节点遍历完 查看完所有节点parent才不会漏掉孩子节点 其实很灵活的 哎呀 你还可以加很多东西 直接加孩子下标 兄弟下标 什么什么的 都可以解决很多问题 只不过有点麻烦

孩子表示法、孩子兄弟表示法其实差不多 都是指过去指过来从而解决各种问题

3.二叉树

简单来说就是树的度最大为2的树且严格区分左子树右子树简单来说就是每个节点最多只能有两个孩子 根节点没有孩子就是空二叉树

3.1特殊二叉树

3.1.1斜二叉树

就是所有节点只有左子树或者右子树 分别称为左斜树和右斜树

3.1.2满二叉树

这个比较好理解 就是所有节点除了叶子节点度为2 都有左右孩子

3.1.3完全二叉树

理解起来有点难 我也是看b站up主学到的一个比较容易理解的办法没有左子树，不能有右子树，上一层没有铺满，不能有下一层我对完全二叉树的理解也还不够 我还知道的就是叶子节点只能出现在最后两层 其次就是上面说的 还是要多判断判断

3.2二叉树的性质

1.二叉树第i层最多有个节点

2.深度为k的二叉树最多有个节点

3.对于任意二叉树 如果终端节点数为，度为2的节点数为则

4.具有n个节点的完全二叉树的深度为

还有第五点过于复杂这里就先不说了

3.3二叉树链式结构代码实现

可以看出二叉树是具有左右孩子的 这里就需要说明我们还需要手动创建一个二叉树

这里使用了递归来创建上图二叉树

3.4二叉树的遍历

有前序遍历、中序遍历、后序遍历、层序遍历其实前三个代码上只有顺序区别 层序遍历有需要用到队列这个东西 这里先说前三个 先看代码

前序

看得出最先执行的就是打印根节点然后一直往左走 边走边打印（lc为左 rc为右）然后打印完左子树再打印右子树

打印顺序

中序

看得出一直向左走直到没有左子树就打印 然后判断有没有右子树

后续