离散数学

我的一点小巧思:

度数之和: 家谱里的人有多少(除了祖宗)
某一结点的度数:自己生了多少孩子
边:每个结点自己的 脐带 ,祖宗(根节点)从石头里蹦出来的,没有脐带
叶结点: 绝后的人
分支结点: 有后代的人

完全二叉树的性质有:

完全二叉树与顺序存储

完全二叉树是由顺序存储结构引出来的概念。顺序存储二叉树时,普通二叉树会有大量空位浪费空间;而完全二叉树的结点紧凑排列,恰好能高效利用顺序存储。满二叉树只是完全二叉树的一种特殊形式——刚好在图形上每一层都填满,因此得名。

  1. 因为通过树的基本性质有 即: 所以 能通过度为2的点算出 叶结点 数

  2. 度为 1 的点 只有 1 或 0 个,只需要知道 结点数 (奇、偶)就能知道叶节点数

  3. 知道结点数还能利用 层间 等比数列求结点公式 求出 深度 具体公式如下

最多 最少字眼的题 再三检查,一定一定要慎重选择

中序遍历 +任意一个遍历顺序 唯一构造二叉树

线索二叉树

在遍历了完全二叉树后,可以通过线性序列反推回二叉树的结构而诞生的一种循环链表

先维护好这个类似链表的数据结构,后续查找左右子树 或者 根据线索查找某个结点的前驱或后继时会十分容易。

易混点:

  1. 一个线索二叉树 不一定能直接通过 线索 找到 某个节点的 后继(前驱也一样),有时需要根据不同 遍历顺序 通过寻找 左右子树的 最左或最右结点的 结点 确定 后继

树、森林

森林转二叉树
  1. 普通树 转 二叉树 严格遵守 左子树是孩子,右子树是兄弟 的重构要求

  2. 二叉树拼接,遵循 第一颗树的子树森林会转换为左子树,剩余森林则转换为右子树。

由于左孩 右兄所以每个分支结点 的 最右子结点都没有右孩子,并且根节点也没有右孩子

森林转成的二叉树右链表为空域的结点数 等于 (非终端) 分支结点 的数量 加 一

错题

树的基本概念

二叉树的概念

错因 算错了

错因 漏想了一个反例,只有一个根节点的二叉树

错因 算错了

解法 可以将空指针域看作度的反例称作,因为 空 + 度 = 3;这样度为 2 的结点就含有 1 个空,度为 1 的结点有 2 个空(如果是m叉树,就是 m - x(度) 个空)

二叉树遍历和线索二叉树

总结:

这道题 说明了一个关键因素, 根节点(下标为1)在整个遍历序列中是个 游离分子 ,头中尾都可以是他,无论在哪对 左子树 右子树 内的 叶结点序列 都不影响,