树
邹博
“面试算法”公开课
2/75
主要内容
o 二叉查找树
n 增删改查/其他结构的基础：如AVL
o Huffman树
n 前缀编码
o 前序中序后序遍历
n 三种遍历本身/通过前序中序求后序
o 隐式树的搜索
n 所有括号匹配的字符串
o B树及其变种
n 分裂结点/合并结点
n R树：实践中的应用
o 附：平衡二叉树
n 增删改查
“面试算法”公开课
3/75
决策树的实例
“面试算法”公开课
4/75
树和二叉树
o 一般地说，树的结点间是无序的，即：
o 一个结点有m个孩子L
1
L
2
…L
m
，则L
1
L
2
…L
m
可以互
换位置，仍然认为是一颗树。
o 二叉树的两个孩子，一般称为左孩子、右孩子，不
能互换位置。
n 之所以这样定义，是因为有些算法，需要严格区分左右
孩子，如前序-中序-后序遍历、堆排序等问题。
o 从这个意义上说，树和二叉树是两个概念，不能说
二叉树是树的子集。
n 注：这种区分非常弱而且乱，因为树还有“有序
树”“无序树”的说法。
“面试算法”公开课
5/75
树转换成二叉树
