渝粤教育江苏开放大学2023年秋数据结构与算法形成性考核作业三(1)

江苏开放大学2023年秋数据结构与算法形成性考核作业三

文档预览

文本预览

总页数：约7页 总字数：约3493字

江苏开放大学实验报告

学 号:

姓 名:

课程代码: 060220

课程名称:

数据结构与算法

评阅教师:

许小媛

实验名称：树和二叉树的应用

一、实验目的及要求

1. 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；

2. 重点掌握二叉树的生成、遍历及求深度等算法；

3. 掌握哈夫曼树的含义及其应用。

4. 掌握运用递归方式描述算法及编写递归 C 程序的方法，提高算法分析和程序设计能力。

二、实验内容

在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占 4

个字节，每个信息域占 k 个字节。试问：对于一棵有 n 个结点的二叉树，且在顺序存储结构中最后一个节点

的下标为 m，在什么条件下顺序存储结构比三叉链表更节省空间？

三、实验设备及环境

安装 C 语言编译环境。

四、实验步骤（功能实现的核心代码及说明，包括数据库表）

在顺序存储结构中，每个节点包含了除了指针域之外的所有信息，而在三叉链表中，每个节点包含了指

向父节点、左子节点和右子节点的指针域，以及除了指针域之外的信息。

对于一棵有 n 个结点的二叉树，在顺序存储结构中最后一个节点的下标为 m 时，首先计算二叉树中所有

节点所需的总空间。顺序结构所需的总空间为：

```

1

总空间 = n * (k + 4)

```

三叉链表结构所需的总空间为：

```

总空间 = n * (k + 12)

```

要顺序存储结构比三叉链表更节省空间，即顺序结构所需的总空间小于三叉链表结构所需的总空间。因

此，我们需要找到这样的条件：

```

n * (k + 4) < n * (k + 12)

```

化简得到：

```

4n < 8n

```

即：

```

n > 0

```

根据上面的推导，当二叉树的节点数量大于 0 时，顺序存储结构将比三叉链表结构更节省空间。

需要注意的是，这是一个理论上的分析，实际应用中，还需要考虑到具体的实现细节和操作的复杂度。

2

总页数：7