数据结构第六章作业及答案11页.ppt

1
数据结构第六章作业
1、已知一棵树边的集合为{<I,M>,<I,N>,<E,I>,
<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,
<H,L>,<C,H>,<A,C>},请画出这棵树,并回答下列
问题:
(1)哪些是叶子结点?
(2)哪些是结点G的双亲?
(3)哪些是结点G的祖先?
(4)哪些是结点E的子孙?
(5)树的深度是多少?
2、(1)二叉树与树之间有何区别?
(2)一棵度为2的树与二叉树有何区别?
2
3、试分别画出具有3个结点的树和3个结点的二叉树
的所有不同形态。
4、对右图所示的二叉树求出
以下的遍历序列:
(1)先序序列
(2)中序序列
(3)后序序列
5、假设一棵二叉树的先序序列为 EBADCFHGIKJ 和
中序序列为 ABCDEFGHIJK。请画出该树,并给
出后序序列。
6、假设一棵二叉树的中序序列为 DCBGEAHFIJK和
后序序列为 DCEGBFHKJIA 。请画出该树,并给
出先序序列。
A
B
C
D
G
E
F
H
3
7、将以下森林转换成二叉树。
C
A
B
F
G
E
D
K
J
L
I
H
4
8、画出和下列二叉树相应的森林。
(a) (b) (c) (d) (e)
A
B
C
A
C
B
A
C
B
A
H
D
G
B
A
F
C
I
K
E
J
M
5
第六章作业解答
1、(1) M、N、D、L、F、J、K是叶子结点
(2) C是结点G的双亲
(3) A、C是结点G的祖先
(4) I、M、N是结点E的子孙
(5) 树的深度是5
2、(1)二叉树与树的区别:
二叉树的一个结点至多有2个子树,树则不然;
二叉树的一个结点有左、右之分,而树则没有此要求
(2)一棵度为2的树有2个分支,没有左、右之分,
一棵二叉树也可以有2个分支,但有左、右之分,
且左、右不能交换。
3、具有3个结点的树的形态为:
6

有3个结点的二叉树的所有形态为:


7
4、解:
(1)先序序列为:ABDGCEFH
(2)中序序列为:DGBAECHF
(3)后序序列为:GDBEHFCA
5、后序序列为:ACDBGJKIHFE
6、先序序列为:ABCDGEIHFJK
E
B
D
A
C
F
H
I
G
K
J
A
B
C
G
D
E
I
H
J
F
K
8
7、解:转换后的二叉树为:
A
B
C
D
E
I
H
F
G
J
L
K
9
8、解:转换后的森林为:
A
C
A
B
B
A
C
(a)
(b)
(c)
A
B
C
(d)
(e)
A
B
C
F
I
M
K
D
G
H
J
E
神医嫡女最新章节:85/神医嫡女最新章节 0 仐摋一