数据结构导论自考全书重点综合复习.ppt

第四章树和二叉树 要点： 1.树的基本概念 2.二叉树的概念及性质 3.二叉树的顺序存储结构 4.二叉树的链式存储结构 5.二叉树的遍历 6.树的表示、树和森林的转换 7.哈夫曼树 树的基本概念 树 结点的度 叶子 树的度 结点的层次 树的高度 森林 基本运算： 求根 求双亲 求孩子 建树 剪枝 遍历 经典题例 ?6．除根结点外，树上每个结点（　　　） ?A．可有任意多个孩子、任意多个双亲 ?B．可有任意多个孩子、一个双亲 ?C．可有一个孩子、任意多个双亲 ?D．只有一个孩子、一个双亲 7.根据定义，树的叶子结点其度数（　　　） A.必大于?0???????B.必等于0 C.必等于1???????D.必等于2 经典例题 ?21．在下列树中，结点H的祖先为__________。 7.树是n个结点的有穷集合，(????? ) A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 经典例题 8.除根结点外，树上每个结点( ) A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。 9.题9图中树的度为( ) A.2 B.3 C.5 D.8 经典例题 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点 二叉树的概念及性质 二叉树的定义 二叉树的形态 满二叉树 完全二叉树 性质1：二叉树第i层上至多有2i-1个结点。 性质2：深度为k的二叉树至多有2k-1个结点。 至少有k个结点。 性质3：对任何一棵二叉树，若度数为0的结点个数为n0,度数为2的结点个数为n2,则n0=n2+1. 性质4：含有n个结点的完全二叉树的深度为∟log2n」+1. 性质5：如果将一棵有n个结点的完全二叉树按层编号，从第一层到最后一层，每层从左到右的顺序依次标记为1,2,3…n,则对任一编号为i的结点A有： （1）若i=1,则A是根；若i1,则A的双亲的编号为i/2; （2）若2*in,则A既无左孩子，也无右孩子；否则A的左孩子为2*i; (3)若2*i+1n则A无右孩子，否则，A的右孩子为2*i+1. 经典题例 8.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（　　　） A.3 B.4 C.5 D.6 9.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（　　　） A.24 B.25 C.98 D.99 21.三个结点可构成________种不同形态的二叉树。 经典题例 ?7.关于二叉树性质的描述，正确的是（　　　） ?A.二叉树结点的个数可以为0 ?B.二叉树至少含有一个根结点 ?C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子 ?D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子 ?8.具有4个结点的二叉树可有（　　　） ?A.4种形态? B.7种形态 ?C.10种形态? D.11种形态 ?22.深度为k的满二叉树其叶子结点个数共有________________个。 9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（　　） A.99 B.98 C.97 D.50 经典题例 24.对于一棵满二叉树，若有m个叶子，则树中结点数为____________。 21.若满二叉树的结点数为n，则其高度为________。 22.在一棵具有n个结点的完全二叉树中，从树根起，自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点，那么其父结点的编号为_____。 23.深度为k的二叉树，结点数最多有________个。 经典题例 22.深度为k的二叉树至多有______个结点，最少有______个结点。 9.在一棵深度为H的完全二叉树中，所含结点的个数不少于（　　） A.2H-1-1 B.2H-1 C.2H-1 D.2H 19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为_______