二叉树 原创

树的基本术语P112

结点的度：结点拥有的【子树】成为结点的度。

树的度：树的度是树内各结点度的最大值。

叶子：度为0的结点。

树的深度：树中结点的最大层次称为树的深度或高度。

有序树和无序树：树中各结点的各子树看成从左至右是有序的（不能互换），责成有序树。

森林：是m棵不相交的数的集合。

二叉树性质P118

性质一：二叉树第i层上至多有2^(i-1)个结点（i>=1)

性质二：深度为k的二叉树至多有2^k-1个结点的二叉树（i>=1)。 

满二叉树：深度为k，且含有2^k-1个结点的二叉树。

完全二叉树：深度为k，有n个结点的二叉树。

有n个叶子节点的二叉树，有2*n-1个节点。

含有n个结点的二叉链表中有n+1个空链域。

1、一棵完全二叉树有1001个节点，其中叶子节点的个数是：501

2、一个具有1025个节点的二叉树高度h为：10

[解析]  当高度为 10时，此时即使 树为满二叉树也不够1025个节点，所以树高的最小取值为 11当树的每一层只有一个节点时，此时的树高为1025  。这一个具有1025个结点的二叉树的高h为11至1025之间。  

二叉树的遍历  

二叉树的遍历：前序遍历、中序遍历和后序遍历 。先后是相对于树的根节点

二叉树有四个特征： 

特性1：对于前序遍历，第一个是根节点；

特性2：对于后序遍历，最后一个是根节点；

特性3：在中序遍历中，根节点的两边就可以分出左子树和右子树 ；

特性4：对左子树和右子树分别做前面3点的拆分，相当于做递归，就可以重建出完整的二叉树；  

 已知二叉树的前序遍历和中序遍历，如何得到它的后序遍历 ？ 

 例题：设一颗二叉树的先序遍历：ABDFCEGH，中序遍历：BFDAGEHC。

1、画出这棵树。

2、将这棵树转化成对应的树（或森林）

树与森林转换  

树与森林转换：1、左子树，右兄弟  

把一棵树转换成二叉树后,这棵树的形态：唯一的，且根结点没有右子树。

哈夫曼树  （最优树）

哈夫曼树 ：哈夫曼树（Huffman Tree）是最优二叉树。给定n个权值作为n个叶子的结点，构造一棵二叉树，若树的带权路径长度达到最小，这棵树则被称为哈夫曼树。

构造哈夫曼树：

贪心法：首先选择权小的，这样保证权大的离根较近，在计算【带权路径长度 】时，自然最小。