树及查找习题课.PPT

树及二叉树 查找习题课 程绪文 二叉树的结构 1.一棵非空二叉树的第i层上最多有__个结点。 2.高度为k的二叉树最多具有__个结点。 3.具有n个结点的完全二叉树的高度k=__。 4.一棵n个结点的完全二叉树的结点按层序自上而下，每一层自左至右编号。设根结点编号1，则对编号为i的结点,有： （1）如i1，父结点编号为__。 （2）如__，则i为叶子，否则左儿子为__。 （3）如__,则i无右儿子，否则右儿子编号__。 二叉树的结构 1.一棵非空二叉树的第i层上最多有 2i-1 个结点。 2.高度为k的二叉树最多具有2k-1个结点。 3.具有n个结点的完全二叉树的高度k=┌log(n+1) ┐ 。 4.一棵n个结点的完全二叉树的结点按层序自上而下，每一层自左至右编号。设根结点编号1，则对编号为i的结点,有： （1）如i1，父结点编号为└ i/2 ┘ 。 （2）如2in ，则i为叶子，否则左儿子为2i。 （3）如2i+1n,则i无右儿子，否则右儿子编号2i+1。 满K叉树 1.一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点(根为第1层)，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： 1）各层的结点数目是多少? 2）编号为i的结点的双亲结点(若存在)的编号是多少? 3）编号为i的结点的第j个孩子结点(若存在)的编号是多少? 4）编号为i的结点的有右兄弟的条件是什么? 提示：层次遍历 满K叉树 2.在具有n个结点的k叉树(k=2)的k叉链表表示中，有多少个空指针? 解答： 出度 = k叉*n个节点 = nk 入度 = (n-1) 每个节点有一个入度，根节点没有入度,故为n-1 入度 +空指针数= 出度 空指针数 = nk-(n-1) = n(k-1)+1 二叉树的遍历 试找出分别满足下面条件的所有二叉树： (1)前序序列和中序序列相同 (2)中序序列和后序序列相同 (3)前序序列和后序序列相同 (4)前序、中序、后序序列均相同 二叉树形态 有n个结点的二叉树具有多少种不同形态？ 提示：递归 作业题 1.设二叉树的结点的数据场之值仅为一大写英文字母。其前序和中序的遍历结果（打印结点的数据场之值）分别保存在字符串数组 pre [N] 及 in [N]之中，其中 N 为常数。请设计程序以标准形式形式存储保存该二叉树。 假设一棵二叉树的前序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。 作业题 2.设树的根结点的层号为1，而其他各层上的结点的层号比其父结点的层号大 1。另外设该树中的结点的数据场之值为正整数。这样数对( Ik，Wk)就表示了该树中的结点的层号和其数据场之值。从键盘上依次输入 m 个数对，如：( I1，W1)，( I2，W2)，……，( Im，Wm)；这些数对是按照结点的前序序列给出的。注意这是用 层号 ＋ 前序 表示一棵树的方法。如：（1，A）, （2，B）, （2，C）, （3，E）, （4，G）, （3，F）, （2，D）, （3，X）, （3，Y）, （3，Z）；它所表示的树如图 3 所示。请编写程序，以标准形式存储这棵树。为了简单起见，可设这棵树上的结点的度数最大为 3，结点的存储形式为： data parent son1 son2 son3 其中：data 域为结点的数据场，parent 域为结点的父亲结点的地址，son1，son2，son3分别给出结点的三个儿子的地址。 问题分析 递归的从序列中构建子树 （1，A）, （2，B）, （2，C）, （3，E）, （4，G）, （3，F）, （2，D）, （3，X）, （3，Y）, （3，Z） （1，A） （2，B） （2，C）, （3，E）, （4，G）, （3，F）, （2，D）, （3，X）, （3，Y）, （3，Z） 静态查找 1.对线性表进行折半查找时，线性表必须满足什么条件。 解答：1. 线性表中数据元素有序 2. 线性表以顺序方式存储 另外，如果是插值查找，除以上两个条件外，还必须满足：线性表中数据元素均匀分布。 静态查找 2.判断：有n个数存放在一维数组A[1…n]中，在进行顺序查找时，这n个数排列有序和无序其平均查找长度相同。 解答：错误。 在等概率情况下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不同。 静态查找 3.在顺序表(8,11,15,19,25,26,30,33,42,48,50） 中，用折半查找法查找关键字20，所需的比较次数为＿ ，依次比较的关键字是＿ ，查找长度为4 的元素个数是＿ 。 解答：1. 4。