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为右然后打印完左子树再打印右子树打印顺序中序看得出一直向左走直到没有左子树就打印 然后判断有没有右子树后续