【数据结构第十六节】实现链式结构二叉树（详细递归图解—呕心沥血版！）

news/2025/2/25 7:12:52

必须有为成功付出代价的决心，然后想办法付出这个代价。云边有个稻草人-CSDN博客

这节课挺抽象（苦笑），没事，我会帮你！干就完了！

（目录在路上）

正文开始——

引言

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

//创建链式结构二叉树的结构->二叉链
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType* data;
	struct BinaryTreeNode* left;//指定当前结点的左孩子
	struct BinaryTreeNode* right;//指定当前结点的右孩子
}BTNode;

二叉树的创建方式比较复杂，为了更好地步入到二叉树内容中，我们先手动创建一棵链式二叉树。

//申请结点
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc faile!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

BTNode* CreateTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);

    //改变指针指向，使其成为一棵链式二叉树
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;

	return node1;

}

回顾二叉树的概念，二叉树分为空树和非空二叉树，非空二叉树由根节点、根节点的左子树和根节点的右子树组成的。

根节点的左子树和右子树分别又是由子树节点、子树结点的左子树和子树结点的右子树组成的，因此二叉树是递归式的，后序链式二叉树的操作基本都是按照概念实现的。

一、前中后序遍历

1.1 遍历规则

按照规则，二叉树的遍历有：前序 /中序/ 后序的遍历结构：

  • 前序遍历（Preorder Traversal 亦称先序遍历）：访问根结点的操作发生在遍历其左右子树之前，访问的顺序：根节点、左子树、右子树
  • 中序遍历（Inorder Traversal）：访问根节点的操作发生在遍历其左右子树之间，访问顺序：左子树、根节点、右子树
  • 后序遍历（Postorder Traversal）：访问根节点的操作发生在遍历其左右子树之后，访问顺序：左子树、右子树、根节点

1.2 代码实现

（1）前序遍历

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

该图里面，前序遍历结果为：1 2 4 3 

（2）中序遍历

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

中序遍历结果为：4  2  1  3 

（3）后序遍历

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

二、结点个数以及高度等

2.1 二叉树结点个数

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

2.2 二叉树叶子结点的个数

//二叉树叶子结点个数
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);
}

2.3 二叉树第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);
}

2.4 求二叉树的高度/深度

//求二叉树高度/深度
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;
}

2.5 二叉树查找值为x的节点

//二叉树找值为x的结点
BTNode* BinaryFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode* leftFind = BinaryFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}

	BTNode* rightFind = BinaryFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

2.6 二叉树的销毁

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

	BinaryTreeDestroy(&((*root)->left));//注意这里的传参，传的是地址
	BinaryTreeDestroy(&((*root)->right));

	free(*root);
	*root = NULL;
}

三、层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进行层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点， 以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。

我们要提前实现一个队列的结构，（1）在下面的函数里面我们创建一个队列，并且别忘记队列的初始化和销毁，（2）同时要注意，我们前面学习的队列里面的数据是整型类型，这次我们要将结点插入到队列里面，所以我们要将队列里面的数据类型改为二叉树节点的类型，并且我们不能直接写二叉树节点的缩写那样，我们要写成 struct BinaryTreeNode* / struct BTNode* ，反正都不能少 struct，不然会报错。（3）还有一点，在我们的层序遍历代码里面当while循环结束的时候队列为NULL，下一步再进行队列的销毁的时候就会报错，因为我们前面实现的队列的销毁里面队列为空时不能销毁，所以assert会报错，所以我们可以把队列的销毁里面判断队列是否为空的那一步给注释掉。

提及到的代码需要注意的点都在下面，多看看！

//创建节点的结构
typedef struct BinaryTreeNode* QUDatatype;//这里需要注意
typedef struct QueueNode
{
	QUDatatype data;
	struct QueueNode* next;
}QueueNode;
//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));//往这看，注释掉这里也没事，就算队列为空也没关系
    //此时pcur为NULL，进不去循环

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//层序遍历
void LevelBinaryTree(BTNode* root)
{
	//先创建一个队列
	Queue q;
	QueueInit(&q);

	//取根节点入队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//打印队头数据
		BTNode* Front = QueueFront(&q);
		printf("%d ", Front->data);
		QueuePop(&Front);
		if (Front->left)
		{
			QueuePush(&q, Front->left);
		}
		if (Front->right)
		{
			QueuePush(&q, Front->right);
		}
	}
	QueueDestroy(&q);
}

四、判断是否是完全二叉树

//判断是否是完全二叉树
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;
}

【图解】

五、本节课代码汇总

 Queue.h

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

//创建节点的结构
typedef struct BinaryTreeNode* QUDatatype;
typedef struct QueueNode
{
	QUDatatype data;
	struct QueueNode* next;
}QueueNode;

//创建队列的结构
typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);

//入队列
void QueuePush(Queue* pq,QUDatatype x);

//判空
bool QueueEmpty(Queue* pq);

//出队列
void QueuePop(Queue* pq);

//取队头数据
QUDatatype QueueTop(Queue* pq);

//去队尾数据
QUDatatype QueueBack(Queue* pq);

//去队列中有效数据的个数
int QueueSize(Queue* pq);

//销毁
void QueueDestroy(Queue* pq);

Queue.c

#include"Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//入队列
void QueuePush(Queue* pq, QUDatatype x)
{
	assert(pq);
	//现申请新的结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//如果为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* pcur = pq->phead->next;
		free(pq->phead);
		pq->phead = pcur;
	}
	pq->size--;
}

//取队头数据
QUDatatype QueueTop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->phead->data;

}

//去队尾数据
QUDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	/*QueueNode* pcur = pq->phead;
	int count = 0;
	while (pcur)
	{
		count++;
		QueuePop(pq);
		pcur = pq->phead;
	}*/
	/*return count;*/

	return pq->size;
}

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

Tree.h

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

//创建链式结构二叉树的结构->二叉链
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;//指定当前节点的左孩子
	struct BinaryTreeNode* right;//指定当前节点的右孩子
}BTNode;

//申请节点
BTNode* BuyNode(BTDataType x);

//前序遍历
void PreOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PosOrder(BTNode* root);

//求二叉树节点的个数
int BinaryTreeSize(BTNode* root);

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);

//第K层节点个数
int BinaryTreeLevelKSize(BTNode* root,int k);

//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root);

//找X的结点
BTNode* BinaryFind(BTNode* root, BTDataType x);

//二叉树的销毁
void BinaryTreeDestroy(BTNode** root);

//层序遍历
void LevelBinaryTree(BTNode* root);

//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c

#include"Tree.h"
#include"Queue.h"

//申请节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc faile!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

//前序遍历-
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 PosOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PosOrder(root->left);
	PosOrder(root->right);
	printf("%d ", root->data);
}

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

//二叉树叶子结点个数
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);
}

//第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);
}

//求二叉树高度/深度
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;
}

//二叉树找值为x的结点
BTNode* BinaryFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode* leftFind = BinaryFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}

	BTNode* rightFind = BinaryFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

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

	BinaryTreeDestroy(&((*root)->left));
	BinaryTreeDestroy(&((*root)->right));

	free(*root);
	*root = NULL;
}

//层序遍历
void LevelBinaryTree(BTNode* root)
{
	//先创建一个队列
	Queue q;
	QueueInit(&q);

	//取根节点入队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//打印队头数据
		BTNode* Front = QueueFront(&q);
		printf("%d ", Front->data);
		QueuePop(&Front);
		if (Front->left)
		{
			QueuePush(&q, Front->left);
		}
		if (Front->right)
		{
			QueuePush(&q, Front->right);
		}
	}
	QueueDestroy(&q);
}

//判断是否是完全二叉树
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;
}

 test.c

#include"Tree.h"

BTNode* CreateTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;

	return node1;

}

int main()
{
	BTNode* node = CreateTree();
	/*PreOrder(node);
	printf("\n");
	InOrder(node);
	printf("\n");
	PosOrder(node);*/

	printf("NodeSize:%d\n", BinaryTreeSize(node));
	printf("NodeSize:%d\n", BinaryTreeSize(node));
	printf("NodeSize:%d\n", BinaryTreeSize(node));

	printf("LeafSize：%d\n", BinaryTreeLeafSize(node));

	printf("%d\n", BinaryTreeLevelKSize(node, 3));

	printf("%d\n", BinaryTreeDepth(node));

	BTNode* find = BinaryFind(node, 22);
	printf("%s\n", find == NULL ? "没找到\n" : "找到了！\n");

	LevelBinaryTree(node);

	bool ret = BinaryTreeComplete(node);
	printf("%s\n", ret == false ? "不是完全二叉树\n" : "是完全二叉树\n");

	BinaryTreeDestroy(&node);

	return 0;
}

我感觉这节递归还是挺难理解的，感觉函数递归进行的过程不好想象，层层递归就比较难以理解透彻，我会忘记自己递归到那个地方了绕不回去了就很烧脑筋，难想的时候呢我就得画出函数进行栈帧的创建与销毁，这样一步一步来还是比较好的。对了，我画的红箭头还有绿箭头可以看成是函数栈帧的创建与销毁。把详细的函数的栈帧的创建与销毁多想几遍函数的递归应该就会好想象一点了。这节课我啃了两天了，后续还得多回顾理解多敲代码，告诉自己，别畏难，很难，但也得一步一步走下去，总不能放弃吧，那就坚定不移的前进！（这节课的博客真难写呀啊啊啊——）

知识点有不对的地方还请多多指教（抱拳）

完——

终——Relaxing Time！

好好休息一下，继续战斗！昨天又发现了一首好听的歌(＾－＾)V）分享给你

           ————————————《Falling U》————————————

Falling U_T-ara_高音质在线试听_Falling U歌词|歌曲下载_酷狗音乐

至此结束——

我是云边有个稻草人

期待与你的下一次相遇！


http://www.niftyadmin.cn/n/5865148.html

相关文章

解决升级flutter 3.29.0 Gradle8.7后报错 Exception has occurred. MissingPluginException

解决升级flutter 3.29.0 Gradle8.7后报错 Exception has occurred. MissingPluginException

Flutter 升级后 MissingPluginException 及 Proguard 混淆问题解决方案 问题描述 在将 Flutter 从 3.24.5 升级到 3.29&#xff0c;以及 Gradle 升级到 8.7.0 之后&#xff0c;原生自己写的Flutter 插件在运行时出现以下错误&#xff1a; Exception has occurred. MissingPl…
阅读更多...
Java中文件操作和IO（如果想知道Java中有关文件操作和IO的知识，那么只看这一篇就足够了！）

Java中文件操作和IO（如果想知道Java中有关文件操作和IO的知识，那么只看这一篇就足够了！）

前言&#xff1a;在 Java 中&#xff0c;输入输出&#xff08;I/O&#xff09;是常见的操作&#xff0c;字节流和字符流是处理文件和数据的核心类&#xff0c;本文将介绍 InputStream、OutputStream、Reader 和 Writer 类的基本用法。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨想…
阅读更多...
Linux系统：服务器常见服务默认IP端口合集

Linux系统：服务器常见服务默认IP端口合集

服务器的默认IP端口取决于所使用的协议和服务类型。以下是一些常见服务和协议的默认端口&#xff1a; 服务端口实例&#xff1a; HTTP服务 默认端口&#xff1a;80 说明&#xff1a;用于普通的HTTP网页访问。例如&#xff0c;访问 http://example.com 时&#xff0c;默认使用8…
阅读更多...
世界棒球经典赛：各大阵营·棒球1号位

世界棒球经典赛：各大阵营·棒球1号位

当大谷翔平的速球与阿库尼亚的球棒在东京巨蛋相遇&#xff0c;当委内瑞拉的黄金一代与波多黎各的岛国意志正面碰撞&#xff0c;世界棒球经典赛&#xff08;WBC&#xff09;的舞台早已超越竞技场范畴&#xff0c;成为人类运动天赋的万神殿。这份参赛阵容不仅汇聚了全球90%的现役…
阅读更多...
《计算机视觉》——图像拼接

《计算机视觉》——图像拼接

图像拼接 图像拼接是将多幅有重叠区域的图像合并成一幅全景或更大视角图像的技术&#xff0c;以下为你详细介绍&#xff1a; 原理&#xff1a;图像拼接的核心原理是基于图像之间的特征匹配。首先&#xff0c;从每幅图像中提取独特的特征点&#xff0c;如角点、边缘点等&#x…
阅读更多...
Hadoop--Secondary NameNode工作机制，作用及与NameNode HA的区别

Hadoop--Secondary NameNode工作机制，作用及与NameNode HA的区别

Secondary NameNode 主要用于辅助 NameNode 进行元数据的管理和检查点&#xff08;Checkpoint&#xff09;的生成。 1. Secondary NameNode 的工作机制详解 Secondary NameNode 的工作机制可以分为以下步骤&#xff1a; ① Secondary NameNode 询问 NameNode 是否需要 Check…
阅读更多...
为什么java从json中获取值有数据类型，而从xml中获取值没有数据类型？

为什么java从json中获取值有数据类型，而从xml中获取值没有数据类型？

在 Java 中处理 JSON 和 XML 数据时，表面上看起来从 JSON 中获取的值具有数据类型，而从 XML 中获取的值没有，但实际上这是由 JSON 和 XML 的本质特点决定的。 JSON 的本质特点 语法结构：JSON（JavaScript Object Notation）是基于键值对的文本格式，结构清晰，适合表示数据…
阅读更多...
首次使用WordPress建站的经验分享（一）

首次使用WordPress建站的经验分享（一）

之前用过几种内容管理系统（CMS），如：dedeCMS、phpCMS、aspCMS，主要是为了前端独立建站，达到预期的效果，还是需要一定的代码基础的，至少要有HTML、Css、Jquery基础。 据说WordPress 是全球最流行的内容管理系统CMS，从现在开始记录一下使用WordPress 独立建站的步骤 选购…
阅读更多...
最新文章

Copyright @ 2022~2023