首页 > 其他分享 >【数据结构】二叉树和堆

【数据结构】二叉树和堆

时间：2024-08-03 18:28:25浏览次数：14  
标签：arr php int 二叉树 数据结构 root 节点

 

一、二叉树

1.二叉树的基本概念

在C语言中，二叉树是一种基础的数据结构，它由节点组成，每个节点包含数据元素以及指向其他节点的指针。下面是二叉树的基本概念以及如何在C语言中表示和操作它。
节点（Node）：二叉树的每个元素称为节点，每个节点都有一个数据域和两个指针域，通常称为左指针和右指针。

根节点（Root）：位于树顶部的节点，它是树中唯一没有父节点的节点。

子节点（Children）：如果节点A的左指针或右指针指向节点B，则节点B是节点A的子节点。

父节点（Parent）：如果一个节点有子节点，那么这个节点就是其子节点的父节点。

叶节点（Leaf）：没有子节点的节点称为叶节点或外部节点。

深度（Depth）：节点的深度是从根节点到该节点的唯一路径上的边的数量。

高度（Height）：节点的高度是从该节点到最远叶节点的最长路径上的边的数量。树的高度是根节点的高度。

层（Level）：节点的层是从根节点开始计数，根节点在第1层，它的子节点在第2层，以此类推。

2.二叉树的基本性质

（1）节点的度：

  • 二叉树中每个节点的度都不超过2，即每个节点最多有两个子节点。

（2）深度和高度：

  • 二叉树的深度是从根节点到最远叶节点的最长路径上的边的数量。
  • 节点的高度是从该节点到最远叶节点的最长路径上的边的数量。

（3）层次：

  • 二叉树的根节点位于第1层，它的子节点位于第2层，以此类推。

（4）叶节点数量：

  • 对于任何非空二叉树，如果叶子数为n0，度为2的节点数为n2，则有n0 = n2 + 1。

（5）节点总数：

  • 对于任何非空二叉树，如果节点总数为N，度为2的节点数为n2，度为1的节点数为n1，则有N = n0 + n1 + n2，即N = n1 + 2*n2 + 1。

（6）路径和高度：

  • 对于具有n个节点的二叉树，所有节点的路径和等于(n-1) * n / 2。

3.特殊的二叉树

(1)满二叉树：如果二叉树的所有非叶节点都具有两个子节点，则该树被称为满二叉树。

如果一个二叉树的层数为k，且结点总数为2^{k}-1, 则它就是满二叉树。


(2)完全二叉树：如果二叉树的所有层都是满的，除了最后一层可能不完全填满，且最后一层的节点都靠左排列，则该树被称为完全二叉树。


根据满⼆叉树的特点可知：

  • 若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有2^{i-1}个结点
  • 若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是2^{h}-1
  • 若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度h=\log _{2}(n+1) ( log以2为底， n+1 为对数)

4.二叉树存储结构

二叉树一般可以使用两种结构存储，一种是顺序结构，另一种是链式结构。

（1）实现链式结构的二叉树

用链表来表示一棵二叉树，即⽤链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址，其结构如下：

//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	int data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
 a. 前中后序遍历

 前序遍历（先序遍历）的访问顺序：根结点、左结点、右结点。

中序遍历的访问顺序：左结点、根结点、右结点。

后序遍历的访问顺序：左结点、右结点、根结点。

代码如下：

//前序遍历---根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历--左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

//后序遍历 ---左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
b.二叉树结点个数
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
c.二叉树叶子结点个数
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
d.二叉树第K层结点个数
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}
e.⼆叉树的深度/高度
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);

	return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}
f.⼆叉树查找值为x的结点
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode* leftFind =  BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind =  BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}
g.层序遍历(需要额外借助队列数据结构）
//层序遍历
//借助数据结构---队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		//队头节点的左右孩子入队列
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	//队列为空
	QueueDestroy(&q);
}
h.判断二叉树是否为完全二叉树(额外借助队列数据结构）
//判断二叉树是否为完全二叉树
//---队列
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//队列不一定为空
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

（2）实现顺序结构的二叉树——堆

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

5.堆

（1）堆的概念与结构

在C语言中，堆（Heap）是一种特别的完全二叉树，它通常用于实现优先队列。堆分为最大堆和最小堆两种类型：

  • 最大堆（Max Heap）：在最大堆中，对于任意节点i，其父节点的值总是大于或等于子节点的值。
  • 最小堆（Min Heap）：在最小堆中，对于任意节点i，其父节点的值总是小于或等于子节点的值。

堆具有以下性质：

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

堆通常使用数组来实现，数组中的元素按照层次遍历的顺序存储。对于数组中的任意元素array[i]：

  1. 其左子节点为array[2*i + 1]
  2. 其右子节点为array[2*i + 2]
  3. 其父节点为array[(i-1)/2]

（ 2）堆的实现

堆底层为数组，因此定义堆的结构为：

//定义堆的结构---数组

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;//有效的数据个数
	int capacity;//空间大小
}HP;

//默认初始化堆
void HPInit(HP* php);

//利用给定数组初始化堆
void HPInitArray(HP* php,HPDataType* arr,int n);

//堆的销毁
void HPDestroy(HP* php);

//堆的插入
void HPPush(HP* php, HPDataType x);

//堆的删除
void HPPop(HP* php);

//删除堆顶数据
HPDataType HPTop(HP* php);

// 判空
bool HPEmpty(HP* php);

//求size
int HPSize(HP* php);

//向上调整算法
void AdjustUp(HPDataType* arr,int child);

//向下调整算法
void AdjustDown(HPDataType* arr,int n,int parent);
a.向上调整算法
  • 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后
  • 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustUp(HPDataType* arr,int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			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;
}
 向上调整算法建堆的时间复杂度为：O（n*\log _{2}n)
b.向下调整算法
  • 将堆顶元素与堆中最后⼀个元素进行交换
  • 删除堆中最后⼀个元素
  • 将堆顶元素向下调整到满⾜堆特性为止

void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	//while (parent < n)
	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(php && php->size);

	//arr[0]  arr[size-1]
	Swap(&php->arr[0], &php->arr[php->size - 1]);

	--php->size;

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

	
}
向下调整算法建堆的时间复杂度为：O（n)

(3)堆的应用

a.堆排序

 前提条件：必须提供现成的数据结构堆。

数组建堆，首尾交换，交换后队尾数据从堆中删除，将堆顶数据向下调整，选出次大的数据。

升序建大堆，降序建小堆。

void HeapSort(int* arr, int n)
{
	//建堆
	//升序---大堆
	//降序----小堆

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

	//循环将堆顶数据跟最后位置（会变化，每次减少一个数据）的数据进行交换
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}
堆排序时间复杂度为：O（nlogn)
b.TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，⼀般情况下数据量都比较大。
比如：专业前10名、世界500强等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能⼀下子全部加载到内存中)。

最佳的⽅式就是⽤堆来解决，基本思路如下：
1）⽤数据集合中前K个元素来建堆
前k个最⼤的元素，则建⼩堆
前k个最⼩的元素，则建⼤堆
2）⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素
将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(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() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void TOPk()
{
	int k = 0;
	printf("请输入k:");
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail!");
		exit(1);
	}
	int* minHeap = (int*)malloc(k * sizeof(int));
	if (minHeap == NULL)
	{
		perror("malloc fail!");
		exit(2);
	}

	//从文件中读取前K个数据
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}

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

	int x = 0;
	while (fscanf(fout,"%d",&x) != EOF)
	{
		//读取到的数据跟堆顶的数据进行比较
		//比堆顶值大，交换入堆
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			AdjustDown(minHeap, 0, k);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}

	fclose(fout);
}
TOP-K时间复杂度为：O（n)=k+(n-k)\log _{2}k

点赞收藏+关注，进阶大佬不迷路~~~

标签：arr,php,int,二叉树,数据结构,root,节点
From： https://blog.csdn.net/2401_83948390/article/details/140832531

相关文章

  • 代码随想录算法训练营Day18 | Leetcode 530 二叉搜索树的最小绝对差 Leetcode 236 二
    前言今天有一道题目没写，二叉搜索树中的众数，有点太难理解了，先放一放。Leetcode530二叉搜索树的最小绝对差题目链接：530.二叉搜索树的最小绝对差-力扣（LeetCode）代码随想录题解：代码随想录(programmercarl.com)思路：二叉搜索树的性质是中序遍历为升序的，所以我们想找最小绝......
  • 数据结构-------------------二叉排序树的查找
    #include<stdio.h>#include<stdlib.h>typedefstructBSTNode{intkey;structBSTNode*lchild;structBSTNode*rchild;}BSTNode,*BSTTree;//递归实现二叉排序树的查找操作BSTNode*BSTSearch(BSTTreeT,intkey){if(T......
  • Day18 二叉树Part6
    目录任务530.二叉搜索树的最小绝对差思路501.二叉搜索树中的众数思路236.二叉树的最近公共祖先思路心得体会任务530.二叉搜索树的最小绝对差给你一个二叉搜索树的根节点root，返回树中任意两不同节点值之间的最小差值。差值是一个正数，其数值等于两值之差的绝对值。思路......
  • 先(后)序遍历确定唯一二叉树
    在二叉树的先序遍历或后序遍历序列中，如果我们记录了空节点的位置（通常用特殊符号如'#'表示），就足以唯一确定一棵二叉树的结构。这种方法的关键在于，记录空节点的位置能够帮助我们在遍历序列中准确地还原出树中节点的结构信息。因此，只要给出了先序遍历或后序遍历序列以及空节点的位置，......
  • 数据结构--------二叉树的定义及遍历操作的实现
    /*二叉树的链式存储以及基本操作*/#include<stdio.h>#include<stdlib.h>//树的节点typedefstructBTNode{intdata;structBTNode*lchild;structBTNode*rchild;}BTNode,*BTTree;/......
  • Python数据结构第二天—循环链表、树、二叉搜索树
    双向链表之前学习的单向链表只能从头遍历到尾，过程是单向的，而双向链表既可以从头遍历到尾，也可以从尾遍历到头，它的过程是双向的。既然它是双向的，那么我们要实现一个双向链表，就需要在单向链表的基础上，给每一个结点增加一个向前的引用。双向链表的创建："""我们要实现的是一......
  • 【数据结构】大根堆和小根堆
    大根堆实现逻辑从整棵树的最后一颗子树开始调整，每次都让根节点和左右孩子去比较，如果根节点比左右孩子的最大值要小，那么就将这两个值进行交换，然后此时这颗子树变成了大根堆，再看下一颗树然后对下一颗树进行相同的处理方法，后面的子树依次交换：当每棵子树都是大根堆的情况......
  • 【代码随想录训练营第42期 Day17打卡 二叉树Part5-LeetCode 654.最大二叉树 617.合并
    目录一、做题心得二、题目与题解题目一：654.最大二叉树题目链接题解：递归题目二：617.合并二叉树题目链接题解：递归（前序遍历）题目三：617.合并二叉树题目链接题解：BFS层序遍历 题目四：98.验证二叉搜索树题目链接题解：递归（中序遍历）三、小结一、做题心得今天是代码随想......
  • 【数据结构算法经典题目刨析（c语言）】判断链表是否有环（图文详解）
    ......
  • 数据结构———栈
    目录基本概念常用操作栈的实现1. 基于链表的实现2. 基于数组的实现实现之间的对比栈的典型应用基本概念栈（stack）是一种遵循先入后出逻辑的线性数据结构。我们可以将栈类比为枪械上的弹夹，如果想打出底部的子弹，则需要先将上面的子弹依次移走。我们将子弹替换为......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99