树与二叉树

树的基本概念¶

树的定义与基本术语¶

树的任何节点有且仅有一个前驱（除了根节点），不然就是图。

树的性质¶

考点3：m^(i - 1)

**考点4：m^0 + m^1 + ... + m^(h - 1) = (等比数列求和) (m^h - 1) / (m - 1) **

考点5：

高度为h的m叉树至少有h个节点（每一层一个节点）
高度为h的度为m的树至少有h + m - 1(一层为m，其他都为1)

考点6：

树的节点数为n，那么树的边数为n - 1（一个节点除了根节点都只有一个前驱）。

二叉树的基本概念¶

二叉树的定义与基本术语¶

满二叉树和完全二叉树的特点

二叉排序树图示

总结：

二叉树的性质¶

完全二叉树考点二

总结：

二叉树的存储结构¶

二叉树的顺序存储

一个分支节点i的左孩子编号要满足：2i <= n 即 i <= (n / 2)，向下取整。

非完全二叉树

二叉树的链式存储

n - 1个指针是指向前驱的，那么剩下的2n - n + 1 = n + 1是指向空的

二叉树的初始化

习题笔记¶

m叉树
节点i的双亲节点编号

注意： i > 1，因为根节点没有父节点

二叉树的遍历与线索二叉树¶

二叉树的先中后序遍历¶

二叉树的层次遍历¶

由遍历序列构造二叉树¶

线索二叉树的概念¶

此处的前驱和后继指的是遍历序列中的前驱后继，而不是节点的父节点和子节点。

总结：

二叉树的线索化¶

主要现推，理解为主

习题笔记¶

n个节点的线索二叉树上含有的线索数量为 n + 1，因为一共有 2n 个指针域，除了根节点每个节点都有一条前驱，所以一共用了 n - 1 个指针，所以剩下的 n + 1 个空闲指针就用做线索。
后序线索树的遍历仍需要栈的支持。
因为后序线索树找后继需要回到父节点
卡特兰数

对于 \(n\) 个节点能构成的不同形态二叉树的个数 \(C_n\)：

\[C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\]

三大等价考点（答案均为 \(C_n\)）

在考试中，看到以下表述本质都是求卡特兰数：

二叉树形态计数： 给定 \(n\) 个节点，求能构成多少种不同形态的二叉树。
出栈序列计数： 元素按固定顺序入栈（如 \(1, 2, ..., n\)），求合法的出栈序列总数。
遍历序列映射： 已知前序序列（入栈顺序），求可能的中序序列（出栈顺序）个数。

树与森林¶

树的存储结构¶

树、森林与二叉树的转换¶

树和森林的遍历¶

课后习题总结¶

设F是一个森林，B是由F变换来的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有n + 1个。
每一个非终端结点都有一个最后孩子，而这个孩子没有右兄弟，因此他在F中的右指针一定为空，因此有n个
假设B中m棵树，最后一颗树的根节点因为没有右兄弟，所以在F中右指针一定为空
相加即为n + 1

树与二叉树的应用¶

哈夫曼树¶

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
哈夫曼树的结点总数为2n - 1(初始n个结点，n - 1次合并，产生n - 1个结点，n + n - 1 = 2n - 1)
哈夫曼树中不存在度为1的结点
哈夫曼树不唯一，但WPL必然相同且为最优

并查集¶

优化后树的高度不超过floor(log n) + 1

并查集的进一步优化¶

本质都是让树的高度降低

课后习题笔记¶

度为m的哈夫曼树中只存在度为m和度为0的点。（若结点不够合并时，会补0权结点）
合并两个长度分别为m和n的有序表，最坏情况下需要比较m + n - 1次，交叉合并，最后某个有序表只剩一个元素，不用比较，所以 - 1。