五种基本形态：
R L R 性质：
在二叉树的第 i 层上至多有 2i－1个结点。(i 1) [证明用归纳法]
证明：当i=1时，只有根结点，2i-1=20=1。假设对所有j，i>j?1，命题成立，即第j层上至多有2j-1 个结点。
由归纳假设第i-1 层上至多有 2i－2个结点。
由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即 2?2i－2= 2i-1。
对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0＝n2+1. 证明：若度为1的结点有 n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1
具有 n (n 0) 个结点的完全二叉树的深度log2(n)＋1（log2(n＋1)） 证明：设完全二叉树的深度为 h，据完全二叉树的定义有 2h-1-1 < n ? 2h - 1或 2h-1? n< 2h 取对数 h-1 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，则有以下关系： 若i = 0, 则 i 无双亲 若i > 0, 则 i 的双亲为?(i -1)/2? 若2*i+1 < n, 则 i 的左孩子为 2*i+1，若2*i+2 < n, 则 i 的右孩子为2*i+2 若结点编号i为偶数，且i!=0,则左兄弟 结点i-1. 若结点编号i为奇数，且i!=n-1,则 右兄弟结点为i+1. 结点i 所在层次为?log2(i+1)? 二叉树链表的表示： root A B D E F B ? C ? root A ? D ? E ? ? F ? 二叉树 二叉链表 二叉树的遍历： 前序遍历算法： 若二叉树为空，则空操作； 否则 访问根结点记作 （D）； 遍历根的左子树记作 （L）； 遍历根的右子树记作 （R）。 中序遍历算法： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R）。 后续遍历算法： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。 三、 树与森林 树的存储结构 双亲表示(树的顺序存储结构)： 以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。该方法利用每个结点只有一个双亲的特点，可以很方便求结点的双亲，但不方便求结点的孩子。 A B E F C D G datparent 0 1 2 3 A B C D -1 0 0 0 多重链表(树的链式存储结构)：等数量的链域 (k为树的度) A B E F C D G B A ? C ? ? ? D G childk E ? ? ? F ? ? ? data child1 child2 child3 树与二叉树的转换 树/森林与二叉树之间有一一对应关系。 任何一个森林或一棵树可唯一对应到一棵二叉树； 任何一棵二叉树也能唯一对应到一个森林或一棵树。 1) 树 二叉树 在兄弟结点间加一连线；对每个结点，除了与第一个孩子有连线，去除与其它孩子的连线。树转换为二叉树，其右子树为空(树根无兄弟)。 2) 森林 二叉树 先将森林中每一棵树变为二叉树，然后将各二叉树的根结点视为兄弟连在一起。 森林转换为二叉树，其右子树不为空。 3) 二叉树 树、森林 若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。 四、 赫夫曼树 路径长度 (Path Length) 结点间的路径长度PL：是连接两结点的路径上的分支数。 树的外部路径长度是各叶结点(外结点)到根结点的路径长度之和 EPL。 树的内部路径长度是各非叶结点(内结点)到根结点的路径长度之和 IPL。 树的路径长度：树根到各结点的路径长度之和。 树的路径长度 PL = EPL + IPL 带权路径长度 (Weighted Path Length, WPL) 二叉树的带权路径长度是树的各叶结点所带的权值 wi 与该结点到根 的路径长度 li 的乘积的和。 给结点赋予一个有某种意义的实数。 赫夫曼树 n?1WPL??wi?0iil带权路径长度达到最小的二叉树即为赫夫曼树。 在赫夫曼树中，权值大的结点离根最近。 参考文献; [1]曹桂琴 郭芳 《数据结构学习指导》 大连理工出版社 [2] 傅清祥 王晓东 《算法与数据结构》 电子工业出版社 [3]严蔚敏 吴伟民 《数据结构（C语言版）》清华大学出版社 [4] 辛运帏 陈有祺 《数据结构与算法》 高等教育出版社