题目
解决问题的一种方法是使用2-d树。2-d树类似于二叉搜索树,不同之处在于:
◇偶数层用keyl来比较:在该层上每一结点的keyl都大于共左子树中任一结点的key1,都不大于其右子树中任一结点的keyl。
◇奇数层用key2来比较:在该层上每一结点的key2都大于其左子树中任一结点的key2,都不大于其右子树中任一结点的key2.
◇树的根结点处于第0层。每次插入或搜索都从根结点出发,逐层比较。新结点应作为叶结点插入,
臂如,可以将不同人的姓和名(假设没有同名同姓者)分别为keyl和key2,建立一棵2-d树.作为例子,图7-27就是将清华大学的历任校长,按共任职年代的先后次序(周白齐、唐国安、周春、金邦正、曹云祥、严鹤龄、罗家伦、梅贻琦、叶企孙、蒋南翔、高景德、张孝文、王大中、顾秉林),顺序插人而形成的一棵2-d树。
(1)若命名树结点的类名为kdTNode,树的类名为kdTrce,关键码keyl的数据类型为T1,关键码key2的数据类型为T2,试写出2-d树的模板类结构定义,包括构造函数、复制构造函数、求树高、按给定值搜索、查找左子女、查找右子女、查找父结点、插人、删除等函数。此外,还要定义对树结点私有数据成员的存取函数(只要求写出函数的原型,不必给出代码实现)。
(2)基于上述定义,写出其中一个成员函数的实现代码:从根开始搜索关键码keyl和
key2与给定值vall和val2匹配的结点。函数的形式为:
若搜索成功,则函数返回true值,同时引用参数pt指向搜索到的结点,另引用参数pr指向结点*pt的父结点。此时,若树中只有一个结点,pr为NULL。
若搜索不成功或树为空,则函数返回false值,同时参数pt为NULL,在树非空时,pr则指向搜索失败前指针pt最后到达的结点;当树为空时,pr为NULL。
第1题
最佳二叉搜索树是(36)。
A.关键码个数最少的二叉搜索树
B.搜索时平均比较次数最少的二叉搜索树
C.所有结点的左子树都为空的二叉搜索树
D.所有结点的右子树都为空的二叉搜索树
第3题
A.关键码个数最少的二叉搜索树
B.搜索时平均比较次数最少的二叉搜索树
C.所有结点的左子树都为空的二叉搜索树
D.所有结点的右子树都为空的二叉搜索树
第4题
个不可能是在二叉搜索树中搜索到的序列?
(1)(2,252,401,398,330,344,397,363)
(2)(924,220,911,244,898,258,362,363)
(3)(925,202,911,240,912,245,363)
(4)(2,399,387,219,266,382,381,278,363)
第5题
设有一个关键码的输入序列(55,31,11,37,46,73,63,02,07):
(1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需进行的平衡旋转的类型及平衡旋转的结果
(2)计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
第6题
第7题
第8题
此题为判断题(对,错)。
第10题
此题为判断题(对,错)。
为了保护您的账号安全,请在“赏学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!