未完待续
树的概念：
子树
根结点
内部结点
叶结点或终端结点
深度或高度：根为第一层，根的孩子为第二层，依次类推，树中结点最大的层数就称为深度或高度。
在树中，如果任意一个结点的子树，从左到右都是有次序的，那么这棵树被称为有序树，反之则为无序树。
森林：由多棵不相交的树的集合。
树的存储结构：
双亲表示法：
- 双亲域：每个结点设置一个指向双亲位置的单元。
- 长子域：每个结点设置一个指向第一个结点位置的单元。
- 右兄弟域：每个结点设置一个指向右边兄弟位置的单元。
孩子表示法：
- 方案一：每个结点都持有固定数量的孩子域，把所有的孩子的单元地址都持有。（此方法有一个缺点，在孩子数量极其不一致的时候，会浪费许多的空间）。
- 方案二：对方案一进行改进，采用链表存储的方法来指向所有的孩子，并有一个空间标明当前孩子个数。（此方法对空间利用率提高了，但需要维护各结点的度的数值，在运算上效率还不是最高的）。
- 方案三：用顺序存储结构来储存所有的结点，每个结点都有一个长子域，对比方案二 不同的是，双亲不持有所有孩子的引用，而是让孩子的上一个哥哥来持有，这样在遍历该结点的所有孩子后，就可以知道该结点的深度为多少。
孩子兄弟表示法：每个节点有两个指向，一个指向长子，一个指向弟弟。这样做的好处是，假如有一个结点有三个或三个以上的孩子，用孩子兄弟表示法可以表示为二叉树的形式，极大地方便操作。
二叉树
特殊二叉树：
1. 斜树：所有结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树。
2. 满二叉树：根结点和内部节点都有存在左子树和右子树，并且所有的叶结点都在同一层上。
3. 完全二叉树：对于一棵二叉树，其编号为为I的结点与同样样深度的满二叉树中编号为i的结点位置相同，则这棵二叉树称为完全二叉树。
可以看出：满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。
二叉树的性质：
性质一：二叉树的第i层上最多有有2的（i - 1）次方个结点。
性质二：深度为k的二叉树最多有（2的（k）次方）-1个结点。
性质三：对任何一棵二叉树T，设有两个孩子结点数位n2，有一个孩子结点数位n1，没有孩子结点数为n0，则，n0 = n2 + 1。（加上分支总线来推导）
性质四：具有n个结点的完全二叉树的深度为（log2n） + 1。
性质五：对于一棵完全二叉树，若结点2i > n，那么它没有左孩子；若2i + 1 > n，那么它没有右孩子。
顺序存储结果一般只用于完全二叉树。
二叉链表：每个结点有一个数据域和两个指针域（分别指向左右子结点）。
遍历二叉树：
前序遍历：先打印自己，再遍历左子树，再遍历右子树/
中序遍历：先遍历根节点的左子树，再打印自己，最后才是右子树。
后序遍历：先遍历左子树，再遍历右子树，最后才打印自己。
层序遍历：一层一层访问。
已知前序和后序，是不能确定一棵二叉树的。
线索二叉树：
用二叉链表来表示二叉树时，有的结点会出现左孩子为空，或右孩子为空的情况，浪费了分配的空间，所以把这些空间都利用起来，用来储存该二叉树的前驱和后继，可以使得在遍历时大大提高效率。
树、森林和二叉树的转换：
树转换为二叉树：参考孩子兄弟表示法。
森林转换为二叉树：
按照树转换成二叉树的方法，把森林中的树都转换成二叉树，再将其连接起来。
树与森林的遍历：
树的遍历：
- 先根遍历树：先访问树的根结点，然后依次先根遍历根的每棵子树。
- 后根遍历树：先依次后根遍历每棵子树，然后再访问根结点
森林的遍历：
- 前序遍历：先访问第一颗树，然后按照先根遍历树访问该树，依次访问所有的树。
- 后序遍历：先访问第一棵树，采用后根遍历方法遍历每棵子树，依次遍历剩下的树。
赫夫曼树：
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。
树的路径长度就是从树根到每一结点的路径长度之和。
带权路径长度WPL最小的二叉树称做赫夫曼树。
构建方法，将当前最小的两个组合在一起，相加当成一个结点，重复此步骤。