二叉树顺序结构及链式结构

一.二叉树的顺序结构

1.定义：使用数组存储数据，一般使用数组只适合表示完全二叉树，此时不会有空间的浪费

注：二叉树的顺序存储在逻辑上是一颗二叉树，但是在物理上是一个数组，此时需要程序员自己想清楚调整数据时应该怎样调整

2.堆

(1)定义：集合中所有元素按照完全二叉树的顺序存储在一个一维数组中，并满足Ki<=K2*i+1且K2*i+2(或Ki<=K2*i+1且K2*i+2)的规律，则称之为堆

(2)性质：

1>堆中某个节点的值总是不大于(或不小于)其父节点的值

2>堆是一颗完全二叉树

3>大堆：任何一个父节点的值>=孩子的值

    小堆：任何一个父节点的值<=孩子的值

(3)堆的实现(以小堆为例)

1>堆的结构体定义：数组指针(用于存储数据),有效数据个数，空间容量大小

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* a;//数组指针
	int size;//有效数据个数
	int capacity;//有效空间大小
}HP;

2>堆的初始化：

//堆的初始化
void HPInit(HP* ph)
{
	assert(ph);
	ph->a = NULL;
	ph->size = ph->capacity = 0;
}

3>堆的销毁：

//堆的销毁
void HPDestory(HP* ph)
{
	assert(ph);
	free(ph->a);
	ph->a = NULL;
	ph->size = ph->capacity = 0;
}

4>向堆中插入数据：

**思路：将数据插在原数据的最后面，在不断向上调整以保证插入数据后仍为小堆 

**画图解释

**代码实现

//向堆内插入数据
void HPPush(HP* ph, HeapDataType x)
{
	assert(ph);
	//判断是否需要增容
	if (ph->size == ph->capacity)
	{
		int newcapacity = ph->capacity * 2 == 0 ? 4 : ph->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(ph->a, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ph->a = tmp;
		ph->capacity = newcapacity;
	}
	ph->a[ph->size] = x;
	ph->size++;
	AdjustUp(ph->a, ph->size-1);

}

5>向上调整数据：

思路：找孩子的父亲，判断父亲是否大于孩子，若大于则交换父子地位，继续向上调整

 注：由于堆是完全二叉树，一个父亲最多有两个孩子，所以父亲的下标应该是孩子的下标减一再除以2，即parent=(child-1)/2;

//向上调整
void AdjustUp(HeapDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent= (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

6>删除根部数据：

思路：先交换根部数据和最后一个数据，再删除根部数据，同时将最后一个数据向下调整以保证删除后的堆仍为小堆

//删除堆顶数据(根位置)
void HPPop(HP* ph)
{
	assert(ph);
	Swap(&ph->a[0], &ph->a[ph->size - 1]);
	ph->size--;
	AdjustDown(ph->a, ph->size, 0);
}

7>向下调整数据：

**思路：先找左右孩子中较小的那个孩子，与父亲相比，若父亲大于孩子，则交换父子地位，继续向下调整

注：由于堆是完全二叉树，一个父亲最多有两个孩子，所以左孩子的下标应该是父亲的下标乘以2再加1，即child=parent*2+1;

**画图解释

**代码实现

//向下调整
void AdjustDown(HeapDataType* a, int size, int parent)
{
	//默认左孩子小
	int child = parent * 2 + 1;
	while (child < size)
	{
		//找左右孩子中小的那一个
		if ((child+1) < size && a[child+1] < a[child])
		{
			child ++;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}

	}
}

(4)堆的应用

1>堆排序

1.1)思路：注：降序：建小堆，升序建大堆

             将数组中的元素建堆，交换最后的数据与首位数据，并进行向下调整，让size--，循环操                 作，直至完成排序

1.2)时间复杂度：O（N*log N）

1.3)画图解释：

1.4)代码实现

void HeapSort(int* a, int size)
{
	//将数组建堆
	for (int i = 1; i < size; i++)
	{
		AdjustUp(a, i);
	}
	int end = size - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

2>TOP_K(以求前K个最大的数据为例)

2.1)定义：求出数据中前K个最大的数据（或前K个最小的数据）

2.2)思路：

思路一：创建一个含N个节点的大堆，PopK次，即可获取前K个最大的数据

              弊端：当N非常大时，在创建节点时需要占用大量的内存

思路二：建一个含K个节点的小堆，将剩余的N-K个数据与堆顶数据相比，若大于堆顶数据则入                    堆进行向下调整，否则进行下一个比较

注：思路二更优，效率高

2.3)代码实现

void TOP_K(int* a,int n,int k) 
{
    //在文件中读取数据
	const char* fp = "data.txt";
	FILE* fout = fopen(fp, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

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

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

	//将剩余的n-k个数据于堆顶数据相比
	int x = 0;
	while (fscanf(fout,"%d",&x)!=EOF)
	{
		if (a[0]<x)
		{
			a[0] = x;
			AdjustDown(a, k, 0);
		}
	}

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

2.4)数据验证

思路：将N的节点的数据模上N，是他们处于小于N的状态，在随机挑K个数据将他们调大于N，若在选出来的K个数据为大于N的数据，则说明该程序执行的是选取前K个最大的数据的指令

二.二叉树的链式结构(以二叉链表为例)

注：在二叉树的实现中多用递归来达到一层一层向下查找的目的(所以读者需要熟练掌握递归的相关知识)

1.定义：用链表表示一颗二叉树，即用链表表示元素之间的逻辑关系

2.二叉树节点的定义：该节点内存储的数据，指向左孩子的指针，指向右孩子的指针

typedef int BTNodeData;
typedef struct BinaryTreeNode
{
	BTNodeData val;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

3.二叉树的创建(根据前序遍历来创建二叉树)：

以数组abd##e#h##cf##g##构建二叉树

1>思路：1)若当前数据为#，则返回NULL；

               2)否则开辟一个二叉树节点root，将该数据赋给val,给左，右孩子赋值，通过调用函数递                 归实现

2>代码实现：

//创建二叉树
BTNode* BTCreate(BTNodeData* a, int* pi)
{
	if (a[*pi] == ‘#’)
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->val = a[*pi];
	(*pi)++;
	root->left = BTCreate(a,pi);
	root->right = BTCreate(a, pi);

	return root;
}

4.二叉树的前序遍历：

1>访问顺序：根，左子树，右子树

2>思路：如果根为空，打印N，什么都不返回；否则先打印根的值，再调用该函数，将左子树的地址作为参数，然后调用该函数，将右子树的地址作为参数，利用递归实现前序遍历

3>代码实现

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

5.二叉树的中序遍历

1>访问顺序：左子树，根，右子树

2>思路：与前序遍历类似

3>代码实现

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

6.二叉树的后序遍历

1>访问顺序：左子树，右子树，根

2>思路：与前序遍历类似

3>代码实现

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

7.二叉树的层序遍历

1>思路：利用队列，让上一层的节点先入队列，在删除他们时，带进去下一层，若节点为空不进队列

2>代码实现：

//层序遍历
void BTLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->val);

		//当节点不为空时入队列
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if(front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestory(&q);
}

8.二叉树的节点个数

1>思路：1)如果根节点为空，返回0；

               2)否则返回左子树的节点数+右子树的节点数+1(利用递归法实现左右子树节点数的计算)

2>代码实现：

//二叉树节点个数
int BTSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return  BTSize(root->left) + BTSize(root->right) + 1;
}

9.二叉树的叶子节点个数

1>思路：1)如果根为空，返回0；

               2)如果左右孩子均为空，返回1；

               3)否则返回左子树叶子数+右子树叶子数(利用递归实现左右子树叶子数的计算)

2>代码实现：

//二叉树叶子节点个数
int BTLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTLeafSize(root->left) + BTLeafSize(root->right);
}

10.二叉树第K层节点个数

1>思路：1)如果根为空返回0；

               2)如果k==1，返回1；

               3)否则返回左子树的k-1层+右子树的k-1层

注：将树一层一层向下压，直至出现两种特殊情况

2>代码实现：

//二叉树第K层节点个数
int BTLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k - 1);
}

11.二叉树查找值为X的节点

1>思路：1)若根为空，返回空；

               2)若根的值等于待查找数据，返回根的地址；

              3)否则查找左子树是否有值为X的节点若有返回该节点的地址，否则查找右子树是否有值                  为X的节点若有返回该节点的地址，若左右子树均没有是否有值为X的节点，则返回空

2>代码实现：

//二叉树查找值为X的节点
BTNode* BTFind(BTNode* root, BTNodeData x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}

	//比较左子树是否有节点值为x
	BTNode* ret1 = BTFind(root->left, x);
	if (ret1!=NULL)
	{
		return ret1;
	}

	//比较右子树是否有节点值为x
	BTNode* ret2 = BTFind(root->right, x);
	if (ret2 != NULL)
	{
		return ret2;
	}

	//左右子树中均未找到值为x的节点
	return NULL;
}

12.树的高度

1>思路：1)若根为空，返回0；

               2)否则记录并分别求左右子树的高度，哪个值更大哪个即为树的高度

注：每次都需记录所求的树的高度，否则会出现走到上一层忘了下一层的情况，导致反复求某棵树高度的情况

2>代码实现：

//二叉树的高度
int BTHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int HeightLeft = BTHeight(root->left)+1;
	int HeightRight = BTHeight(root->right)+1;

	return HeightLeft > HeightRight ? HeightLeft  : HeightRight ;
}

13.二叉树的销毁

1>思路：用后序遍历的思想先销毁左右子树，再销毁根(若先销毁根，销毁根后，无法找到左右子树)

2>代码实现

//二叉树的销毁
void BTDestory(BTNode* root)
{
	if (root == NULL)
		return;

	BTDestory(root->left);
	BTDestory(root->right);
	free(root);

}

14.判断二叉树是否为完全二叉树

1>思路：无论节点是否为空都入队列，当检查到第一个空节点时，开始遍历后面的节点看是否有非空节点，若有，则不是完全二叉树，否则是完全二叉树

2>代码实现

//二叉树是否为完全二叉树
bool BTComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		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)
		{
			QueueDestory(&q);
			return false;
		}
	}

	QueueDestory(&q);
	return true;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/638246.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

vue小记——小组件（1）

vue小记——小组件（1）

代码&#xff1a; <template><div><el-steps :active"active" finish-status"success" simple><el-step title"数据导入"><i class"fa fa-cloud-upload fa-icon-custom" slot"icon"></i…
阅读更多...
一文带你了解所有常用排序算法

一文带你了解所有常用排序算法

目录 快速排序 堆排序 桶排序 归并排序 拓扑排序 本文主要介绍那些我在刷题过程中常用到的排序算法: 快速排序,堆排序,桶排序,归并排序,拓扑排序 其余算法例如冒泡,插入这种效率特别低的算法就不介绍了,用的可能性极小 每一个算法都将采用例题加解释的方式进行介绍 快速…
阅读更多...
创意无限，设计所需——Affinity Designer for Mac/win强大登场

创意无限，设计所需——Affinity Designer for Mac/win强大登场

在当今数字设计领域&#xff0c;寻找一款功能强大、操作简便的矢量图设计软件并不容易。然而&#xff0c;Affinity Designer 凭借其出色的性能和令人惊艳的功能&#xff0c;在众多设计师中脱颖而出&#xff0c;成为了首选软件之一。今天&#xff0c;让我们一起来探索 Affinity …
阅读更多...
【深度学习】与【PyTorch实战】

【深度学习】与【PyTorch实战】

目录 一、深度学习基础 1.1 神经网络简介 1.2 激活函数 1.3 损失函数 1.4 优化算法 二、PyTorch基础 2.1 PyTorch简介 2.2 张量操作 2.3 构建神经网络 2.4训练模型 2.5 模型评估 三、PyTorch实战 3.1 数据加载与预处理 3.2 模型定义与训练 3.3 模型评估与调优 3…
阅读更多...
618购物节快递量激增，EasyCVR视频智能分析助力快递网点智能升级

618购物节快递量激增，EasyCVR视频智能分析助力快递网点智能升级

随着网络618购物节的到来&#xff0c;物流仓储与快递行业也迎来业务量暴增的情况。驿站网点和快递门店作为物流体系的重要组成部分&#xff0c;其安全性和运营效率日益受到关注。为了提升这些场所的安全防范能力和服务水平&#xff0c;实施视频智能监控方案显得尤为重要。 一、…
阅读更多...
领券拿外卖返利红包，最低0元吃外卖

领券拿外卖返利红包，最低0元吃外卖

小蚕荟是利用本地资源和自媒体优势构建的“本地生活服务”平台&#xff0c;总部位于杭州&#xff0c;旨在为用户提供热门的吃喝玩乐本地生活服务类产品。布局已覆盖杭州、南京、上海等一二线城市。 小蚕荟是一款专为用户吃外卖省钱的生活工具&#xff0c;单单可返利15元起&…
阅读更多...
【教学类-58-03】黑白三角拼图03（4*4宫格）总数算不出+随机抽取10张

【教学类-58-03】黑白三角拼图03（4*4宫格）总数算不出+随机抽取10张

背景需求&#xff1a; 【教学类-58-01】黑白三角拼图01&#xff08;2*2宫格&#xff09;256种-CSDN博客文章浏览阅读318次&#xff0c;点赞10次&#xff0c;收藏12次。【教学类-58-01】黑白三角拼图01&#xff08;2*2宫格&#xff09;256种https://blog.csdn.net/reasonsummer/…
阅读更多...
数组-求和为k的连续子数组

数组-求和为k的连续子数组

一、题目描述 二、题目思路 这里注意&#xff1a;题目要求时间、空间复杂度都为O(n)&#xff0c;所以不能直接通过双层循环来暴力解(时间复杂度为O&#xff08;n&#xff09;)&#xff0c;可以使用Map实现。 1. 遍历数组计算sum(i)&#xff0c;Map记录sum值第一次出现的位置&…
阅读更多...
STM32 MAP文件结合固件文件分析

STM32 MAP文件结合固件文件分析

文章目录 加载域的结束地址并不是固件的结束地址&#xff1f;ROM中执行域的描述RAM中执行域的描述问题分析 中断向量表在固件中的存储位置代码段在固件中的位置只读数据Regin$$Table RW Data段其中的内部机理 总结 MAP 文件分析可以参考之前的文章 程序代码在未运行时在存储器…
阅读更多...
LeetCode刷题之HOT100之多数元素

LeetCode刷题之HOT100之多数元素

2024/5/21 起床走到阳台&#xff0c;外面绵柔细雨&#xff0c;手探出去&#xff0c;似乎感受不到。刚到实验室&#xff0c;窗外声音放大&#xff0c;雨大了。昨天的两题任务中断了&#xff0c;由于下雨加晚上有课。这样似乎也好&#xff0c;不让我有一种被强迫的感觉&#xff0…
阅读更多...
SpringCloud Alibaba Nacos分类配置--多方案配置隔离

SpringCloud Alibaba Nacos分类配置--多方案配置隔离

文章目录 Nacos 分类配置(实现配置隔离)1.DataID 方案需求分析/图解配置实现测试 2.Group 方案需求分析/图解配置实现修改application.yml修改bootstrap.yml测试 3.Namespace 方案需求分析/图解配置实现修改application.yml修改bootstrap.yml测试 Namespace/Group/Data ID 关系…
阅读更多...
基于springboot+vue+Mysql的逍遥大药房管理系统

基于springboot+vue+Mysql的逍遥大药房管理系统

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…
阅读更多...
EfficientSAM分割对象后求其中图像中的高

EfficientSAM分割对象后求其中图像中的高

1 分割对象 EfficientSAM https://github.com/yformer/EfficientSAM 2 计算在图像中最高点即y值最小点 import os import cv2def read_images(folder_path):image_files [f for f in os.listdir(folder_path) iff.endswith(".jpg") or f.endswith(".png&quo…
阅读更多...
文心智能体-恋爱专家

文心智能体-恋爱专家

⭐简单说两句⭐ ✨ 正在努力的小叮当~ &#x1f496; 超级爱分享&#xff0c;分享各种有趣干货&#xff01; &#x1f469;‍&#x1f4bb; 提供&#xff1a;模拟面试 | 简历诊断 | 独家简历模板 &#x1f308; 感谢关注&#xff0c;关注了你就是我的超级粉丝啦&#xff01; &a…
阅读更多...
邮件系统数据面临的安全问题及解决方法

邮件系统数据面临的安全问题及解决方法

随着电子邮件的普及&#xff0c;邮件系统已成为企业、学校、个人等用户之间进行信息交流的重要工具。然而&#xff0c;随着数据量的增加和用户对邮件系统的依赖&#xff0c;邮件系统数据安全问题也逐渐凸显。下面U-Mail技术张工就给大家讲解一下邮件系统数据面临的主要安全问题…
阅读更多...
CCF-GESP 等级考试 2023年9月认证C++四级真题

CCF-GESP 等级考试 2023年9月认证C++四级真题

2023年9月 一、单选题&#xff08;每题2分&#xff0c;共30分&#xff09; 第 1 题 ⼈们所使⽤的⼿机上安装的App通常指的是&#xff08; &#xff09;。 A. ⼀款操作系统B. ⼀款应⽤软件C. ⼀种通话设备D. 以上都不对 第 2 题 下列流程图的输出结果是&#xff1f;( ) A. 9B.…
阅读更多...
【30天精通Prometheus：一站式监控实战指南】第4天：node_exporter从入门到实战：安装、配置详解与生产环境搭建指南，超详细

【30天精通Prometheus：一站式监控实战指南】第4天：node_exporter从入门到实战：安装、配置详解与生产环境搭建指南，超详细

亲爱的读者们&#x1f44b;   欢迎加入【30天精通Prometheus】专栏&#xff01;&#x1f4da; 在这里&#xff0c;我们将探索Prometheus的强大功能&#xff0c;并将其应用于实际监控中。这个专栏都将为你提供宝贵的实战经验。&#x1f680;   Prometheus是云原生和DevOps的…
阅读更多...
搜索插入位置 ---- 二分查找

搜索插入位置 ---- 二分查找

题目链接 题目: 分析: 因为数排序数组, 所以具有"二段性", 可以使用二分查找题目中, 我们如果找到目标值 , 则返回下标, 如果没找到目标值, 应该返回的是>target的第一个位置, 所以应该将数组分成< target 和 > target当<target时, 应该移动left, left…
阅读更多...
3DMax

3DMax

先转换为可编辑多边形 按“1”选择为点&#xff0c;点击目标焊接&#xff08;CtrlShiftw&#xff09;&#xff0c;然后点击一个顶点拉到另一个定点上&#xff1b; 选择一个面&#xff0c;点击塌陷&#xff08;CtrlAltC&#xff09;&#xff0c;四点合并为一个点&#xff1b; …
阅读更多...
《艺术大观》知网艺术刊：可加急， 出刊上网快

《艺术大观》知网艺术刊：可加急， 出刊上网快

《艺术大观》 《艺术大观》征文通知 《艺术大观》期刊诚邀学者、艺术家和文化工作者积极投稿&#xff0c;共同探索艺术领域的前沿问题&#xff0c;促进学术交流和艺术创作的发展。我们欢迎各类艺术形式的研究与评论&#xff0c;包括但不限于绘画、雕塑、音乐、舞蹈、戏剧、电…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站