第四章 树和二叉树

1、对于具有层次结构的数据需要用树形结构来描述。

2、树形结构中一个结点可以有一个或多个直接后继。

3、树是n个结点的有限集合，满足：当n=0时，称为空树；当n>0时，有且仅有一个称为根的结点，除根结点外，其余结点分为m(m>=0)个互不相交的非空集合，这些集合中的每一个都是一棵树，称为根的子树。

4、森林是m颗互不相交的树的集合。

5、结点的度：树上任一结点所拥有的子树的数目称为该结点的度。

叶子：度为0的结点成为叶子或终端结点。

树的度：一棵树中所有结点的度的最大值称为该树的度。

一个结点的子树的根称为该结点的孩子。相应地该结点称为孩子的双亲。

结点的层次：从根开始算起，根的层次为1，其余结点的层次为其双亲的层次加1.

树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度。

有序树：若树中各结点的子树从左到右是有次序的，不能互换，称为有序树。

无序树：若树中各结点的子树都是无次序的，可以互换，则称为无序树。

6、二叉树是n个元素的有限集合，该集合或者为空，或者由一个根及两颗互不相交的左子树和右子树组成。（左右子树也均为二叉树）

7、二叉树性质：

a 二叉树第i(i>=1)层上至多有2^(i-1)个结点；

b 深度为k（k>=1）的二叉树至多有2^k - 1；

c 对任何一颗二叉树，若度数为0的结点（叶结点）个数为n0，度数为2的结点个数为n2，则n0=n2 + 1；

d 满二叉树：深度为k(k>=1)且有2^k - 1个结点的二叉树为满二叉树。

8、完全二叉树：如果对满二叉树按从上到下，从左到右的顺序编号，并在最下一层删去部分结点（删后最后一层仍有结点），如果删除的这些结点的编号是连续的且删除的结点中含有最大编号结点，那么这棵二叉树就是完全二叉树。

含有n个结点的完全二叉树的深度为log2^n（向下取整）+1；

如果将一颗有n个结点的完全二叉树按层编号，每层从左到右顺序依次为：1,2,3···n。对任一编号为i（1<=i<=n）的结点A有：

若 i=1，则结点A是根；若i>1，则A的双亲Parent（A）的编号为 i/2 向下取整；

若 2*i > n，则结点A既无左孩子，也无右孩子；否则A的左孩子的编号为2*i；

若 2*i + 1 > n，则结点A无右孩子；否则，A的右孩子的编号为2*i +1；

9、二叉树的顺序存储结构

完全二叉树存储示例：

非完全二叉树存储示例：

10、二叉树的链式存储：

二叉链表：具有n个结点的二叉树中，有2n个指针域，其中只有n - 1个用来指向结点的左、右孩子，其余的n + 1个指针域为NULL。

三叉链表：具有n个结点的二叉树中，采用二叉链表存储，有n + 2个指针域为NULL。

11、二叉树的遍历：先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）、层次遍历；

12、二叉树的先序遍历非递归算法可以借助栈来实现。

13、树的存储结构为：孩子链表示法、孩子兄弟链表示法、双亲表示法。

14、树转换为二叉树的方法：a 将所有兄弟结点链接起来；保留第一个兄弟结点与父亲结点的链接，断开其他兄弟结点与父结点的连续，然后以根结点为轴心按顺时针的方向旋转45度。

15、森林转换成二叉树：将每课树转换成相应的二叉树；再将得到的各颗二叉树根结点是兄弟连接起来。

16、树的遍历：先序遍历（根左右）、后序遍历（左右根）、层次遍历。

17、森林遍历：先序遍历（根左右）、中序遍历（左根右）。

18、哈夫曼树和哈夫曼编码（这个挺好的理解的，主要求它的平均编码长度）。

又困了