PS-05 Binary Trees

1. 树

一种连通无环图

节点深度即为从根节点到达该节点的路径长度

根的深度为0

所有叶子中深度最大者称为子树的高度

空树高度取作-1

树的表示

用父亲节点+孩子节点表示

任何一棵有根有序的多叉树都可以转化为二叉树

满二叉树

高为 $h$的二叉树节点数 $n=2^{h+1}-1$

真二叉树

每个节点都有两个孩子

2. 二叉树

实现

先序遍历

void traverse(x, visit){
	visit(x);
	traverse(x->lc, visit);
	traverse(x->rc, visit);
}

制约：递归深度有限

改进

先访问最左侧的一根藤，然后自下而上访问藤上每个右子树，每个右子树仍以同样的方式遍历

用栈来实现

中序遍历

void tarverse(x, visit){
	traverse(x->lc, visit);
	visit(x);
	traverse(x->rc, visit);
}

迭代方法

先从最左侧的藤走下去，走到最深处，然后从下而上遍历藤上节点以及右子树

用栈来实现

在中序遍历意义下，如果有右孩子，直接后继为最靠左的右后代，

如果没有，反过来想，应是以该节点为直接前驱的节点

后序遍历

void tarverse(x, visit){
	traverse(x->lc, visit);
	traverse(x->rc, visit);
	visit(x);
}

迭代

尽量沿左走，如果左走不了，则向右，直到无路可走，然后自下而上遍历节点以及右子树（如果有的话）

还是用栈来实现

层次遍历

（广度优先搜索hhh）

运用队列来迭代

完全二叉树

• 底层叶子只居于最底下两层，且最后一层的叶子都靠在最左侧的真二叉树
• 叶子节点不比内部节点少，至多多出来一个
• 辅助队列最大规模 $n/2$向上取整

重构

可以用两个向量或列表来重构二叉树

先序/后序+中序

完全可行，在先序的头或后序的尾找到中间节点，再在中序中找到中间节点分割即可，左边就对应左子树，右边则对应右子树

先序+后序

当原二叉树有左右两棵子树时，通过查找两棵子树的根节点也能把左右子树对应的序列区分开来，但是当只有一棵子树时，就不行了

3. Huffman 编码树

关键：不同字符的编码互不为前缀（Prefix-Free Code)

平均编码长度等于叶节点的平均深度

最优编码树

平均编码长度最小者，最特别的是真完全树，否则可以通过交换节点来实现最优

但实际上不同字符的出现频率并不相同，叶节点的平均深度要加上频率的权重，此时完全树就未必是最优编码树

考虑频率时，要把频率高的字符放在高处，频率低的字符放在低处

贪心策略

所有字符单节点作为一棵树，组成森林，按频率将树从小到大排序，取出频率最小的两棵树组成一棵新的树，然后放回森林中，如此循环往复，最终组成一棵完整的树，符合频率低的在低处，频率高的在高处

如果采用向量或者列表，复杂度要 $O(n^{2})$

如果采用优先级队列，复杂度为 $O(nlogn)$