62.《树和二叉树简阐论》

是的这是一篇迟来的树与二叉树阐述总结 看到博客园的情况 不知道是否是最后一篇 但无论如何都应该不感慨

简单看 树 二叉树 森林

先看一些头疼的概念（自我总结）：
树：n个结点的有限集 
二叉树：在树的基础上每个结点最多有两个子树
森林：m棵不相交树的集合

所有都是在树的基础上衍生出来的所以先看树 一些基本术语
一张图搞定

不管那么多 用用就会了

重点：树的性质
1.n结点数=所有边数之和+1 n结点数=所有结点度数之和+1
2.度为m的树第i层最多有 m的i-1次方 个结点
3.高度为h的m叉树最多有 (mh次方-1)/(m-1) 个结点
4.度为m n个结点树 最小高度 logm（n(m-1)+1）向上取整
5.度为m n个结点树 最大高度 n-m+1

重点：二叉树的性质
1.n0=n2+1 度为0的结点数=度为2的结点数+1
2.二叉树每个结点的左孩子编号为2i 右孩子为i/2向下取整
3.第k层最多有 2的k-1次方 个结点
4.高度为h的二叉树 最多有 2的h次方-1 个结点
5.满二叉树只有度为0和2 完全二叉树最多只有一个度为1结点且叶子结点出现最大两层

是的就这些性质能考一堆题了 我也归纳为第一大考点看例题 具体应用：

度为3的数中 结点数为50 最小高度为多少

这个真题很重要 度为4的树 20个度为4的结点 10个度为3的结点 1个度为2 10个度为1 求叶子结点个数

具体就是根据性质总结点数等于各结点度数之和+1来得出 所以很简单就简单记住 204+103+12+101+1-20-10-1-10 当然如果给了你叶子节点 也可以倒推出其他未知的已知度结点的个数
具有1025各结点的二叉树高

最大肯定是一层一个结点1025 然后最小根据树的性质即可

一棵完全二叉树上有1001个结点 叶结点数

就除于2向上取整

真题 一棵完全二叉树第6层有8个叶结点 结点数最小 最大是多少

二叉树概念啥的真没啥好说的重要的是应用 简单看一个东西：

三个结点可以构成几种二叉树

注意有左右子树之分

再看一下链式存储和顺序存储 n个结点二叉链表有n+1个空链域

二叉树的遍历和线索二叉树

分为两个知识点
1 先序遍历 中序遍历 后序遍历 层序遍历(基本不用)
2.由遍历确定二叉树
3.简单阐述线索二叉树

这个说那么多废话没什么用简单看：

关于遍历确定二叉树我认为一道题够了3

二叉树先序遍历结果为ABCDEF 中序遍历CBAEDF 求后序遍历

必须中序遍历 和任意一种结合便可确定 但是完全二叉树就不是了

完全二叉树后序遍历 CDBFGEA 先序为....根据其特点来确定

关于线索二叉树我这个考试不注重考察简单阐述一下

为的就是查找其前驱和后继 注意是先中后序排完后所指的

树 二叉树 森林 之间的转换

树的存储结构：
双亲链表表示法 孩子链表表示法 孩子兄弟表示法
孩子兄弟表示法最重要：为的就是树转换成二叉树
第一个孩子指针域 右兄弟指针域 数据域

看一下转化 就是 左孩子右兄弟 根节点和左子树为第一棵树 右边指向下一棵树
因此根节点右指针可能为空

哈夫曼树(最优二叉树)和哈夫曼编码

WPL带权路径
哈夫曼树的构造
哈夫曼编码

时间不够了 一道题看下三个概念的应用
字符集{ABCDE} 出现的频度为8 18 22 4 32

假设规定左0 右1