二叉树顺序结构及实现

发表于

「这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战」

💦 二叉树的顺序结构

1
2
3
scss复制代码普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。
而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆 (一种二叉树) 使用顺序结构的数组来存储。
需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

  ❓ 操作系统和数据结构这两门学科中都有栈和堆的概念，如何区分 ❔

在这里插入图片描述

💦 堆的概念及结构

如果有一个关键码的集合K = {k₀, k₁, k₃,…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足：Ki <= K2*i+1 且 Ki <= K2*i+2 (Ki >= K2*i+1 且 Ki >= K2*i+2) i = 0，1，2…，则称为小堆 (或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

    ❗ 堆的性质 ❕

      ▶ 堆中某个节点的值总是不大于或不小于其父节点的值；

      ▶ 堆总是一棵完全二叉树；

    —————————————Cut—————————————–

    ❗ 大(根)堆和小(根)堆 ❕

      ▶ 大(根)堆，树中所有父亲都大于或者等于孩子，且大堆的根是最大值；

      ▶ 小(根)堆，树中所有父亲都小于或者等于孩子，且小堆的根是最小值；

在这里插入图片描述

💦 堆的概念选择题

1、下列关键字序列为堆的是（ ）

A. 100, 60, 70, 50, 32, 65

B. 60, 70, 65, 50, 32, 100

C. 65, 100, 70, 32, 50, 60

D. 70, 65, 100, 32, 50, 60

E. 32, 50, 100, 70, 65, 60

F. 50, 100, 70, 65, 60, 32

📝 分析：根据堆的概念分析，A 选项为大根堆；

2、注，请理解下面堆应用的知识再做。已知小根堆为 8, 15, 10, 21, 34, 16, 12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（ ）

A. 1

B. 2

C. 3

D. 4

📝 分析：

此题考查的是建堆的过程
在这里插入图片描述

所以选择 C 选项

3、注，请理解下面堆应用的知识再做。一组记录排序码为 (5 11 7 2 3 17)，则利用堆排序方法建立的初始堆为（ ）

A. (11 5 7 2 3 17)

B. (11 5 7 2 17 3)

C. (17 11 7 2 3 5)

D. (17 11 7 5 3 2)

E. (17 7 11 3 5 2)

F. (17 7 11 3 2 5)

📝 分析：

此题考查的是堆排序建堆的过程

根据下面堆排序的过程分析，选择 C 选项

在这里插入图片描述

4、、注，请理解下面堆应用的知识再做。最小堆 [0, 3, 2, 5, 7, 4, 6, 8]，在删除堆顶元素0之后，其结果是（ ）

A. [3，2，5，7，4，6，8]

B. [2，3，5，7，4，6，8]

C. [2，3，4，5，7，8，6]

D. [2，3，4，5，6，7，8]

📝 分析：

此题考查的是 Pop 堆顶后，重新建堆的变化

在这里插入图片描述

所以选择 C 选项

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%