基本概念
几种特殊的二叉树
满二叉树
完全二叉树
完全二叉树未必是满二叉树
满二叉树是一种特殊的完全二叉树
二叉排序树
二叉树的存储结构
顺序存储
链式存储
^代表指向NULL
二叉树的遍历
先序遍历
空间复杂度：O(h+1),即O(h)，h为二叉树的高度，+1是指叶子结点的空结点
中序遍历
后序遍历
遍历算法的应用举例
二叉树的层序遍历
由遍历序列构造二叉树
后序、层序遍历的结论同上
线索二叉树
普通二叉树存在的问题：每次遍历的时候都必须从根节点出发
线索二叉树的作用
线索二叉树的存储结构
三种线索二叉树
区别：按照不同的遍历次序
二叉树线索化 （代码，上节为手算）
线索二叉树找前驱/后继
灵光乍现明白了：靠人不如靠己
因为它已经有前驱就是它的左孩子所以它必有左孩子
树的存储结构
树的逻辑结构回顾
双亲表示法
找双亲方便，找孩子不方便
孩子表示法
找孩子方便，找双亲不方便
孩子兄弟表示法（链式存储）
树和二叉树的转化
优点：可以用二叉树操作来处理树
用孩子兄弟表示法存储的树在物理上呈现出“二叉树”的亚子
树、森林与二叉树的转换
本质：用二叉链表存储森林
树、森林的遍历
树的遍历
先根遍历和后根遍历为深度优先遍历
森林的遍历
哈夫曼树
带权路径长度
哈夫曼树的定义
哈夫曼树的构造
哈夫曼编码
可变长度编码--允许对不同字符用不等长的二进制位表示
并查集55、56回头再看
