【数据结构】树和二叉树——Lesson1

_小羊_

发布于 2024-10-16 15:07:12

2450

文章被收录于专栏：C++C++

前言

一、树

1、树的概念和结构

树是一种非线性的数据结构，它是由n（n>=0）个有限节点组成的一个具有层次关系的集合。它包含一个根节点以及若干子节点，子节点又可以有自己的子节点，以此类推。

根节点： 根节点没有前驱结点
子节点： 除根节点外，其余节点被分为m（m>0）个互不相交的集合，其中每一个集合又是一棵结构与树类似的子树。每棵子树的根节点有且只有一个前驱节点，可以有0个或多个后继节点。因此，树是递归定义的。

与现实中的树相比，这里的树更像是一棵倒挂的树。

树形结构中，子树之前不能有交集，否则就不是树形结构。

非树结构：

子树是不相交的
除了根节点，每个节点有且只有一个父节点
一棵N个节点的树有N-1条边

2、相关术语

树有很多的术语，基本都是根据现实中的树和人类亲缘关系命名的，其中红色标记的是比较重要的概念。

父节点/双亲节点： 若一个节点有子节点，这个节点就是子节点的父节点（相对的），上图中A是B的父节点
子节点： 一个节点含有的子树的根节点称为该节点的子节点，上图B是A的子节点
节点的度： 一个节点有几个孩子，它的度就是多少
树的度： 一棵树中，最大节点的度就是树的度，上图树的度为2
叶子节点/终端节点： 度为0的节点称为叶子节点
分支节点/非终端节点： 度不为0的节点
兄弟节点： 具有相同父亲的节点就是兄弟节点（亲兄弟）
节点的层次： 从根开始定义起，根为第一层，其子节点为第二层，以此类推
树的高度/深度： 树中节点的最大层次，上图树的深度为5
节点的祖先： 从根到该节点所经分支上的所有节点
路径： 一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列
子孙： 以某节点为根的子树中任意一节点都称为该节点的子孙
森林： 由m (m>0）棵互不相交的树（多棵树）的集合称为森林

3、树的表示

树结构相对线性表复杂的多，既要保存值域，还要保存节点和节点之间的关系，最常用的表示法是左孩子右兄弟表示法。

struct TreeNode
{
	struct Node* child;//左边开始的第一个孩子节点
	struct Node* brother;//右边的下一个兄弟节点
	int data;
};

4、树形结构应用场景

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件好文件夹。在文件系统中，树结构被广泛应用，它通过父节点和子节点之间的关系来表示不同层级的文件和文件夹之间的关联。

二、二叉树

1、概念和结构

二叉树是一种特殊的树，在树形结构中，我们最常用的就是二叉树，一棵二叉树是节点的一个有限集合，该集合由一个根节点加上两棵别称为左子树和右子树的二叉树组成或者为空。

上图就是二叉树的基本结构。从上图可以看到，二叉树有以下特点：

二叉树的特点：

二叉树不存在度大于2的节点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

对于任意二叉树都是由以下几种情况复合而成的：

2、特殊的二叉树

满二叉树： 一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。一个层数为N的满二叉树的节点数为2^N-1。
完全二叉树： 完全二叉树的前N-1层都是满的，最后一层不满且子节点从左到右必须是连续的。完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的，因此满二叉树是一种特殊的完全二叉树。

3、二叉树的存储

3.1顺序存储

顺序存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，如果不是完全二叉树要保证下标对应就会有空间浪费，因此完全二叉树适合用顺序结构存储。

可以看到非完全二叉树虽然也可以使用数组存储，但是存在空间浪费，所以非完全二叉树更适合链式存储。

这种存储结构有一个规律，可以根据下标来计算父子关系。

假设父亲在数组中的下标为：i

左孩子在数组中的下标：2*i+1
右孩子在数组中的下标：2*i+2

假设孩子在数组中的下标是：j

父亲在数组中的下标就是(j-1）/ 2

实际中常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆不是一回事，一个是数据结构，一个是操作系统中管理内存的一块区域划分。

3.2链式存储

二叉树的链式存储是指用链表来表示一棵二叉树，即用链表来指示元素的逻辑关系。通常每个节点由三个域组成，一个数据域和两个指针域，分别用左指针和右指针来指向左孩子和右孩子。链式结构又分为二叉链和三叉链，当前学习中一般都是二叉链。

本篇文章主要介绍二叉树的顺序存储，在下篇文章中会详细介绍二叉树的链式存储。

4、顺序结构实现二叉树

4.1堆的结构和概念

	堆（Heap）	栈（Stack）
数据结构	一种树形结构，可以做堆排序，效率很高	一种线性结构，具有后进先出的特点，基本操作有压栈、出栈
C语言	用于动态分配内存的区域	由操作系统分配的固定大小的空间

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树性质的同时，还具备其他的特性。

堆具有以下性质：

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

其中堆又分为大堆和小堆：

大堆 / 大根堆 / 大顶堆：任何一个父亲>=孩子，根最大
小堆 / 小根堆 / 小顶堆：任何一个父亲<=孩子，根最小

从上图中可以看到，小堆不一定是升序，大堆也不一定是降序， 因为兄弟之间没有大小关系。

4.2堆的实现

堆的底层结构是数组，基本与顺序表一样。因此定义堆的结构为：

typedef int HeapDataType;

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

void HeapInit(Heap* php);
void HeapDestroy(Heap* php);
HeapDataType HeapTop(Heap* php);
bool HeapEmpty(Heap* php);

其中初始化、销毁、取堆顶、判空函数也基本与我们之前写过的相差无几，这里就直接给出不做介绍。

void HeapInit(Heap* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->arr[0];
}

bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

接下来就到了比较重要的内容.

4.2.1向上调整算法

| 堆的插入 将新数据插入到数组末尾，再通过向上调整算法，直到满足堆。

先将元素插入到堆的末尾，即最后一个孩子之后
插入后如果堆的性质被破坏，将新插入的节点顺着其双亲节点往上调整到合适的位置即可

下面是小堆插入：

void AdjustUp(HeapDataType* 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 HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HeapDataType* tmp = (HeapDataType*)realloc(php->arr, newcapacity * sizeof(HeapDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->arr = tmp;
		tmp = NULL;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	php->size++;
	
	//向上调整
	AdjustUp(php->arr, php->size - 1);
}

向上调整算法建堆的时间复杂度为：O(N*logN)

4.2.2向下调整算法

| 堆的删除

删除堆是删除堆顶的数据，前提是size > 0有数据可删。将堆顶的数据和最后一个数据交换，然后删除数组最后一个数据，为了继续满足堆需要再进行向下调整算法，结果是次小的（次大的）在堆顶。 堆顶数据和最后一个数据交换再删除的目的是保证根节点下左右子树都是堆，父子关系不会乱。

向下调整：

void AdjustDown(HeapDataType* arr, int parent, int n)
{
	//假设左孩子小
	int child = 2 * parent + 1;

	while (child < n)//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 = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	
	AdjustDown(php->arr, 0, php->size);
}

向下调整算法建堆时间复杂度为：O(N)

4.3堆的应用

4.3.1堆排序

| 版本一：基于已有数组建堆，取堆顶元素完成排序

void HeapSort(HeapDataType* arr, int n)
{
	Heap hp;
	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp, arr[i]);
	}

	int i = 0;
	while (!HeapEmpty(&hp))
	{
		arr[i++] = HeapTop(&hp);
		HeapPop(&hp);
	}

	HeapDestroy(&hp);
}

该版本有一个前提：必须提供有现成的数据结构堆。所以这样排序不好，得先建一个堆放入数据（开辟额外空间），再从堆里面将数组拷贝到原数组中，空间复杂度O(N)。 要是能有什么办法避免开辟额外的空间就好了，来看版本二：

| 版本二：原数组上建堆，首尾交换，交换后的堆尾数据从堆中删除，将堆顶数据向下（向上）调整选出次大（次小）的数据

思路是直接将原数组（看作）一个堆，从下标为1的孩子开始，向上（向下） 循环调整（实现大堆或者小堆），最终达到在原数组上建堆的效果，这个方法好在没有额外的空间消耗。

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

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

向上调整算法建堆时默认第一个元素已经排好，从下标为1的元素往后依次开始调整。向下调整算法建堆，从最后一个孩子的父亲开始往前依次向下调整，到堆顶时结束。

因为向上调整算法建堆的时间复杂度是：O(N*logN)，而向下调整算法建堆的时间复杂度是：O(N)，所以我们优先使用向下调整算法建堆来实现堆排序。

确定了建堆的算法，接下来就要考虑的是如果我们要排升序，该在原数组上建大堆还是小堆？可能大多数人下意识地认为排升序的话应该建小堆，因为我们可以通过循环拿根节点（堆顶）再删除根节点的方法依次得到最小值，其实这样是不好的。因为小堆的堆顶是所有数里的最小值，此时堆顶已经排好了，要想排剩下的数就要重新建堆，这样一来父子关系全乱了，实现起来代价太大。

如果建大堆，此时堆顶是最大的数，可以删除堆顶，结果就是最大的数到数组末端，n- -后这个最大的数就不被当做堆内的数，循环向下调整重复上面的操作，就能得到按升序排列的数组了。

所以，排升序，建大堆；排降序，建小堆。

void HeapSort(int* arr, int n)
{
	//升序，建大堆
	//降序，建小堆
	
	//向下调整建堆
	//O(N)
	for (int i = (n-1-1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	
	//O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

向下调整算法建堆时间复杂度O(N)，再加上最后的排序操作的时间复杂度O(N*logN)，整个堆排序的时间复杂度是O(N*logN)，比起冒泡排序时间复杂度O(N^2)，堆排序是非常非常理想的。

4.3.2 TOP-K问题

TOP-K问题：求数据量比较大的数据中前K个最大或最小的元素。比如：富豪榜TOP10、世界企业TOP500、中国名校TOP100等。

对于TOP-K问题，最简单最直接的办法就是排序，但是当数据量比较大时排序就不可取了，最佳的方式就是利用堆来解决。

我们可以将大量的数据建大堆（向下调整算法优先），此时堆顶就是最大的数据，然后Topk次就能解决问题了。

void TOP()
{
	Heap hp;
	HeapInit(&hp);

	int arr[] = { 34,453,3,4,56,36,6,3,7,34,6,36,3,7,2,4,46,534,7,3,7673,56 };
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		HeapPush(&hp, arr[i]);
	}

	int k = 0;
	scanf("%d", &k);
	while (k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}

	HeapDestroy(&hp);
}

5、完整代码

heap.h:

#pragma once

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

typedef int HeapDataType;

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

void AdjustUp(HeapDataType* arr, int child);
void AdjustDown(HeapDataType* arr, int parent, int n);
void Swap(HeapDataType* child, HeapDataType* parent);
void HeapInit(Heap* php);
void HeapDestroy(Heap* php);
void HeapPush(Heap* php, HeapDataType x);
void HeapPop(Heap* php);
HeapDataType HeapTop(Heap* php);
bool HeapEmpty(Heap* php);

heap.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "heap.h"

void HeapInit(Heap* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void Swap(HeapDataType* child, HeapDataType* parent)
{
	HeapDataType tmp = *child;
	*child = *parent;
	*parent = tmp;
}

void AdjustUp(HeapDataType* 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 HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HeapDataType* tmp = (HeapDataType*)realloc(php->arr, newcapacity * sizeof(HeapDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->arr = tmp;
		tmp = NULL;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	php->size++;

	//向上调整
	AdjustUp(php->arr, php->size - 1);
}

void AdjustDown(HeapDataType* arr, int parent, int n)
{
	//假设左孩子小
	int child = 2 * parent + 1;

	while (child < n)//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 = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;

	AdjustDown(php->arr, 0, php->size);
}

HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->arr[0];
}

bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

test.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "heap.h"

void test1()
{
	int arr[] = { 5,3,2,8,5,3,6,9,0 };
	Heap hp;
	HeapInit(&hp);

	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		HeapPush(&hp, arr[i]);
	}

	HeapDestroy(&hp);
}

void test2()
{
	//排升序
	int arr[] = { 5,3,2,8,5,3,6,9,0 };
	for (int i = 1; i < sizeof(arr) / sizeof(int); i++)
	{
		//建大堆
		AdjustUp(arr, i);
	}

}

//void HeapSort(int* arr, int n)
//{
//	//升序，建大堆
//	//降序，建小堆
//
//	for (int i = 1; i < n; i++)
//	{
//		AdjustUp(arr, i);
//	}
//
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&arr[0], &arr[end]);
//		AdjustDown(arr, 0, end);
//		end--;
//	}
//}

void TOP()
{
	Heap hp;
	HeapInit(&hp);

	int arr[] = { 34,453,3,4,56,36,6,3,7,34,6,36,3,7,2,4,46,534,7,3,7673,56 };
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		HeapPush(&hp, arr[i]);
	}

	int k = 0;
	scanf("%d", &k);
	while (k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}

	HeapDestroy(&hp);
}

int main()
{
	//test1();
	//test2();
	TOP();

	return 0;
}

总结

二叉树在各种领域和问题中都有广泛的应用，文件系统、数据库、表达式求值、代码编译、网络路由、Huffman 编码等场景。
堆排序利用了二叉堆的性质，通过构建最大堆（或最小堆）来实现排序。整个排序过程分为两个阶段：首先通过数组构建一个最大堆，然后不断将堆顶元素与堆的最后一个元素交换并调整堆，最终得到一个有序数组。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-08-19，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构