栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

二叉树链式结构

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

二叉树链式结构

不要有太大压力李
生活不是选择而是热爱李

文章目录呀
  • ⭐前言⭐
  • 0️⃣手搓一个二叉树
  • 1️⃣二叉树的遍历
    • 1. 深度优先遍历
      • ① 前序遍历
      • ② 中序遍历
      • ③ 后序遍历
    • 2. 广度优先遍历
      • 层序遍历
      • 层序遍历代码
  • 2️⃣求二叉树的节点个数
    • 方法1
      • 缺陷:
    • 方法2
  • 3️⃣求叶子节点数量
  • 4️⃣求第k层节点的个数
  • 5️⃣查找某个节点
  • 6️⃣求二叉树的深度
  • 7️⃣二叉树的销毁
  • 8️⃣判断是否为完全二叉树
  • ⭐写在最后⭐

⭐前言⭐

我们已经学习了二叉树的顺序结构 —>完全二叉树 、 堆
但那是特殊的二叉树,对于普通的二叉树,不适合利用顺序结构来存储
因为可能存在很多的空间浪费,如:

数组中很多空间是没有存放数据的!

0️⃣手搓一个二叉树
//手搓一个二叉树
BTNode* CreateBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

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

	//没赋值的 一定都是NULL

	return node1;	
}

int main()
{
	BTNode* root = CreateBinaryTree();
	return 0;
}

得到这样一个二叉树:

1️⃣二叉树的遍历

首先我们要知道两个名词:深度优先遍历和广度优先遍历

  • 深度优先遍历

深度优先遍历:DFS

沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当沿着某个节点已经到达最深(已经到空),然后就回去遍历该节点的另一条边。

如图就是一种深度优先遍历

深度优先遍历又分为先序遍历,后序遍历,中序遍历
区别就是访问根节点的先后

  • 广度优先遍历:

广度优先遍历 BFS(Breadth-First-Search),也就是宽度优先,BFS是从根节点开始,沿着树的某一层遍历树的节点,优先横向遍历。

1. 深度优先遍历 ① 前序遍历

前序遍历的顺序就是 访问根节点的操作发生在遍历其左右子树之前
如图:

代码:
注:我们用 # 表示空,前序结果应该是 1 2 3 # # # 4 5 # # 6 # #

// 二叉树的前序遍历
void PreOrder_Traversal(BTNode* root)
{
	//如果节点为空树
	if (root == NULL)
	{
		printf("# ");
		return;
	}

	//先访问 根节点数据 -->左子树 --> 右子树
	printf("%d ", root->val);//访问根节点数据
	PreOrder_Traversal(root->left);//找左子树
	PreOrder_Traversal(root->right);
}

前序打印结果:

② 中序遍历

同理,中序遍历就是 遇到根节点并不访问,先去找左子树,左子树找完回来再访问根,然后再去找右子树
在前序遍历的基础上 如图:

代码:

//二叉树的中序遍历
void InOrder_Traversal(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

	//先左子树 --> 根 --> 右子树
	InOrder_Traversal(root->left);
	printf("%d ", root->val);
	InOrder_Traversal(root->right);
}
③ 后序遍历

后序遍历: 先访问左子树,然后访问右子树,左右子树都找完了再回来访问根节点

//二叉树的后序遍历
void PostOrder_Traversal(BTNode*root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

	//左树 --> 右树 --> 根
	PostOrder_Traversal(root->left);
	PostOrder_Traversal(root->right);
	printf("%d ", root->val);
}
2. 广度优先遍历 层序遍历

层序遍历就是一种广度优先遍历,这种遍历会先访问同一层的节点,而不会一昧的往深了走
但是二叉树的结构是这样的:

每一个根 只能去找他的左右孩子,而并没有兄弟节点去找每一层的兄弟
那么怎么实现呢?

—— 利用队列!

我们可以利用队列 先进先出的性质 来实现对每一层的遍历

  1. 根节点入队,然后出队,把根节点的左孩子left和右孩子right入队
  2. left出队的同时 left->left和left->right入队
  3. right出队的同时right->left和right->right入队
  4. 继续上面过程,直到队列为空


但是这里有个问题就是 完成层序遍历需要队列这个数据结构
C语言没有库!所以只能我们自己写一个队列的数据结构!

队列的实现比较简单,博主就不写了哈~~

层序遍历代码
void TreeLevel(BTNode* root)
{
	Queue q;//创建队列
	QueueInit(&q);//队列初始化
	//如果root为空,那么直接返回
	if (root == NULL)
		return;
	//然后把root根节点push到队列
	// 注意push的是 树的一整个节点:因为需要利用该节点的拷贝去找下一个节点!(递归)
	QueuePush(&q, root);
	// 进入循环
	while (!QueueEmpty(&q))//如果队列不为空
	{
		//拿到队头元素(树节点指针的拷贝)
		BTNode* front = QueueFront(&q);
		// 拿到之后出队即可
		//先打印一下
		printf("%d ", front->val);
		QueuePop(&q);
		
		//当前节点出队之后 带入root的两个子节点(即下一层入队)
		if (front->left)//如果左节点不为空,入队
		{
			QueuePush(&q, front->left);
		}
		if (front->right)//右节点不为空,入队!
		{
			QueuePush(&q, front->right);
		}
		//如果左右节点都为空,那么直接把该front出队即可。
	}
}
2️⃣求二叉树的节点个数 方法1

因为二叉树是递归实现的,所以如果简单地像链表那样,在函数内部定义一个局部变量通过遍历求出节点个数,会涉及到一个问题:每一次递归都会创建一个新的局部变量,实际上这个局部变量并不会起到计数的作用

所以我们可以利用一个全局变量记录节点的个数
思路很简单:前序遍历,如果节点不为空 count++

int count = 0;//定义全局变量
void TreeSize1(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	++count;
	TreeSize1(root->left);
	TreeSize1(root->right);
}
缺陷:
  1. 每一次调用都要先在主函数中把count清0,因为count的值是上一次求节点个数的值,并没有被清零!
  2. 多线程问题:count是全局变量,可能被多个线程同时利用,这样计算出的count就有问题!
方法2

我们可以利用返回值+递归的方法
也就是分治思想:
root的节点数量 = 1 + root->left的节点数量 + root->right的节点数量

int TreeSize2(BTNode* root)
{
	return root == NULL ? 0 : 1 + TreeSize2(root->left) + TreeSize2(root->right);
}
3️⃣求叶子节点数量

叶子节点有一个特征:
节点的左孩子和右孩子都为NULL
所以这就是我们遍历的一个限制条件

  1. 如果节点为空 返回0
  2. 如果节点的左右孩子都为空:返回1 (是叶子节点)
  3. 如果都不满足,说明正在查找的该节点不是叶子节点,我们递归去找该节点的左右孩子
int TreeLeafSize(BTNode* root)
{
	return root == NULL ? 0 : ((root->left == NULL && root->right == NULL) ? 1 : TreeLeafSize(root->left) + TreeLeafSize(root->right));
}
4️⃣求第k层节点的个数


int KLevelSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	//如果 k不等于1 那么继续递归
	return KLevelSize(root->left, k - 1) + KLevelSize(root->right, k - 1);
	
}
5️⃣查找某个节点

BTNode* TreeFind(BTNode* root,BTDataType x)
{
	if (root == NULL)
	{
		return NULL;	
	}
	if (root->val == x)
	{
		return root;
	}
	// 简单的逻辑: 先找左树 找到就返回,找不到去找右树,如果也找不到 返回空 
	// 每一个子树都这样进行!
	BTNode* left = TreeFind(root->left, x);
	if (left)
		return left;
	BTNode* right = TreeFind(root->right, x);
	if (right)
		return right;


	//这里也可以不用找右树,直接返回右树的结果
	// 因为右树也有两个结果:1. 空 ,2. 找到了
	//return TreeFind(root->right, x);
	return NULL;


	//以下是三目的方法
	

}
6️⃣求二叉树的深度

分析:
求root的深度 也就是求出 1 + 左右孩子深度的较大值

int TreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeDepth(root->left);
	int right = TreeDepth(root->right);
	int max = left > right ? left : right;
	return 1 + max;
	//return left > right ? left + 1 : right + 1;
}
7️⃣二叉树的销毁

最直接的想法是 直接遍历就好了啊 把每一个节点销毁释放!
但是 要用后序哦!!
因为如果用前序,先把根销毁了怎么找 左右孩子呢?找不到了!


利用后序 销毁的顺序应该是 3 2 5 6 4 1
我们可以每一次销毁之前打印一下验证对不对

void TreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	//如果不为空
	TreeDestory(root->left);
	TreeDestory(root->right);
	//销毁之前打印一下
	printf("%d ", root->val);
	free(root);
}

8️⃣判断是否为完全二叉树

我们知道完全二叉树的最后一层是 从左到右依次编号的,最后一层不可以存在有右子树而没有左子树的情况
如图就是一个非完全二叉树 3的后面为空,而空的后面还有非空的节点!

那么如何判断是否为空呢?
我们可以借助队列!


如果是完全二叉树 应该是这样

代码

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root == NULL)// 完全二叉树也可以是空树
		return true;

	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取出 队头
		BTNode* front = QueueFront(&q);	
		// 然后出队
		QueuePop(&q);
		if (front)
		{
			// 这里不需要判断front的左右是否为空 空也需要入队
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else// 如果front为空直接break
		{
			break;
		}

		
	}

	//退出循环的时候  说明遇到了空
	// 再一次进入循环 找一找有没有非空
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);//这里必须先pop一下 否则就死循环了!
		// 如果遇到非空 返回false
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
			
	}
	QueueDestory(&q);
	//来到这 说明 第一次遇到空之后全都是空了
	return true;


}
⭐写在最后⭐

2022 / 06 / 06 高考倒计时:1天
去年这个时候我正在准备明天的高考
今年,我的复读的同学正在紧张地复习
是的去年我也考砸了,但是决定人生的并不是高考
今后路还长
放平心态,不要去想什么高考多难,不要去听一些 “千军万马过独木桥”
拿出平时做练习的姿态去迎接这场考试就好
2022的考生,高考加油!
愿你们前程 如你们所愿

✨感谢阅读~ ✨
❤️码字不易,给个赞吧~❤️

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/956261.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号