Tasks.Data_Structure

数据结构 第五次课堂作业

题目

第七章练习题 4

设二叉树 bt 的一种存储结构如表7.7所示。其中， bt 为树根结点指针， lchild， rchild 分别为结点的左，右孩子指针域，在这里使用结点编号作为指针域值，0表示指针域值为空；data为结点的数据域。请完成下列各题：

表7.7	1	2	3	4	5	6	7	8	9	10
lchild	0	0	2	3	7	5	8	0	10	1
data	j	h	f	d	b	a	c	e	g	i
rchild	0	0	0	9	4	0	0	0	0	0

1. 画出二叉树 bt 的树形表示。
2. 写出按先序、中序和后序遍历二叉树 bt 所得到的结点序列。
3. 画出二叉树 bt 的后序线索树 （不带头结点）。

第七章练习题 15

设二叉树中的每个结点值为单个字符，采用二叉链存储结构存储。 设计一个算法，求二叉树 b 中第k层上的叶子结点个数。

第七章练习题 17

假设二叉树中的每个结点值为单个字符，采用二叉链存储结构存储。 设计一个算法，采用先序遍历方法求二叉树 b 中值为 x 的结点的子孙结点，假设值为x的结点是唯一的。

验证二叉树合法性

给定一个二叉树 bt ，检验其中是否存在一个节点拥有两个父节点。

测试数据说明：

• 第1行: n m 表示有 n个节点 m条边。 设二叉树的节点编号为 1, 2, … ,n。 约定1号节点为根节点。
• 第2行到第1+m行：a b 表示节点编号为 a 的节点是节点编号为 b 父节点。

一些测试数据：

3 2
1 2
2 3

3 3
1 2
2 3
1 3

提交

1. 将作业打包为压缩文件，如 zip 格式。
2. 压缩文件命名为你的学号， 如 2018302114514.zip 。
3. 将压缩文件以附件形式发送到邮箱 DS_Task5 # superexercisebook.com
4. 如果一切顺利，你将会收到一个投递成功回执。