数据结构——第6章树和二叉树北华航天工业学院计算机系制作目标理解树、二叉树的定义、相关术语；掌握二叉树的二叉链表存储方式、二叉树性质；掌握二叉树的四种遍历方式及遍历的实现算法；理解二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题理解树、森林和二叉树间的转换理解树、森林的遍历北华航天工业学院计算机系制作本章内容6.1树的定义和基本术语6.2二叉树6.3二叉树的遍历和线索二叉树6.4树和森林6.5哈夫曼树及其应用北华航天工业学院计算机系制作6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构北华航天工业学院计算机系制作1．二叉树二叉树（BinaryTree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个互不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，元素称作结点。二叉树是有序树。二叉树有五种形态。6.2.1二叉树的定义北华航天工业学院计算机系制作•二叉树的五种基本形态：6.2.1二叉树的定义Ø北华航天工业学院计算机系制作2．二叉树的相关概念结点的度；叶子结点；分支结点；左孩子、右孩子、双亲、兄弟；路径、路径长度；祖先、子孙；结点的层数；树的深度；树的度；满二叉树；完全二叉树6.2.1二叉树的定义北华航天工业学院计算机系制作6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构北华航天工业学院计算机系制作6.2.2二叉树的主要性质性质1一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。性质2一棵深度为k的二叉树中，最多具有2k-1个结点。证明设第i层的结点数为xi（1≤i≤k），深度为k的二叉树的结点数为M，xi最多为2i-1，则有：北华航天工业学院计算机系制作性质3对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0＝n2＋1。证明：结点总数n＝n0＋n1＋n2（6-1）在二叉树中，除根结点外，其余结点只有唯一的一个前驱。则有：分支数＝n－1（6-2）这些分支是由度为1和度为2的结点发出的，所以：分支数＝n1＋2n2（6-3）综合上三式可得：n0＝n2＋16.2.2二叉树的主要性质北华航天工业学院计算机系制作性质4具有n个结点的完全二叉树的深度k为log2n+1。证明：当一棵完全二叉树的深度为k、结点个数为n时，满足2k－1≤n<2k。对不等式取对数，有k－1≤log2n1，则双亲结点的序号为i/2；如果i＝1，则i是根结点，无双亲结点。⑵如果2i≤n，则左孩子结点的序号为2i；如果2i>n，则无左孩子；如果2i＋1≤n，则右孩子结点的序号为2i＋1；如果2i＋1>n，则无右孩子。注意：若对二叉树的根结点从0开始编号，都会发生变化。6.2.2二叉树的主要性质北华航天工业学院计算机系制作选择题1、按二叉树的定义，具有3个结点的二叉树有（）种。A、3B、4C、5D、62、深度为5的二叉树至多有（）个结点。A、16B、31C、32D、103、对一个满二叉树，m个树叶，n个结点，深度为h，则（）。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-1答案：1（C）2（B）3（D）6.2.2二叉树的主要性质北华航天工业学院计算机系制作选择题4、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中包含的结点数至少为（）。A、2hB、2h-1C、2h+1D、h+15、对于一棵深度为4的三叉树，最多具有（）个结点。A、30B、36C、40D、54答案：1（B）2（C）6.2.2二叉树的主要性质北华航天工业学院计算机系制作填空题1、深度为k的完全二叉树至少有（）个结点，至多有（）个结点，若自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（）。2、一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非叶子结点。答案：1(2k-1,2k-1,2k-1)2(n/2,n/2+1)6.2.2二叉树的主要性质北华航天工业学院计算机系制作6.2二叉树6.2.1二叉树的定义6.2.2二...
