AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】二叉树顺序实现（大堆）--＞赋源码

2024-08-08 95
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】二叉树顺序实现（大堆）--＞赋源码

前言

在前面的顺序表、链表、都是线性表。今天的所介绍的二叉树是一种非线性数据结构。

树的概念以及介绍

定义

树是一种非线性的数据结构，它由n（n>0）个有限结点组成一个具有层次关系的集合。

image.png

树的相关概念（类比人类血缘关系）

  • 结点的度：一个结点含有的子树的个数称为该结点的度。
  • 叶结点或终端结点：度为0的结点称为叶结点。
  • 非终端结点或分支结点：度不为0的结点。
  • 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点。
  • 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点。
  • 兄弟结点：具有相同父结点的结点互称为兄弟结点。
  • 树的度：一棵树中，最大的结点的度称为树的度。
  • 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
  • 树的高度或深度：树中结点的最大层次。
  • 堂兄弟结点：双亲在同一层的结点互为堂兄弟。
  • 结点的祖先：从根到该结点所经分支上的所有结点。
  • 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
  • 森林：由m（m>0）棵互不相交的树的集合称为森林

二叉树的概念

二叉树是树的一种特殊形式，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

满二叉树

满二叉树的定义

1.满二叉树是一种特殊的二叉树，它的特点是每一层的节点数都达到最大值，即每一层的节点数都恰好为2的幂次（除了最后一层以外）。

2.如果满二叉树的深度为k，那么它的节点总数为2^k - 1。在满二叉树中，除了最后一层的节点之外，其余每一层的节点都是完全填满的，而且最后一层的节点也是从左到右连续排列的

满二叉树性质
  1. 满二叉树的深度为k，节点总数为2^k - 1。
  2. 满二叉树的每一层的节点数都达到最大值，即每一层的节点数为2^(i-1)，其中i是层数。
  3. 满二叉树的叶子节点全部位于最后一层。
  4. 满二叉树的节点要么是叶子节点（度为0），要么是度为2的节点，不存在度为1的节点

如下图：

image.png

完全二叉树

完全二叉树的定义
  1. 除了最后一层外，其他每一层的节点数都达到最大数量，即该层的节点数等于2的幂减去1。
  2. 最后一层的节点都集中在最左边，并且右边的节点可以少，但不能有空位。
完全二叉树的性质

1.完全二叉树的节点编号从1开始，对于编号为i的节点，其左子节点的编号为2i，右子节点的编号为2i+1。

2.如果一棵完全二叉树有n个节点，那么它的深度大约为log2(n)+1。

3.完全二叉树的特点是叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。

image.png

二叉树的顺序实现

堆

堆的定义

堆是一种特殊的完全二叉树，它可以被视为一种特殊的顺序表。

堆的分类

堆的特点是父节点的值总是大于或小于其子节点的值，根据这个特点，堆可以分为大根堆和小根堆。在大根堆中，根节点的值是最大的，而在小根堆中，根节点的值是最小的。

二叉树的实现（本质：顺序表，形式：大根堆）

二叉树的功能

//初始化
void HeapInit(Heap* hp);
//扩容
void CheckCapacity(Heap* hp);
//插入数据
void HeapPush(Heap* hp, HPDataType x);
//删除数据
void HeapPop(Heap* hp);
//顶数据
HPDataType HeapTop(Heap* hp);
//大小
int HeapSize(Heap* hp);
//堆是否为空
bool HeapEmpty(Heap* hp);
//销毁
void HeapDestory(Heap* hp);

二叉树的定义以及初始化

定义
typedef int HPDataType;

typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}Heap;
初始化

本质就是顺序表，没有太大的变化，开辟初始空间。

//初始化
void HeapInit(Heap* hp)
{
  assert(hp);
  hp->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
  if (hp->a == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  hp->capacity = 4;
  hp->size = 0;
}

二叉树空间扩容

//扩容
void CheckCapacity(Heap* hp)
{
  assert(hp);

  if (hp->size == hp->capacity)
  {
    HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * hp->capacity * 2);
    if(tmp == NULL)
    {
      perror("malloc fail");
      return NULL;
    }
    hp->a = tmp;
    hp->capacity *= 2;
  }

}

二叉树的插入数据

数据从尾部插入，但是要保证大堆结构，我们调用函数 AdjustUp（向上调整）。

插入
//插入数据
void HeapPush(Heap* hp,HPDataType x)
{
  assert(hp);
  CheckCapacity(hp);

  hp->a[hp->size++] = x;

  AdjustUp(hp,hp->size-1);
}
AdjustUp（向上调整）

在这里，由于孩子结点和父亲结点的关系是：父亲 = （孩子-1）/ 2. （顺序表本质就是数组，首元素下标就是0）

如图：结点为4 父亲节点为 （4-1）/ 2 = 1。

0

1

2

3

4

5

6

DLeft...

DRight...

ELeft...

ERight...

FLeft...

FRihgt...

HLeft...

HRight...

如果发现，孩子节点大于父亲节点，进行交换。

//向上调整
void AdjustUp(Heap* hp, int child)
{
  assert(hp);
  int parent = (child - 1) / 2;
  while (child >= 0)
  {
    if (hp->a[child] > hp->a[parent])
    {
      Swap(&(hp->a[child]), &(hp->a[parent]));
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
Swap(交换)
//交换
void Swap(HPDataType* child, HPDataType* parent)
{
  HPDataType tmp = *child;
  *child = *parent;
  *parent = tmp;
}

二叉树数据的删除

在这展示的是首节点的删除，尾节点删除的意义不大

删除

删除操作是首节点，和尾节点进行互换，删除尾节点。

  • 保证了删除效率
  • 保证了堆的原始关系

由于尾结点互换到了头结点，需要进行AdjustDown（向下调整）

//删除数据
void HeapPop(Heap* hp)
{
  assert(hp);
  
  hp->a[0] = hp->a[hp->size - 1];
  hp->size--;

  AdjustDown(hp,hp->size);
}
AdjustDown（向下调整）

在这里，由于孩子结点和父亲结点的关系是：孩子 = 父亲*2 + 1.

如图：1. 孩子结点 5 = 2 * 2 +1

2. 孩子结点 6 = 2 * 2 + 1 +1

0

1

2

3

4

5

6

DLeft...

DRight...

ELeft...

ERight...

FLeft...

FRihgt...

HLeft...

HRight...

//向下调整
void AdjustDown(Heap* hp,int size)
{
  assert(hp);
  int parent = 0;
  int child = parent * 2 + 1;
  while (child < size)
  {
    if (hp->a[parent] < hp->a[child])
    {
      Swap(&hp->a[parent], &hp->a[child]);
      parent = child;
      child = parent * 2 + 1;

    }
    else
    {
      break;
    }
  }
}

二叉树顶数据

//顶数据
HPDataType HeapTop(Heap* hp)
{
  assert(hp);
  return hp->a[0];
}

二叉树大小

//大小
int HeapSize(Heap* hp)
{
  assert(hp);
  
  return hp->size;

}

二叉树是否为空

//堆是否为空
bool HeapEmpty(Heap* hp)
{
  assert(hp);

  return hp->size == 0;
}

二叉树销毁

//销毁
void HeapDestory(Heap* hp)
{
  free(hp->a);
  hp->a == NULL;

}

源码

Heap.h

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>


typedef int HPDataType;

typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}Heap;


//初始化
void HeapInit(Heap* hp);
//扩容
void CheckCapacity(Heap* hp);
//插入数据
void HeapPush(Heap* hp, HPDataType x);
//删除数据
void HeapPop(Heap* hp);
//顶数据
HPDataType HeapTop(Heap* hp);
//大小
int HeapSize(Heap* hp);
//堆是否为空
bool HeapEmpty(Heap* hp);
//销毁
void HeapDestory(Heap* hp);

Heap.c

#define _CRT_SECURE_NO_WARNINGS  1

#include "heap.h"


//初始化
void HeapInit(Heap* hp)
{
  assert(hp);
  hp->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
  if (hp->a == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  hp->capacity = 4;
  hp->size = 0;
}

//扩容
void CheckCapacity(Heap* hp)
{
  assert(hp);

  if (hp->size == hp->capacity)
  {
    HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * hp->capacity * 2);
    if(tmp == NULL)
    {
      perror("malloc fail");
      return NULL;
    }
    hp->a = tmp;
    hp->capacity *= 2;
  }

}

//交换
void Swap(HPDataType* child, HPDataType* parent)
{
  HPDataType tmp = *child;
  *child = *parent;
  *parent = tmp;
}

//向上调整
void AdjustUp(Heap* hp, int child)
{
  assert(hp);
  int parent = (child - 1) / 2;
  while (child >= 0)
  {
    if (hp->a[child] > hp->a[parent])
    {
      Swap(&(hp->a[child]), &(hp->a[parent]));
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }

}

//插入数据
void HeapPush(Heap* hp,HPDataType x)
{
  assert(hp);
  CheckCapacity(hp);

  hp->a[hp->size++] = x;

  AdjustUp(hp,hp->size-1);
}

//向下调整
void AdjustDown(Heap* hp,int size)
{
  assert(hp);
  int parent = 0;
  int child = parent * 2 + 1;
  while (child < size)
  {
    if (hp->a[parent] < hp->a[child])
    {
      Swap(&hp->a[parent], &hp->a[child]);
      parent = child;
      child = parent * 2 + 1;

    }
    else
    {
      break;
    }
  }
}

//删除数据
void HeapPop(Heap* hp)
{
  assert(hp);
  
  hp->a[0] = hp->a[hp->size - 1];
  hp->size--;

  AdjustDown(hp,hp->size);
}
//顶数据
HPDataType HeapTop(Heap* hp)
{
  assert(hp);
  return hp->a[0];
}
//大小
int HeapSize(Heap* hp)
{
  assert(hp);
  
  return hp->size;

}
//堆是否为空
bool HeapEmpty(Heap* hp)
{
  assert(hp);

  return hp->size == 0;
}

//销毁
void HeapDestory(Heap* hp)
{
  free(hp->a);
  hp->a == NULL;

}

test.c

#define _CRT_SECURE_NO_WARNINGS  1

#include "heap.h"



void Heaptest()
{
  Heap HP;
  HeapInit(&HP);
  HeapPush(&HP, 3);
  HeapPush(&HP, 5);
  HeapPush(&HP, 40);
  HeapPush(&HP, 70);
  HeapPush(&HP, 18);
  HeapPush(&HP, 25);

  while (!HeapEmpty(&HP))
  {
    printf("%d ", HeapTop(&HP));
    HeapPop(&HP);
  }

  HeapDestory(&HP);

}




int main()
{
  Heaptest();

  return 0;
}





关键词：
数据结构源码
数据结构二叉树
数据结构二叉树源码
数据结构堆源码
数据结构堆
chian-ocean
目录
相关文章
啦啦啦191
|
5月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架，涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口，逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变，包括数组+链表+红黑树优化，以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例，展示集合框架的应用价值，助你全面掌握相关知识，轻松应对面试与开发需求。
啦啦啦191
253 3
修己xj
|
8月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构，广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型（如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等）及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历，并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力，优化算法设计。
修己xj
240 10
算法系列之数据结构-二叉树
ephemerals__
|
8月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现（附源码）
在深入探讨了AVL树的原理和实现后，我们不难发现，这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题，还通过其独特的平衡机制，确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
ephemerals__
612 19
ephemerals__
|
8月前
|
数据库 C++
【数据结构进阶】红黑树超详解 + 实现（附源码）
本文深入探讨了红黑树的实现原理与特性。红黑树是一种自平衡二叉搜索树，通过节点着色（红/黑）和特定规则，确保树的高度接近平衡，从而实现高效的插入、删除和查找操作。相比AVL树，红黑树允许一定程度的不平衡，减少了旋转调整次数，提升了动态操作性能。文章详细解析了红黑树的性质、插入时的平衡调整（变色与旋转）、查找逻辑以及合法性检查，并提供了完整的C++代码实现。红黑树在操作系统和数据库中广泛应用，其设计兼顾效率与复杂性的平衡。
ephemerals__
1405 3
RossyYan
|
10月前
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
242 12
RossyYan
|
10月前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
186 10
RossyYan
|
10月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
356 3
三三是该溜子
|
11月前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
228 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
那年春天
|
12月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
257 59
hahaha无
|
5月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
96 0
栈区的非法访问导致的死循环(x64)

热门文章

最新文章

  • 1
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 2
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 3
    软考中级软件设计师专项-数据结构与算法上篇
  • 4
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
  • 5
    【数据结构与算法】数组应用4：多项式计算Java版
  • 6
    【算法数据结构Java实现】递归的简单剖析及时间复杂度计算
  • 7
    Activity 生命周期及其栈管理方式
  • 8
    【数据结构】笔记（一）
  • 9
    函数调用栈
  • 10
    栈的代码实现之数组方案
  • 1
    232.用栈实现队列，225. 用队列实现栈
    110
  • 2
    栈区的非法访问导致的死循环(x64)
    96
  • 3
    Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
    253
  • 4
    Redis设计与实现——数据结构与对象
    268
  • 5
    快速排序-数据结构与算法
    492
  • 6
    16.1k star! 只需要DDL就能一键生成数据库关系图！开源神器ChartDB让你的数据结构"看得见"
    1463
  • 7
    java实现队列数据结构代码详解
    207
  • 8
    Java 中 .length 的使用方法：深入理解 Java 数据结构中的长度获取机制
    670
  • 9
    线性数据结构详解
    193
  • 10
    为什么要学习数据结构与算法
    148

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云对象存储OSS收费标准：500G存储118元1年、