定义

• 度
  • 节点度 $:=$ 子节点个数
  • 树度 $m$ $:=$ 节点最大度数 aka. $m$ 叉树
• 满二叉树 := 度只有 0/2
• 完全二叉树 := 只可以最后一层不满
• 完美二叉树 := 所有层都满
• 线索二叉树
• 最优二叉树

性质

1. 节点与度数

   1. 树节点 $n$ = 度数和 + 1
   2. 高度为 $h$ 的 $m$ 叉树总结点数 $n$ $\le$ $\frac{m^{h}-1}{m-1}$
   3. $m$ 叉树
      1. 第 $i$ 层节点数 $\le$ $m^{i-1}$
      2. 节点 $i$ 的第 $j$ 个儿子 $= (i-1)m+j+1$
   4. 二叉树
      1. $n_{0}=n_{2}+1$

2. 高度分析 $$\log_{m}(n(m-1)+1) \leq h \leq n-m+1 $$

   1. 节点为 $n$ 的 $m$ 叉树高度 $h$ $\ge$ $\log_{m}(n(m-1)+1)$ 由 $\frac{m^{h}-1}{m-1} \ge n$
   2. 节点为 $n$ 的 $m$ 叉树高度 $h$ $\le$ $n-m+1$ 构造只有根节点度数为 $m$，其余节点度数为 $1$ 故 $n$ 个节点只浪费 $m-1$ 个节点

3. 遍历

   1. 给定 $n$ 个节点先序遍历求所有可能，等于出栈方案数 $\frac{1}{n+1}C_{2n}^{n}$ (卡特兰数)
   2. 遍历序列最后一个节点要考虑偏子树
   3. 线索树
      1. 后序线索树遍历要借助栈
      2. 是物理结构

应用

哈夫曼

• 前缀编码：左 0 右 1 只有叶结点
• 哈夫曼树
  • 构造方法
    1. 每个点赋权值，构成权值集合 $S$
    2. 选权值最小的节点(子树) $a, b \in S$
       1. $S$ -= ${a,b}$
       2. 构造最小二叉子树 val: a+b lchild: a rchild: b
       3. 把 $(a+b)$ 放回 $S$
    3. 重复 2. 直到 $S=\emptyset$
  • 性质
    1. 满
    2. $WPL=\sum$ leaf[i].val $\times$ leaf[i].depth $=$ $\sum$ 分支节点权值
• 哈夫曼编码
  • 把出现频率作为权值
  • 在哈夫曼上 左 $0$ 右 $1$
  • 出现的越多编码长度越短

并查集

并查集

实验坑点

1. 树不一定是二叉树
2. 序号 1 不一定是根节点