初识二叉树以及堆的简单实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了初识二叉树以及堆的简单实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一:什么是树

【1】树的概念

【2】树的另外几个重要概念

【3】树的几种表示方法

二:什么是二叉树

【1】概念以及特点

【2】两种特殊的二叉树

【3】二叉树的性质

【4】二叉树的两种存储方式

三:堆的实现

一:什么是树

【1】树的概念

我们前面所学的顺序表，链表都属于线性结构，而树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

图解：

(1) 树有一个特殊的节点，叫根节点，在图中为结点A。

(2)除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。

(3)父子结点：例如A是B,C,D的父节点，而E，F是B的子节点。

(4)叶结点：没有子节点的结点，例如E,F,C,G,H。

注意：树的子树是不相交的，除了根结点以外别的结点有且只有一个父节点。

【2】树的另外几个重要概念

图解：

(1)节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6

(2)非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点

(3)兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点

(4)树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6

(5)节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

(6)树的高度或深度：树中节点的最大层次；如上图：树的高度为4

(7)节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

(8)子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

(9)森林：由m(m>0)棵互不相交的多颗树的集合称为森林。

【3】树的几种表示方法

(1)利用顺序表存子节点的地址(结构复杂)

(2) 已经说明了树的度(最大结点的度)，设置一个指针数组来存储子节点的地址

(3)结构体数组存储

(4)左孩子右兄弟表示法(比较常用，结构也比较简单，逻辑相对清晰)

二:什么是二叉树

【1】概念以及特点

概念:

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

特点:

1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

【2】两种特殊的二叉树

1. 满二叉树：

所有叶子节点都在最后一层

所有分支节点都有两个孩子

2. 完全二叉树：

假设这个二叉树有N层，前N-1层必须满

最后一层可以不满，但是必须左向右连续

【3】二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1。
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1。
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=LogN。

【4】二叉树的两种存储方式

(1)顺序结构存储(数组)

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

(2)链式结构存储

用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

链式结构又分为二叉链和三叉链，目前一般都是二叉链，红黑树等高阶数据结构会用到三叉链。

三:堆的实现

堆是用数组实现的二叉树，并且一般用来实现完全二叉树。

堆分为大堆和小堆

大堆：父亲>=孩子

小堆：孩子>=父亲

本文实现的是大堆

堆的实现和顺序表类似，这里就不展开细讲，只讲主要的接口实现。

附上顺序表链接:https://blog.csdn.net/2301_76269963/article/details/129352041?spm=1001.2014.3001.5501

【1】插入数据

(1)判断扩容，和顺序表一致。

(2)存储数据，和顺序表一致。

(3)在进行数据插入后我们要保证插入以后还是大堆，就必须进行父子关系的调整。

在考虑调整之前，我们观察一下父亲下标和孩子下标的关系

我们可以发现这样一个规律

父亲下标=（孩子下标-1）/2。

我们根据这个规律来设计调整函数，如果要插入的数据大于父亲，就调换两者，一直到小于父亲或者成为了根部节点。

因为后续的删除也需要进行交换调整，我们可以将交换单独封装成函数HeapSwap( )。

代码：

【2】删除数据（堆排序的基础）

基础思路：

(1)堆的数据删除要求的是删除根部数据。

(2)要注意不能直接和顺序表一样向前覆盖，这样会破坏原堆的结构。

图解：

(3)我们既要删除掉原根部数据，又要进行调整。

删除：我们可以将根部和最后的一片叶子进行交换，然后直接将size(有效数据个数)减1.

图解：

调整：从下标0开始向下调整，如果孩子大于父亲就进行交换，一直到比两个孩子都大或者已经调整到了叶子就结束，每次进行判断前先比较两个孩子谁比较大，防止破坏大堆的结构，较大的孩子与父亲进行交换，然后迭代。

图解：

代码：

全部代码：

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;
}HP;
//初始化
void HeapInit(HP* hp);
//销毁
void HeapDestory(HP* hp);
//交换函数
void HeapSwap(int* p1, int* p2);
//判空函数
bool HeapEmpty(HP* hp);
//调整函数
void AdjustUp(HPDataType* a,int child);
//向下调整，n是有效个数
void AdjustDown(HPDataType* a, int n, int parent);
//插入数据
void HeapPush(HP* hp, HPDataType x);
//打印数据
void HeapPrint(HP* hp);
//删除数据
void HeapPop(HP* hp);

Heap.c(接口实现)

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//初始化
void HeapInit(HP* hp)
{
	//断言，不能传空的结构体指针
	assert(hp);
	hp->a = NULL;
	//初始化size和容量都为0
	hp->size = hp->capacity = 0;
}

//销毁
void HeapDestory(HP* hp)
{
	free(hp->a);
	hp->size = hp->capacity = 0;
}

//交换函数
void HeapSwap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//判空函数
bool HeapEmpty(HP* hp)
{
	return hp->size == 0;
}

//调整函数
//向上调整
void AdjustUp(HPDataType* a, int child)
{
	//断言，不能传空指针
	assert(a);
	//找到父结点的下标
	int parent = (child - 1) / 2;
	//循环，以child到树根为结束条件
	while (child > 0)
	{
		//如果父结点比child下，交换并更新
		if (a[child] > a[parent])
		{
			HeapSwap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		//如果父结点比child大，跳出循环
		else
		{
			break;
		}
	}
}
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	//默认左孩子最大
	int child = parent * 2 + 1;
	//当已经调整到超出数组时结束
	while (child<n)
	{
		//找出两个孩子中大的一方
		//考虑右孩子不存在的情况
		if (child+1<n&&a[child + 1] > a[child])
		{
			//如果右孩子大，child加1变成右孩子
			child++;
		}
		//如果父亲比大孩子小，进行调整，否则跳出
		if (a[child] > a[parent])
		{
			HeapSwap(&a[child], &a[parent]);
			//迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//插入数据
void HeapPush(HP* hp, HPDataType x)
{
	if (hp->size == hp->capacity)
	{
		//判断扩容多少
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		//扩容
		HPDataType* tmp =
			(HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		//更新
		hp->capacity = newcapacity;
		hp->a = tmp;
	}
	//存储数据
	hp->a[hp->size] = x;
	hp->size++;
	//进行调整
	AdjustUp(hp->a, hp->size-1);
}

//打印数据
void HeapPrint(HP* hp)
{
	//断言，不能传空的结构体指针
	assert(hp);
	int i = 0;
	for (i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

//删除数据
void HeapPop(HP* hp)
{
	//断言，不能传空的结构体指针
	assert(hp);
	//如果为空，不能删除，避免数组越界
	assert(!HeapEmpty(hp));
	//不为空，先交换根和最后一片叶子，然后size减1
	HeapSwap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

text.c(测试)

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

void text1()
{
	HP hp;
	HeapInit(&hp);
	HPDataType a[] = { 70,30,56,25,15,10.85,79};
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);
	}
	HeapPrint(&hp);
	HeapPop(&hp);
	HeapPrint(&hp);
	HeapDestory(&hp);
}

int main()
{
	text1();
}

初识二叉树以及堆的简单实现文章来源地址https://www.toymoban.com/news/detail-407323.html