1、给出一棵树的逻辑结构T=(N,R),其中:
N={A,B,C,D,E,F,G,H,I,J,K}
R={r}
r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}
试回答下列问题:
(1)哪个是F的父结点?
(2)哪些是B的子孙?
(3)以结点C为根的子树的深度是多少?
(注:根的层数为0,独根树深度为0,高度为1,其他题目同样如此)
解析?
?答案: B EFGH 2
2、将下图的二叉树转换为对应的森林,按照后根次序列出其结点。
解析:
转化后的森林如下所示:
参考:?
后根深度优先遍历森林 = 按中序法遍历对应的二叉树(左根右)
后根次序列 :EBFCDAIJKHGL
3、对于以下等价类,采用“加权合并规则”(也称“重量权衡合并规则”),进行并查运算,给出最后父节点索引序列。
8-9 3-2 7-4 5-9 6-1 8-6 7-3 2-5 8-0 //右指向左
注意:当合并大小相同的两棵树的时候,将第二棵树的根指向第一棵树的根;根节点的索引是它本身;数字之间用空格隔开。
解析:(合并时,结点数少的指向结点数多的)
4、若一个具有N个顶点,K条边的无向图是一个森林(N>K且2K>=N),则该森林有多少棵树?
解析:
在一棵树中,结点比边多一个,即结点比边多几个就有几棵树。
答案: N-K
5、一棵完全三叉树,下标为121的结点在第几层?(注:下标号从0开始,根的层数为0)
解析:
第h层的下标是从(3^h-1)/2到(3^(h+1)-1)/2-1,
第5层的下标是从121到363。
答案: 5
?