1. Toy模板网首页
  2. > Toy博客

【数据结构】非线性结构之树结构（含堆）

7月前 作者：是阿建吖! 分类：Toy博客 阅读(38) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】非线性结构之树结构（含堆）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

前言

前面的三篇文章已经将线性结构讲述完毕了，下面的文章将会为大家将讲点新东西：非线性结构中的树结构。萌新对这里的知识点相对陌生，建议反复观看！！
关于线性结构的三篇文章放在下面：
线性表之顺序表
线性表之链表
线性表之栈、队列

一、树的概念及结构

1. 树的概念及结构

树是一种非线性的数据结构，它是由n (n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

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

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言
注意：树结构中，子树之间不能相交，否则不能叫做树结构
【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

2. 树的相关概念

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

注意：这里使用 ▲ 标注的都是比较重要的概念

  • ▲节点的度:一个节点含有的子树的个数称为该节点的度;如上图: R 的为6
  • ▲叶节点或终端节点:度为0的节点称为叶节点;如上图:j、k、m、l!..等节点为叶节点
  • ▲非终端节点或分支节点:度不为0的节点;如上图:b、c、d、h…等节点为分支节点
  • ▲双亲节点或父节点:若一个节点含有子节点，则这个节点称为其子节点的父节点;如上图: R 是 b 的父节点
  • ▲孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;如上图: b 是 R 的孩子节点
  • 兄弟节点:具有相同父节点的节点互称为兄弟节点;如上图:a、b是兄弟节点
  • ▲树的度:一棵树中，最大的节点的度称为树的度;如上图:树的度为3
  • 节点的层次:从根开始定义起，根为第1层，根的子节点为第2层，以此类推;
  • ▲树的高度或深度:树中节点的最大层次;如上图:树的高度为4
  • 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:k、m互为堂兄弟节点
  • 祖先:从根到该节点所经分支上的所有节点╱如上图: A 是所有节点的祖先
  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是 R 的子孙
  • 森林:由m (m>0)棵互不相交的树的集合称为森林;

3. 树的表示

这里使用孩子兄弟表示法：根节点左指针指向孩子，右指针指向兄弟。

typedef int DataType;struct Node
{
	struct Node* firstChild1;	//第一个孩子结点
	struct Node* pNextBrother;  //指向其下一个兄弟结点
	DataType data;				//结点中的数据域
};

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言
实际中树有很多种表示方式如:双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

二、二叉树的概念及结构

1. 二叉树的概念

二叉树是一种特殊的树结构：

  • 节点的度最多为二
  • 由根节点连接着左子树和右子树构成（子树可以为空）

二叉树可以分为以下五种情况：

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言
每一颗二叉树都可以分为三个部分：根 、左子树、右子树。而子树还可以继续往后分。
【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

2. 程序员的吉祥物

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

3. 特殊的二叉树

满二叉树：对于满二叉树而言，它的每一层节点个数都会达到最大值( 叶子节点只能是最后一层的节点，除叶子节点外，其余的所以节点都含有左右孩子 ) 。
完全二叉树：对于完全二叉树而言，它除了最后一层可以不为满，其他层必须为满，且最后一层节点必须是从左向右排列，且两节点之间不可有空再插入一个节点。
【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

4. 二叉树的性质

  1. 若规定根节点的层数为 1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
  2. 若规定根节点的层数为 1，则深度为h的二叉树的最大结点数是2^h - 1.
  3. 对任何一棵非空二叉树,如果度为 0 其叶结点个数为 M,度为 2 的分支结点个数为 N,
    则有M = N + 1
  4. 若规定根节点的层数为 1，具有 n 个结点的满二叉树的深度，h = log以2为底，n+1为对数)
  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为i的结点有:
    1.若i > 0，i位置节点的双亲序号:(i - 1) / 2; 若i = 0，则无双亲节点
    2.若2i+1 < n，左孩子序号:2i + 1，2i + 1 >= n否则无左孩子
    3.若2i+2 < n，右孩子序号:2i + 2，2i + 2 >= n否则无右孩子

三、二叉树的顺序存储

1. 二叉树树的顺序存储

二叉树树的顺序存储是以数组为物理结构存储的一种结构，而画出来的是逻辑结构。
树的顺序存储是依照上面树的父子关系：

  • parent = (child - 1) / 2 （ 这里由于整形相除得到整形的机制，使得不需要要分辨左右孩子 ）
  • leftchild = parent * 2 + 1 ( 左孩子的下标是父亲下标的两倍加一 ）
  • rightchild = parent * 2 + 2 ( 右孩子的下标是父亲下标的两倍加二）

而我们看下面的图就可以知道，并不是所有的二叉树都适合使用二叉树的顺序存储。
下面非完全二叉树一共十三个空间就浪费了五个，再别说更极端的树了。
所以得出结论只有完全二叉树适合使用二叉树的顺序存储！！
【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

2. 堆的概念及实现

2.1 堆的概念

如果有一个关键码的集合，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：根节点的关键码大于等于左右子树的关键码（根节点的关键码大于等于左右子树的关键码），则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

关键码(key) 是堆中每个元素的一个属性,用于比较元素的大小。
根据元素的关键码,可以决定堆的类型:

  • 大根堆:每个节点的关键码都大于或等于其子节点的关键码,即根节点具有最大的关键码。
  • 小根堆:每个节点的关键码都小于或等于其子节点的关键码,即根节点具有最小的关键码。

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

2.2 堆的实现

  • 关于堆的一些接口：Heap.h
#pragma once

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

typedef int HPDataType;

typedef struct Heap
{
	int* arr;
	int size;
	int capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* php, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);
2.2.1 堆的向上调整算法

使用堆的向上调整算法的前提是：在插入新元素之前，前面的元素就已经满足了堆的性质！！
堆的向上调整(heapify up)算法的思想是:（假设建大堆）

  1. 将新元素插入到叶子节点。
  2. 与父节点进行比较。如果新元素的值大于父节点的值,则需要进行交换。
  3. 将新元素看作父节点,重复上述过程。

直到新元素值小于父节点为止,此时已经满足堆的性质。

void AdjustUp(int* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			HPDataType tmp = arr[child];
			arr[child] = arr[parent];
			arr[parent] = tmp;
		}

		child = parent;
		parent = (child - 1) / 2;
	}
}
2.2.2 堆的向下调整算法

使用堆的向下调整算法的前提是：根节点的左右子树都满足堆的性质
堆的向下调整(Heapify Down)算法的思想是:

  • 与左右子节点进行比较。
  • 如果子节点中有比当前节点更大的值(小根堆)或者更小的值(大根堆),则与最大(小根堆)或最小(大根堆)的子节点交换。
  • 将交换后的子节点作为新的父节点,重复上述过程。
    【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言 
//从从后往前的第一个非叶子节点开始向下调整
void AdjustDown(int* arr, int N, int parent)
{
	int child = parent * 2 + 1;
	//这里假设左孩子为小的/大的一个
	while (child < N)
	{
		//假设这里建小堆
		//假设有右孩子并且如果右孩子比左孩子小的
		if (child + 1 < N && arr[child + 1] > arr[child])
		{
			child++;
		}
		//如果孩子比双亲小，则将双亲和孩子交换
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else //当孩子比双亲大时，则不需要调整了
		{
			break;
		}
	}
}
2.2.3 堆的构建
a. 堆构建的方法方法
  1. 堆的向上调整算法建堆
  2. 堆的向下调整算法建堆

下面用两张图片来演示这两种构建堆的方法：

堆的向上调整算法建堆:
使用向上调整算法建堆需要从头开始插入元素，必须保证每次插入新元素使用向上调整算法，使得满足堆的条件。
【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

堆的向下调整算法建堆:
向下调整算法的前提是左右子树都符合堆的条件，而下面这颗完全二叉树的左右子树并不满足这一条件，那么左右子树任何满足堆的条件呢？那就需要左右子树的左右子树满足堆的条件，这样一直想下去可以的得出想要对根节点使用向下调整算法，必须让根节点以下的所有子树都满足堆的条件，显然从头开始是不能完成的，那么只能从尾部开始向下调整，而后又发现叶子结点本就符合堆的条件，那么只需要从最后一个节点的父亲节点开始从后往前使用向下调整算法即可完成建堆。

小结:使用向下调整算法建堆，需要从最后一个节点的父亲节点开始从后往前使用向下调整算法即可完成建堆。
【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

// 建堆--向上调整建堆 ：注意此方法建堆需要申请和数组一样大的空间，空间复杂度为O(N)
// 这里只是演示一下可以有这种使用方法，不推荐！！！！！！！！
// 若是完成堆排序、TopK等操作不推荐，能够在数组上直接建堆，没有空间的消耗
void HeapCreate(Heap* php, HPDataType* a, int n)
{
	assert(php);
	//堆的初始化
	php->capacity = 0;
	php->size = 0;
	php->arr = 0;
	
	// 此操作是针对堆的，就需要使用这个
	for (int i = 0; i < n; i++)    
	{							   
		HeapPush(php, a[i]);       //HeapPush()函数在下面讲述
	}
	
	//下面两种方法是任何情况都可以使用，只需要修改一些参数
	//而上面的只能在有堆的情况才能使用
	/*// 建堆--向上调整建堆 --O(N*logN) -- log以2为底N的对数
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
	
	// 建堆--向下调整建堆 --O(N)
	for (int i = (n-1-1)/2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}*/
}
b. 建堆的时间复杂度
  1. 向上调整算法建堆的时间复杂度
    【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言
  2. 向下调整建堆的时间复杂度
    【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言
    小结：
    向上调整算法建堆和向下调整算法建堆相比还是稍逊一筹。
    所以这里推荐使用向下调整算法建堆！！
2.2.4 堆的插入

当有新元素插入时，该元素需要与它的父亲进行比较。如果新元素的值大于父节点的值,则需要进行交换。 将新元素看作父节点,重复上述过程。（假设这里建大堆）

void HeapPush(Heap* php, HPDataType x)
{
	assert(php);

	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		int* tmp = realloc(php->arr, sizeof(int) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc");
			return;
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}

	php->arr[php->size] = x;
	php->size++;
	AdjustUp(php->arr, php->size-1);
}
2.2.5 堆的删除
//从从后往前的第一个非叶子节点开始向下调整
void AdjustDown(int* arr, int N, int parent)
{
	int child = parent * 2 + 1;
	//这里假设左孩子为小的/大的一个
	while (child < N)
	{
		//假设这里建小堆
		//假设有右孩子并且如果右孩子比左孩子小的
		if (child + 1 < N && arr[child + 1] > arr[child])
		{
			child++;
		}
		//如果孩子比双亲小，则将双亲和孩子交换
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else //当孩子比双亲大时，则不需要调整了
		{
			break;
		}
	}
}
// 堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	AdjustDown(php->arr, php->size, 0);
}

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

2.2.6 堆代码的总体实现
  • 头文件Heap.h的实现
#pragma once

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

typedef int HPDataType;

typedef struct Heap
{
	int* arr;
	int size;
	int capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* php, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);
  • 接口Heap.c的实现
#include "Heap.h"

void AdjustUp(int* arr, int child);

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 建堆--向上调整建堆 ：注意此方法建堆需要申请和数组一样大的空间，空间复杂度为O(N)
// 这里只是演示一下可以有这种使用方法，不推荐！！！！！！！！
// 若是完成堆排序、TopK等操作不推荐，能够在数组上直接建堆，没有空间的消耗
void HeapCreate(Heap* php, HPDataType* a, int n)
{
	assert(php);
	//堆的初始化
	php->capacity = 0;
	php->size = 0;
	php->arr = 0;
	
	// 此操作是针对堆的，就需要使用这个
	for (int i = 0; i < n; i++)    
	{							   
		HeapPush(php, a[i]);       //HeapPush()函数在下面讲述
	}
	
	//下面两种方法是任何情况都可以使用，只需要修改一些参数
	//而上面的只能在有堆的情况才能使用
	/*// 建堆--向上调整建堆 --O(N*logN) -- log以2为底N的对数
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
	
	// 建堆--向下调整建堆 --O(N)
	for (int i = (n-1-1)/2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}*/
}
	
void HeapDestroy(Heap* php)
{
	assert(php);

	free(php->arr);
}

void AdjustUp(int* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			HPDataType tmp = arr[child];
			arr[child] = arr[parent];
			arr[parent] = tmp;
		}

		child = parent;
		parent = (child - 1) / 2;
	}
}

//从从后往前的第一个非叶子节点开始向下调整
void AdjustDown(int* arr, int N, int parent)
{
	int child = parent * 2 + 1;
	//这里假设左孩子为小的/大的一个
	while (child < N)
	{
		//假设这里建小堆
		//假设有右孩子并且如果右孩子比左孩子小的
		if (child + 1 < N && arr[child + 1] > arr[child])
		{
			child++;
		}
		//如果孩子比双亲小，则将双亲和孩子交换
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else //当孩子比双亲大时，则不需要调整了
		{
			break;
		}
	}
}

void HeapPush(Heap* php, HPDataType x)
{
	assert(php);

	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		int* tmp = realloc(php->arr, sizeof(int) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc");
			return;
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}

	php->arr[php->size] = x;
	php->size++;
	AdjustUp(php->arr, php->size-1);
}


// 堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	AdjustDown(php->arr, php->size, 0);
}

// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->arr[0];
}

// 堆的数据个数
int HeapSize(Heap* php)
{
	assert(php);
	
	return php->size;
}

// 堆的判空
int HeapEmpty(Heap* php)
{
	assert(php);

	return php->size == 0;
}

2.3 堆的应用

  1. 堆排序
  2. TopK
2.3.1 堆排序的实现

堆排序实现思想：

  1. 先将数组建成堆(升序建大堆，降序建小堆)
  2. 交换堆顶元素和堆尾元素（数组首尾元素）
  3. 对数组向下调整，使其保持堆的形式
  4. 调整元素个数，使调整过的元素在正确位置，不再改变
  5. 重复 2-4 步，直到调整元素为 1 时结束，排序成功

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

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

typedef int HPDataType;

typedef struct Heap
{
	int* arr;
	int size;
	int capacity;
}Heap;

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整 O(N*logN)
void AdjustUp(int* arr, int child)
{
	//将传入函数中的child向他的双亲进行对比
	int parent = (child - 1) / 2;
	//循环条件为
	while (child > 0)
	{
		//若child比parent大(建大堆) / 小(建小堆) 则进行交换
		if (arr[child] < arr[parent])
		{
			HPDataType tmp = arr[child];
			arr[child] = arr[parent];
			arr[parent] = tmp;
			//child移到parent的位置，继续与他的parent进行对比
			child = parent;
			parent = (child - 1) / 2;
		}
		else //否则则证明该数组已经是堆，不需要再进行调整
		{
			break;
		}
	}
}

//向下调整算法 O(N)
//从从后往前的第一个非叶子节点开始向下调整
void AdjustDown(int* arr, int N, int parent)
{
	int child = parent * 2 + 1;
	//这里假设左孩子为小的/大的一个
	while (child < N)
	{
		//假设这里建大堆
		//假设有右孩子并且如果右孩子比左孩子大(建大堆)/小(建小堆)的
		if (child + 1 < N && arr[child + 1] > arr[child])
		{
			child++;
		}
		//如果孩子比双亲大(建大堆)/小(建小堆)，则将双亲和孩子交换
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else //当孩子比双亲大时，则不需要调整了
		{
			break;
		}
	}
}


void Print(int* arr, int N)
{
	int i = 0;
	for (i = 0; i < N; i++)
	{
		printf("%d ", arr[i]);
	}
}

void HeapSort(int* arr, int n)
{
	向上调整建堆
	//for (int i = 0; i < n; i++)
	//{
	//	AdjustUp(arr, i);
	//}

	//向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

	int end = n - 1;
	for (int i = 0; i < n; i++)
	{
		//end为数组最后一个元素的下标
		Swap(&arr[0], &arr[end]);
		//end也为该元素之前元素的总个数
		AdjustDown(arr, end, 0);
		end--;
	}
}

int main()
{
	int arr[] = { 3,2,9,7,6,1,8,5,4,0 };
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	Print(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}
2.3.2 TopK的实现

TopK问题有在我已知情况下有两种解决情况：（假设有N个值并且要取k个最值）
当数据量过大的时候，数据只能存储在内存中，而内存中不能建堆，只能使用第二种方法

  1. 建立堆，取堆顶元素，与堆中最后一个元素交换，堆元素个数减一，向下调整堆，再重复前面的内容k-1次

值得注意的是在第一种情况下，若N与k相等，那么TopK就是堆排序。
【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>

typedef int HPDataType;

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//从从后往前的第一个非叶子节点开始向下调整
void AdjustDown(int* arr, int N, int parent)
{
	int child = parent * 2 + 1;
	//这里假设左孩子为小的/大的一个
	while (child < N)
	{
		//假设这里建小堆
		//假设有右孩子并且如果右孩子比左孩子小的
		if (child + 1 < N && arr[child + 1] < arr[child])
		{
			child++;
		}
		//如果孩子比双亲小，则将双亲和孩子交换
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else //当孩子比双亲大时，则不需要调整了
		{
			break;
		}
	}
}

//(1)

void TopK(int* arr,int n , int k)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

	//定义一个变量end记录堆最后一个元素
	int end = n - 1;
	//取前k个最值
	for (int i = 0; i < k; i++)
	{
		//将堆顶的元素输出
		printf("%d ", arr[0]);
		//将堆顶与堆中最后一个元素交换，并减少堆元素个数
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

int main()
{
	int n = 10000;
	srand((unsigned int)time(0));
	int* arr = (int*)malloc(sizeof(int)*n);
	if (arr == NULL)
	{
		perror("malloc fail");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		arr[i] = rand() % 1000000 + 5;
	}

	//最大
	/*arr[100] = 1000001;
	arr[500] = 1000002;
	arr[1000] = 1000003;
	arr[5555] = 1000004;
	arr[9999] = 1000005;*/

	//最小
	arr[100] = 1;
	arr[500] = 2;
	arr[1000] = 3;
	arr[5555] = 4;
	arr[9999] = 5;

	TopK(arr, n , 5);
	return 0;
}
  1. 建立一个 k 个元素个数的堆，(取最大k个数)建小堆 /(取最小k个数)建大堆 ，
    将剩余的N - k个值依此与栈顶的数对比，若符号条件，则取代栈顶的元素
    并向下调整让其保持堆的性质，重复以下内容，直至数组遍历完

【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>

typedef int HPDataType;

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//从从后往前的第一个非叶子节点开始向下调整
void AdjustDown(int* arr, int N, int parent)
{
	int child = parent * 2 + 1;
	//这里假设左孩子为小的/大的一个
	while (child < N)
	{
		//假设这里建小堆
		//假设有右孩子并且如果右孩子比左孩子小的
		if (child + 1 < N && arr[child + 1] < arr[child])
		{
			child++;
		}
		//如果孩子比双亲小，则将双亲和孩子交换
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else //当孩子比双亲大时，则不需要调整了
		{
			break;
		}
	}
}


//当数据量过大的时候，数据只能存储在内存中，而内存中不能建堆，只能使用第二种方法

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand((unsigned int)time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}

void PrintTopK(int k)
{
	//先打开文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
	//建立一个元素个数为k的堆
	int* arr = (int*)malloc(sizeof(int) * k);
	if (arr == NULL)
	{
		perror("malloc error");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &arr[i]);
	}

	//建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr,k, i);
	}

	//遍历剩余的元素比较并进行
	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > arr[0])
		{
			Swap(&val, &arr[0]);
			AdjustDown(arr,k, 0);
		}
	}

	Print(arr , k);
}

int main()
{
	//CreateNDate();
	PrintTopK(10);
	return 0;
}

3. 二叉树的链式存储

二叉树中每一个节点包括：

  1. 需要存储的数据、
  2. 左孩子节点的地址
  3. 右孩子节点的地址
  • 关于二叉树的接口：Btree.h
#pragma once

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

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
  • 关于二叉树接口函数的实现：Btree.c

3.1 二叉树的构建

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BuyTreeNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->data = x;

	return newnode;
}

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	//当a == '#'时说明当前节点为NULL
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = BuyTreeNode(a[*pi]);
	(*pi)++;
	root->left = BinaryTreeCreate(a, n , pi);
	root->right = BinaryTreeCreate(a, n, pi);

	return root;
}

3.2 二叉树的前序遍历

// 二叉树前序遍历 : 根   左子树   右子树
void BinaryTreePrevOrder(BTNode* root)
{
	//当该节点为NULL时，打印N
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

3.3 二叉树的中序遍历

// 二叉树中序遍历: 左子树   根   右子树
void BinaryTreeInOrder(BTNode* root)
{
	//当该节点为NULL时，打印N
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

3.4 二叉树的后序遍历

// 二叉树后序遍历: 左子树   右子树    根
void BinaryTreePostOrder(BTNode* root)
{
	//当该节点为NULL时，打印N
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

3.5 二叉树的节点个数

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	//如果该root为NULL，则root不是节点
	if (root == NULL)
		return 0;
	//如果root不为空，则返回他的左子树节点+右子树的节点+1 (1为他本身)
	return BinaryTreeSize(root->left) 
	+ BinaryTreeSize(root->right) + 1;
}

3.6 二叉树的叶子节点个数

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	//如果该root为NULL，则root不是节点
	if (root == NULL)
		return 0;
	//当root的左子树和右子树都为NULL时，则说明root是叶子节点
	if (root->left == NULL && root->right == NULL)
		return 1;
	//返回root左子树和右子树上的叶子节点个数
	return BinaryTreeLeafSize(root->left) 
		+ BinaryTreeLeafSize(root->right);
}

3.7 二叉树的第k层节点个数

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//k不能为0
	assert(k > 0);

	//如果该root为NULL，则root不是节点
	if (root == NULL)
		return 0;
	//当k == 1是，说明到了相对于根的第k层
	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

3.8 二叉树中寻找值为x的节点

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	//如果该root为NULL，则root不是节点
	if (root == NULL)
		return NULL;

	//当找到x后返回root
	if (root->data == x)
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)  //当左子树返回的地址不为空，说明已经找到了x，返回ret1
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)  //当右子树返回的地址不为空，说明已经找到了x，返回ret1
	{
		return ret2;
	}

	//当前面左子树和右子树都没返回，说明没有找到，返回NULL
	return NULL;
}

3.9 二叉树的层序遍历

  • 队列的接口
#pragma once

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

typedef struct BinaryTreeNode* QDataType;
// 链式结构：表示队列 

typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;  //指向队列最后一个元素的后面
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
  • 关于队列接口函数的实现：Queue.c
#include "Queue.h"

// 初始化队列 
void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->next = NULL;
	newnode->data = data;

	if (q->front == NULL)      //分队列是否有元素两种情况
	{
		assert(q->rear == NULL);
		q->front = newnode;
		q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}

	q->size++;//入队列，队列长度加一
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL && q->rear == NULL;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	//出队列时，队列不能为空
	assert(!QueueEmpty(q));

	//当队列中只有一个元素的时候，不仅仅头指针需要改变，尾指针也需要改变
	//因为当删除最后一个元素时，首指针释放当前节点，并向后移动，而尾指针并没有移动
	//当释放后若在插入元素时，尾指针会造成野指针的情况
	if (q->front->next == NULL)
	{
		QNode* del = q->front;
		q->front = NULL;
		q->rear = NULL;
		free(del);
	}
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
	}
	q->size--;
}


// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	//获取队列头部元素时，队列不能为空
	assert(!QueueEmpty(q));

	return q->front->data;
}


// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	//获取队列头部元素时，队列不能为空
	assert(!QueueEmpty(q));

	return q->rear->data;
}


// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);

	//结构体中定义了一个size
	//而这里遍历链表得到个数，效率低
	/*int size = 0;
	QNode* cur = q->front;
	while (cur != q->rear)
	{
		size++;
		q->front = q->front->next;
	}*/
	return q->size;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu;
	QueueInit(&qu);
	QueuePush(&qu, root);
	while (!QueueEmpty(&qu))
	{
		BTNode* front = QueueFront(&qu);
		printf("%c ", front->data);
		QueuePop(&qu);
		if(front -> left != NULL)
			QueuePush(&qu, front->left);
		if (front->right != NULL)
			QueuePush(&qu, front->right);
	}
}

3.10 判断是否为完全二叉树

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	if (root == NULL)
		return true;
	//当一个节点的左子树为NULL，右子树不为NULL，那么这棵树不是完全二叉树
	if (root->left == NULL && root->right != NULL)
		return false;

	return BinaryTreeComplete(root->left)
		&& BinaryTreeComplete(root->right);
}

结尾

二叉树作为一个新知识相比较于前面的知识点会有点点陌生，里面涉及的递归也会是新手相对于薄弱的地方，这边建议对于二叉树递归知识点反复观看，二叉树递归题目先自己思考，实在想不出来的可以参考一下解决思路，这也是学习的过程，对于二叉树中递归问题最终方法就是画递归展开图。

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，请大家给一个三连支持一下！！🌹🌹
【数据结构】非线性结构之树结构（含堆）,数据结构,链表,算法,c语言文章来源地址https://www.toymoban.com/news/detail-550872.html

到了这里，关于【数据结构】非线性结构之树结构（含堆）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C 非线性结构——树 万字详解（通俗易懂）

    C 非线性结构——树 万字详解（通俗易懂）

    目录 一、树的介绍         1.定义 :          2.相关概念 :          3.简单分类 :          4.相关应用 :  二、树的存储         1.二叉树的存储 :                  1° 二叉树连续存储                 2° 二叉树链式存储（常用）         2.普通树和森林的存储 :   

    2023年04月09日
    浏览(37)
  • Abaqus结构仿真软件的非线性问题与解决方案

    Abaqus结构仿真软件的非线性问题与解决方案

    ​ 无论是什么FEA 软件，想要获得非线性问题的一些解决方法始终没有那么简单。遇到问题是很常见的，那么下面就来看看Abaqus用户克服这一类问题的解决方法吧。   1. 简化模型 从简化模型开始，通过逐渐添加详细信息来构建它，例如可塑性和摩擦性可以在开始时排除。由于

    2024年02月06日
    浏览(34)
  • 机器学习实战-系列教程8：SVM分类实战3非线性SVM（鸢尾花数据集/软间隔/线性SVM/非线性SVM/scikit-learn框架）项目实战、代码解读

    机器学习实战-系列教程8：SVM分类实战3非线性SVM（鸢尾花数据集/软间隔/线性SVM/非线性SVM/scikit-learn框架）项目实战、代码解读

    本篇文章的代码运行界面均在Pycharm中进行 本篇文章配套的代码资源已经上传 SVM分类实战1之简单SVM分类 SVM分类实战2线性SVM SVM分类实战3非线性SVM 使用PolynomialFeatures模块进行预处理，使用这个可以增加数据维度 polynomial_svm_clf.fit(X,y)对当前进行训练传进去X和y数据 SVM分类实战

    2024年02月07日
    浏览(40)
  • 线性回归（线性拟合）与非线性回归(非线性拟合)原理、推导与算法实现（一）

    线性回归（线性拟合）与非线性回归(非线性拟合)原理、推导与算法实现（一）

    关于回归和拟合，从它们的求解过程以及结果来看，两者似乎没有太大差别，事实也的确如此。从本质上说，回归属于数理统计问题，研究解释变量与响应变量之间的关系以及相关性等问题。而拟合是把平面的一系列点，用一条光滑曲线连接起来，并且让更多的点在曲线上或

    2023年04月14日
    浏览(40)
  • R语言lasso惩罚稀疏加法（相加）模型SPAM拟合非线性数据和可视化

    R语言lasso惩罚稀疏加法（相加）模型SPAM拟合非线性数据和可视化

    本文将关注R语言中的LASSO（Least Absolute Shrinkage and Selection Operator）惩罚稀疏加法模型（Sparse Additive Model，简称SPAM）。SPAM是一种用于拟合非线性数据的强大工具，它可以通过估计非线性函数的加法组件来捕捉输入变量与响应变量之间的复杂关系 （ 点击文末“阅读原文”获取完

    2024年02月11日
    浏览(28)
  • Matlab数据处理：用离散数据根据自定义多变量非线性方程拟合解析方程求取参数

    Matlab数据处理：用离散数据根据自定义多变量非线性方程拟合解析方程求取参数

    问题：已知xlsx表格[X,Y,Z]的离散取值，希望用  来拟合，用matlab求得[C1,C2,C3,C5,C6]的值 解答： 运行结果：  备注： 1.rsquare=0.8668认为接近1，拟合效果不错 2.fill函数的startpoint如何设置[C1,...C6]得到一个收敛点？（我找了没找到什么设置startpoint好方法，摸索用如下方法找到了一个

    2024年02月11日
    浏览(36)
  • 【Python机器学习】SVM解决非线性问题和信用卡欺诈检测实战（附源码和数据集）

    【Python机器学习】SVM解决非线性问题和信用卡欺诈检测实战（附源码和数据集）

    需要全部源码和数据集请点赞关注收藏后评论区留言私信~~~ 支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的 间隔最大的线性分类器 ，间隔最大使它有别于感知机；SVM还包括 核技巧 ，这使它成为实质上的非线性分类器。SVM的的学

    2024年02月06日
    浏览(35)
  • 【具有非线性反馈的LTI系统识别】针对反馈非线性的LTI系统，提供非线性辨识方案（Simulink&Matlab代码实现）

    【具有非线性反馈的LTI系统识别】针对反馈非线性的LTI系统，提供非线性辨识方案（Simulink&Matlab代码实现）

     💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势： 🌞🌞🌞 博客内容尽量做到思维缜密，逻辑清晰，为了方便读者。 ⛳️ 座右铭： 行百里者，半于九十。 📋📋📋 本文目录如下： 🎁🎁🎁 目录 💥1 概述 📚2 运行结果 🎉3 参考文献 🌈4 Matlab代码、Simulink仿真

    2024年02月14日
    浏览(37)
  • 连续非线性系统线性化理论

    连续非线性系统线性化理论

    在工程领域的被控对象常常是非线性的动力系统。对非线性控制系统 x ˙ = f ( x , t ) dot{x}=f(x,t) x ˙ = f ( x , t ) 的稳定性分析，常常需要将非线性系统线性化成线性系统 x ˙ = A ( t ) x dot x = A(t)x x ˙ = A ( t ) x 后，对线性系统设计的控制器放在非线性系统上，达到合适的控制效果

    2024年01月18日
    浏览(78)

  • 数学建模：线性与非线性优化算法

    🔆 文章首发于我的个人博客：欢迎大佬们来逛逛 优化算法 是指在满足一定条件下,在众多方案中或者参数中最优方案,或者参数值,以使得某个或者多个功能指标达到最优,或使得系统的某些性能指标达到最大值或者最小值 优化的两个关键点： 1.明确优化的目标函数 2.明确优化

    2024年02月07日
    浏览(29)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包