【C++】树和二叉树的实现（下）

本篇博客给大家带来的是用C++语言来实现数据结构树和二叉树的实现！

🐟🐟文章专栏：数据结构

🚀🚀若有问题评论区下讨论，我会及时回答

❤❤欢迎大家点赞、收藏、分享！

今日思想：你现在的懒惰将来你会买单的！

         续接上文【C++】树和二叉树的实现（上）-CSDN博客

 一、二叉树的实现方法

         在上文我们知道二叉树有两种方法（顺序结构和链式结构），顺序结构实现二叉树的底层是数组，那么在现实生活中我们把堆（一种二叉树）使用顺序结构来存储，最后二叉树的实现方法有：堆的初始化、堆的销毁、向上调整、向下调整、入堆、出堆、判断堆是否为空、取堆顶数据。接下来我们一一实现。

        1、堆的初始化

        既然堆的底层是数组，那么我们先确定堆的结构体。

代码实例：

//Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效数据个数int capacity;//空间大小
}HP;

堆的初始化：

//Heap.h
//堆的初始化
void HPInit(HP* php);

//Heap.c
#include"Heap.h"
//堆的初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}

         2、堆的销毁

        堆的销毁和初始化差不多这里不展开说。

代码实例：

//Heap.h
//堆的销毁
void HPDestory(HP* php);

//堆的销毁
void HPDestory(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

        3、向上调整

        我们有个堆假设是小堆（如图），如果我们在size位置插入0，那么这样就不符合小堆的结 构，所以我们要向上调整。上偏文章我们可知二叉树的特点：如果 i 是孩子下标，父结点下标等于（i-1）/ 2，假设 i 为父结点下标那么右孩子下标等于2i+2，左孩子等于2i+1。

        思路：通过插入数据的下标求父结点的下标然后对比父结点和孩子结点的大小来判断是否符合小堆结构，不符合就交换。

代码实例：

//Heap.h
//向上调整
void AdjustUp(HPDataType* arr, int child);
//交换两个值
void Swap(HPDataType* x, HPDataType* y);

//Heap.c
//交换两个值
void Swap(HPDataType* x, HPDataType* y)
{int tmp = *x;*x = *y;*y = tmp;//向上调整
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){//小堆： <//大堆： >if (arr[child] < arr[parent]){swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

        4、入堆

        入堆的思想和向上调整差不多，只要我们往数组的size位置插入数据，首先我们要判断空间是否满了，如果满了申请新的空间，没有就插入然后向上调整，如果是小堆就要返回小堆的结构。

代码实例：

//Heap.h
//入堆
void HPPush(HP* php, HPDataType x);

//Heap.c
//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->size == php->capacity){//增容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//空间足够直接插入php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);++php->size;
}

5、向下调整

        向下调整和出堆联动，大家可以先看下面的出堆，根据出堆我们把堆顶和最后的数据交换，假设这是个大堆，而10在堆顶（如图），这不符合大堆的结构，我们需要向下调整。

思路：根据10的下标来找10的右孩子和左孩子，左孩子和右孩子比较谁大和父结点交换，交换完之后再让parent来到child的位置，child来到25的位置然后重复操作。

代码实例：

//Heap.h
//向下调整
void AdjustDown(HPDataType* arr, int parent, int n);

//Heap.c
//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){//大堆： <//小堆： >if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//大堆：>//小堆：<if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}

6、出堆与判断堆是否为空

        出堆其实就是把堆顶的数据和最后一个数据交换，然后size--；到时候如果插入新数据就可以覆盖最后的数据，size--之后要向下调整保证符号堆（大堆或者小队）的结构。

代码实例：

//Heap.h
//出堆
void HPPop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);

//Heap.c
//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//出堆
void HPPop(HP* php)
{assert(!HPEmpty(php));swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;//向下调整AdjustDown(php->arr, 0, php->size);
}

 7、堆的打印

        有时候我们需要打印堆来看看是否符号自己的预期。

代码实例：

//Heap.h
//堆的打印
void HPPrint(HP* php);

//Heap.c
//堆的打印
void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}

8、取堆顶数据

        取堆顶的数据就是数组下标为0的数据。

代码实例：

//Heap.h
//取堆顶数据
HPDataType HPTop(HP* php);

//Heap.c
//取堆顶数据
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

9、完整的代码

//Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效数据个数int capacity;//空间大小
}HP;//堆的初始化
void HPInit(HP* php);
//堆的销毁
void HPDestory(HP* php);
//堆的打印
void HPPrint(HP* php);
//交换两个值
void Swap(HPDataType* x, HPDataType* y);
//向上调整
void AdjustUp(HPDataType* arr, int child);
//向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
//入堆
void HPPush(HP* php, HPDataType x);
//出堆
void HPPop(HP* php);
//取堆顶数据
HPDataType HPTop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);

//Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
//堆的初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
//堆的销毁
void HPDestory(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}
//交换两个值
void Swap(HPDataType* x, HPDataType* y)
{int tmp = *x;*x = *y;*y = tmp;
}
//向上调整
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){//小堆： <//大堆： >if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->size == php->capacity){//增容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//空间足够直接插入php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);++php->size;
}
//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){//大堆： <//小堆： >if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//大堆：>//小堆：<if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//出堆
void HPPop(HP* php)
{assert(!HPEmpty(php));swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;//向下调整AdjustDown(php->arr, 0, php->size);
}
//堆的打印
void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}
//取堆顶数据
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

完！！