基本术语和二叉树定义.ppt

6.1 树的定义和基本术语(知识点一) 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树与线索二叉树（知识点二） 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林（知识点三） 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码 两类特殊的二叉树-1 一棵深度为k的且有 个结点的二叉树叫满二叉树。 第一类： 满二叉树 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 特点：每一层上的结点数都是最大结点数。 。。。K=1 层 。。。K=2 层 。。。K=3 层 。。。K=4层 深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。 1 2 3 11 4 5 8 9 12 6 7 10 特点：叶子结点只可能在层次最大的两层上出现。 对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1。 两类特殊的二叉树-2 第二类：完全二叉树 第L层 第L+1层 性质4：具有n个结点的完全二叉树的深度为 证明：由性质2和完全二叉树的定义有： K是整数 性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1?i?n)，有： (1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是结点 ?i/2?。 如果2in，则结点i无左孩子； 否则，编号为2i的结点为其左孩子。 (3)如果2i+1n，则结点i无右孩子； 　否则，编号为2i+1的结点为其右孩子。 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，其双亲结点为编号?i/2? ； 其左孩子结点为编号 2i ； 其右孩子结点为编号2i+1; (2) 若 2in，则该结点无左孩子，若 2i+1n，则该结点无右孩子结点. 1 2 3 4 5 6 7 8 9 10 (1)i=1,结点1就是二叉树的根,无双亲; (2)i=2, 性质5举例： 证明性质5 的（2）和（3）: 对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，结点i无孩子。结点i的右孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。 对于i1，可分为两种情况： 1）设第j（1=j= ?log2n? )层的第一个结点的编号为i，由二叉树的性质2和定义知i＝2j-1 结点i的左孩子必定为j＋1层的第一个结点，其编号为2j＝2×2j-1＝2i。如果2in，则无左孩子。其右孩子必定为第j＋1层的第二个结点，编号为2i＋1。若2i+1n，则无右孩子。 2）假设第j（1=j= ?log2n? )层上的某个结点编号为i（2j-1=i=2j-1),且2i＋1n，其左孩子为2i，右孩子为2i＋1，则编号为i＋1的结点是编号为i的结点的右兄弟或堂兄弟。若它有左孩子，则其编号必定为2i＋2＝2×（i＋1）：若它有右孩子，则其编号必定为2i＋3＝2×（i＋1）＋1。 证明（1）: 当i＝1时，就是根，因此无双亲，当i1时，如果i为左孩子，即2×（i/2)=i,则i/2是i的双亲；如果i为右孩子，i＝2p+1,i的双亲应为p，p＝（i－1）/2= ?i/2? 。 接 证明性质5 的（2）和（3）: #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_ TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt; 6.2.3 二叉树的存储结构 二叉树的存储结构分为：顺序存储结构和 链式存储结构两种形式。 1、顺序存储结构 例1：实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。 例2: A B C D E F A B D C E F 0 1 2 3