树、二叉树概念(+堆的实现)-Toy模板网

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

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

欢迎来到我的：世界

希望作者的文章对你有所帮助，有不足的地方还请指正，大家一起学习交流 !

前言

新的篇章的开始，是见证我的这一刻；
噢，这美好的一天；
是需要你来见证的!
我最亲爱的老铁们！！😊

1.树的概念

要知道二叉树首先要知道树这非线性数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

树的结构：

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

则关于树较为重要的概念：
节点的度：一个节点含有的子树的个数称为该节点的度；如图R节点的度为3；
叶节点或终端节点：度为0的节点称为叶节点；非终端节点或分支节点：度不为0的节点；如图j、k、e… 等为叶节点；
非终端节点或分支节点：度不为0的节点；如图中a、d、b…等为非终端节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如图中：R是a的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如图：b是R的子节点；
树的度：一棵树中，最大的节点的度称为树的度；如图：该树的度为3；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；如图：该树结构有4层；
树的高度或深度：树中节点的最大层次；如图：该树的高度是4；
节点的祖先：从根到该节点所经分支上的所有节点；如图：R是所有节点的祖先；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如图：所有节点都是R节点的子孙；
森林：由m（m>0）棵互不相交的树的集合称为森林；
兄弟节点：具有相同父节点的节点互称为兄弟节点；如图：a和b就是兄弟节点；
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如图：e和f就是堂兄弟节点；

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言
非树种结构可以叫做：图

2.二叉树概念及结构

二叉树（Binary tree）是树形结构的一个重要类型，是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
简述特点：

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

2.1数据结构中的二叉树

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

2.2两个特殊的二叉树

1.满二叉树: 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
2.完全二叉树： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。
树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

这两种二叉树的特殊结构：要注意的是满二叉树是一种特殊的完全二叉树。

2.2.1满二叉树结点和层数的关系

我们既然已经知道满二叉树是一种怎么的结构，那试着来分析一下满二叉树的总节点和层数的关系吧：

假设满二叉树的总节点有N个，层数为H个；

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

所以可以得出满二叉树总节点数:
N = 2^0+ 2^1+ 2^2+....+ 2^(H-2)+ 2^(H-1)
运用错位相减法：

得：N= 2^H - 1
所以来一题检测一下我们的学习：
知道一个满二叉树有7层，那一共有多少个节点？
答案可以是呼之欲出：N=2^7 -1 =128-1= 127;
当然这道题比较简单，那如果知道节点数求层数呢？
化简一下：
h=Log2(n+1).
(ps：Log2(n+1)是log以2为底，n+1为对数)

2.2.2完全二叉树高度为H节点范围

分析完满二叉树，下来我们来分析下完全二叉树：
完全二叉树有个概念：假设它的高是h，代表着它前h-1层都是满的，且是从左到右连续的；
树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言
那如果问：有一个完全二叉树，其高为h,那么其节点的个数范围是多少呢？
可以很容易想到：最大的范围是他就是一个满二叉树的时候，节点为2^h -1
那其最小范围就是满了前h-1层，然后再加来一个节点喽：
满前h-1层个数是：2^(h-1) -1 ，然后还要再加一个节点：
其最小范围是：2^(h-1)

所以若有一个完全二叉树，其高为h，其节点个数的范围是：
[2^(h-1) , 2^h -1]

3.二叉树的存储结构

二叉树一般可以使用两种存储结构，一种顺序结构，一种链式结构。在该篇文章就单单介绍一下顺序结构的存储方式吧！

3.1顺序存储

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

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

3.2二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点；
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h -1个节点；
对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1;
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为底，n+1为对数)
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，i位置节点的双亲序号：(i-1)/2；
i=0，i为根节点编号，无双亲节点;
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子;
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子;

这里还是画图解释一下：

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

4.堆的概念即结构

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。

堆可以分为最大堆和最小堆两种类型：

最大堆：每个节点的值都大于等于其子节点的值。
最小堆：每个节点的值都小于等于其子节点的值。

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

注意：其中储存结构是在内存当中真正存的结构，而逻辑结构是想象出来的；

下面咱们来加深一下大堆，小堆的印象吧：

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选项：100,60,70,50,32,65
树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言
很明显这就是一个大堆；
剩下的我也写出来啦：

4.堆的实现

4.1向上调整算法

实现堆：
我们可以知道堆的存储结构类似一个数组,插入数据怎么插入呢？当然选择尾插如，因为在数组结构中尾插的效率比较好；

但光插入就好了么？
插入也是可以分好几种情况的：
假如有一组数组：10,15,56,25,30,70
1.保持不动的情况：假如要插入的是90，插入后满足小堆存储，所以不需要移动；
树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

2.只移动一步的情况：假如插入的是50，就不满足堆的性质了，影响的是插入该子节点的祖先，所以就需要和他的祖先进行pkpk了，与之父节点比较，小的到上面去；

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

3.移动许多步的情况；假如插入5，那就需要移动许多步了：

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言
这些操作就是向上调整，这怎么实现向上调整Adjustup函数：

void Adjustup(HEAPTypedef* pd,int child )
{
	int parent = (child - 1) / 2;
	//直到子节点为根节点或者小于0，这样其就没有父节点了
	while (child > 0)
	{
	//这是实现小堆，如果想实现大堆就只需要将大于号改成小于号
		if (pd[parent] > pd[child])
		{
			swap(&pd[parent],&pd[child]);//交换
			//重新找父节点节点
			child = parent;
			parent= (child - 1) / 2;
		}
		else
			break;
	}
}

4.2向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {60,25,56,28,30,70,60,30};

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

意思就是：这是个小堆，有不满足小堆的性质的元素，就需要将不满足的元素往下移动，移动到合适的位置，但是该怎么移呢？

往下移动就是本节点与其子节点交换喽，但是和那个子节点交换呢，其实就是和两个子节点较小的那个节点：

树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言

实现Adjustdown向下调整

void Adjustdown(HEAPTypedef* a, int n, int parent)
{
	int child = parent * 2 + 1;//找到孩子，假设这个其左子节点就是更小的那个
	while (child < n)
	{
		//寻找小的那个孩子，如果右子节点小于左子节点就让child赋值为右子节点
		if (child+1< n  && a[child + 1] < a[child])
		{
			child++;//该一步将左子节点变成右子节点
		}
		//继续往下找
		if (a[child] < a[parent])
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

别忘了要实现上面两个函数还需要一个交换函数swap
实现：

void swap(HEAPTypedef*e1, HEAPTypedef*e2)
{
	HEAPTypedef tem = *e1;
	*e1 = *e2;
	*e2 = tem;
}

定义堆
堆的底层是一个数组，那就可以类似于顺序表定义；

typedef int HEAPTypedef;
//顺序表实现堆(完全二叉树)
typedef struct Heap
{
	HEAPTypedef* a;
	int size;//有效长
	int capacity;//总长

}Heap;

初始化堆HeapInt
我选择的是将堆都置空，在后续HeapPush插入的操作中在去开辟空间去存储；

void HeapInt(Heap* pd)
{
	assert(pd);
	pd->a = NULL;
	pd->capacity = 0;
	pd->size = 0;
}

清除堆Destory

void Destory(Heap* pd)
{
	assert(pd);

	free(pd->a);
	pd->a = NULL;
}

插入操作HeapPush实现：
首先进入插入操作判断是否要扩容，然后尾插进来，每插入进来一位都需要向上调整，需要一个Adjustup函数向上调整；

void HeapPush(Heap* pd, HEAPTypedef child)
{
	assert(pd);

	//增容
	if (pd->size == pd->capacity)
	{
		int newcapacity = pd->capacity == 0 ? 4 : 2 * pd->capacity;
		HEAPTypedef* tem = (HEAPTypedef* )realloc(pd->a,sizeof(HEAPTypedef)*newcapacity);
		if (tem == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		pd->capacity = newcapacity;
		pd->a = tem;

	}

	//尾插
	pd->a[pd->size] = child;
	pd->size++;

	//每尾插入一个就往上调整，这样才能保证堆的性质
	Adjustup(pd->a,pd->size-1);

}

打印Heapprint

void Heapprint(Heap* pd)
{

	int i = 0;
	for (i=0;i<pd->size;i++)
	{
		printf("%d ", pd->a[i]);
	}

	printf("\n");
}

删除Heappop

对于堆来说，删除根的意义是最大的，为什么？下面我给你解释：

那如果我们要删除根，怎么删呢？
肯定不能直接将后面的数据往前挪，这样的话会违反堆的性质，举例来看：
上面给了一组数据：10,15,56,25,30,70
他是小堆，挪完后：15,56,25,30,70，那么请问这还是小堆么？
显然他直接打乱了整个堆，导致堆发生变化，堆不再是堆了；

说了那么多，到底怎么删除根节点呢？

我们可以将根节点和最后一个节点进行交换，然后删除最后一个数据，再进行向下调整算法。
树、二叉树概念(+堆的实现),java,数据库,开发语言,c++,数据结构,c语言
实现：

void Heappop(Heap* pd)
{
	assert(pd);
	assert(pd->size > 0);

	swap(&pd->a[0], &pd->a[pd->size - 1]);
	pd->size--;
	Adjustdown(pd->a,pd->size,0);
}

还需要用来查看堆顶的函数：HeapTop

HEAPTypedef HeapTop(Heap* pp)
{
	assert(pp);

	return pp->a[0];
}

还有判断是否为空：HeapEmpty

bool HeapEmpty(Heap* pd)
{
	assert(pd);

	return pd->size == 0;
}

堆的代码实现：

Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>


typedef int HEAPTypedef;
//顺序表实现堆(二叉树)
typedef struct Heap
{
	HEAPTypedef* a;
	int size;//有效长
	int capacity;//总长

}Heap;

//初始化
void HeapInt(Heap* pd);
//清除
void Destory(Heap* pd);
//插入
void HeapPush(Heap* pd, HEAPTypedef x);
//打印
void Heapprint(Heap* pd);
//尾删
void Heappop(Heap* pd);
//交换
void swap(HEAPTypedef* e1, HEAPTypedef* e2);
//堆顶
HEAPTypedef HeapTop(Heap* pp);
//判空
bool HeapEmpty(Heap* pd);
//向下调整算法
void Adjustdown(HEAPTypedef* a, int n, int parent);
//向上调整算法
void Adjustup(HEAPTypedef* pd, int child);

Heap.c

#include "Head.h"

void HeapInt(Heap* pd)
{
	assert(pd);
	pd->a = NULL;
	pd->capacity = 0;
	pd->size = 0;
}


void Destory(Heap* pd)
{
	assert(pd);

	free(pd->a);
	pd->a = NULL;

}

void swap(HEAPTypedef*e1, HEAPTypedef*e2)
{
	HEAPTypedef tem = *e1;
	*e1 = *e2;
	*e2 = tem;

}

void Adjustup(HEAPTypedef* pd,int child )
{
	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (pd[parent] < pd[child])
		{
			swap(&pd[parent],&pd[child]);
			child = parent;
			parent= (child - 1) / 2;
		}
		else
			break;
	}
}



void HeapPush(Heap* pd, HEAPTypedef child)
{
	assert(pd);

	//增容
	if (pd->size == pd->capacity)
	{
		int newcapacity = pd->capacity == 0 ? 4 : 2 * pd->capacity;
		HEAPTypedef* tem = (HEAPTypedef* )realloc(pd->a,sizeof(HEAPTypedef)*newcapacity);
		if (tem == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		pd->capacity = newcapacity;
		pd->a = tem;

	}

	//尾插
	pd->a[pd->size] = child;
	pd->size++;

	//往上寻找
	Adjustup(pd->a,pd->size-1);

}

void Adjustdown(HEAPTypedef* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//寻找小的那个孩子
		if (child+1< n  && a[child + 1] > a[child])
		{
			child++;
		}
		//继续往下找
		if (a[child] > a[parent])
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void Heapprint(Heap* pd)
{

	int i = 0;
	for (i=0;i<pd->size;i++)
	{
		printf("%d ", pd->a[i]);
	}

	printf("\n");
}

void Heappop(Heap* pd)
{
	assert(pd);
	assert(pd->size > 0);

	swap(&pd->a[0], &pd->a[pd->size - 1]);
	pd->size--;

	Adjustdown(pd->a,pd->size,0);
}


HEAPTypedef HeapTop(Heap* pp)
{
	assert(pp);

	return pp->a[0];
}

bool HeapEmpty(Heap* pd)
{
	assert(pd);

	return pd->size == 0;
}