【数据结构】遍历二叉树(递归思想)-->赋源码

欢迎来到我的Blog,点击关注哦💕

前言

二叉树遍历是指按照一定的顺序访问二叉树中的每个节点,使得每个节点恰好被访问一次。遍历是二叉树上最重要的运算之一,是二叉树上进行其他运算的基础。

一、二叉树遍历概念

在这里插入图片描述

二叉树遍历分类

  • 前序遍历 :根节点–>左子树–>右子树。在前序遍历时,首先访问根节点,然后依次访问左子树和右子树。
  • 中序遍历 : 左子树–>根节点–>右子树。在中序遍历时,首先访问左子树,然后访问根节点,最后访问右子树。
  • 后序遍历:左子树–>右子树–>根节点。在后序遍历时,首先访问左子树和右子树,然后访问根节点。
  • 层序遍历: 由顶层到底层,一层一层遍历。

二叉树其他操作

树节点的个数树深度树 k 层的个数查找节点

二、二叉树遍历实现

我们以下面为例子:

1
2
3
4
5
6
7
8
9
2_right_NULL
3_left_NULL

2.1 二叉树建立

1.定义一个结构体,分别有左右两个指针。

2.为每一个节点创建孔家。

3.创建二叉树,并如上图连接。

//定义结构体

typedef int BTTypeData;

typedef struct BinaryTree
{
	BTTypeData data;

	struct BinaryTree* left;
	struct BinaryTree* right;
}BinaryTree;

//创建空间

BinaryTree* BuyBinaryTree(BTTypeData x)
{
	BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

//建树

BinaryTree* CreateBinaryTree()
{

	BinaryTree* node1 = BuyBinaryTree(1);
	BinaryTree* node2 = BuyBinaryTree(2);
	BinaryTree* node3 = BuyBinaryTree(3);
	BinaryTree* node4 = BuyBinaryTree(4);
	BinaryTree* node5 = BuyBinaryTree(5);
	BinaryTree* node6 = BuyBinaryTree(6);
	BinaryTree* node7 = BuyBinaryTree(7);
	BinaryTree* node8 = BuyBinaryTree(8);
	BinaryTree* node9 = BuyBinaryTree(9);

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


	return node1;
}

2.2 前序遍历

在递归实现中,前序遍历的基本思想是对于每一个节点,先访问该节点,然后对其左子树进行前序遍历,最后对其右子树进行前序遍历。如果当前节点为空,则直接返回。这种方法的优点是代码简洁明了,易于理解,但缺点是可能导致栈溢出,特别是在处理深度较大的二叉树时。

遍历结果:1–> 2–> 3 –>7 –>4 –>5 –>6–> 8 –>9

//前序遍历
void PreOrder(BinaryTree* root)
{
	
	
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

2.2 中序遍历

首先对左子树进行中序遍历,然后访问根节点,最后对右子树进行中序遍历。

遍历结果:3 –>7–>2–> 1–> 5–> 4–>8–> 6–> 9

void InOrder(BinaryTree* root)
{


	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}

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

}

2.3 后序遍历

递归函数首先访问左子树,然后访问右子树,最后访问根节点。如果当前节点为空,则直接返回。

遍历结果:7–> 3–> 2–> 5–> 8 –>9 –>6 –>4 –>1

//后序遍历
void PostOrder(BinaryTree* root)
{


	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}

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

}

2.4 层序遍历

在二叉树的层序遍历是指按照树的层次顺序,从上到下、从左到右逐层访问二叉树的节点。这种遍历方式可以帮助我们了解二叉树的结构布局,特别是在处理树状数据结构时非常有用。

利用队列的特点,有关队列可参考 栈和队列

  • 将根节点入队。

  • 当队列不为空时,从队列中取出一个节点,访问该节点。

  • 将该节点的左右子节点(如果存在)入队。

  • 重复步骤2和3,直到队列为空。

遍历结果:1–> 2 –>4 –>3 –>5 –>6 –>7 –>8 –>9

//层序遍历

void LevelOrder(BinaryTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	Queue TBT;
	QueueInit(&TBT);

	if (root)
		QueuePush(&TBT, root);
	
	while (!QueueEmpty(&TBT))
	{
		BinaryTree* front = QueueTop(&TBT);
		QueuePop(&TBT);
		printf("%d ", front->data);

		if (front->left)
			QueuePush(&TBT, front->left);
		if (front->right)
			QueuePush(&TBT, front->right);

	}

	QueueDestroy(&TBT);

}

2.5 二叉树的节点个数

利用递归的方法,左右子树调用,如果该节点为NULL 便会返回0,否则返回1。

//树的结点个数

int TreeSize(BinaryTree* root)
{

	return root == 0 ? 0:TreeSize(root->left) + TreeSize(root->right) + 1;

}

2.6 二叉树的深度

利用 leftright记录左右子树的个数,然后比较 选择较大的一个。

如图:在这里插入图片描述

//树的高度

int TreeHeight(BinaryTree* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int left = TreeHeight(root->left) ;
	int right = TreeHeight(root->right);

	return left > right ? left + 1 : right + 1;

}

2.7 二叉树第K层的个数

假设查找第三层,K为3 ,每次递归K–,知道K== 1 的时候 返回1。

//层的个数

int TreeKLevel(BinaryTree* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}


	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);


}

2.8 二叉树查找结点

节点的查找,如果节点为NULL饭后NULL,如果此节点的data等于x,返回节点的地址。

//查找节点

BinaryTree* TreeFind(BinaryTree* root, BTTypeData x)
{

	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}

	BinaryTree* lret = TreeFind(root->left, 7);
	if (lret)
		return lret;
	BinaryTree* rret = TreeFind(root->right, 7);
	if (rret)
		return rret;
	return NULL;
}

源码

queue.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



//初始化
void QueueInit(Queue* ps)
{
	assert(ps);

	ps->head = ps->tail = NULL;

	ps->szie = 0;

}

//销毁
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->szie = 0;
}

//入队
void QueuePush(Queue* ps,QDataType x)
{
	assert(ps);

	QNode* newcode = (QNode*)malloc(sizeof(QNode));
	if (newcode == NULL)
	{
		perror("malloc fail");
		return ;
	}
	newcode->next = NULL;
	newcode->data = x;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newcode;
		
	}
	else

	{
		
		ps->tail->next = newcode;
		ps->tail = newcode;
	}

	ps->szie++;

}

//删除
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head != NULL);
	assert(!QueueEmpty(ps));

	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QNode* next = ps->head->next;
		free(ps->head);
		ps->head = next;

	}
	ps->szie--;
}

//大小
int QueueSize(Queue* ps)
{
	assert(ps);

	return ps->szie;
}

//判空队
bool QueueEmpty(Queue* ps)
{
	assert(ps);

	return ps->szie == 0;
}

//出队头
QDataType QueueTop(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

//出队尾
QDataType QueueBack(Queue* ps)
{
	assert(ps);

	return ps->tail->data;
}



queue.h

#pragma once

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

typedef struct BinaryTree* QDataType;

typedef struct QNode
{
	struct QNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode*head;
	QNode*tail;
	 
	int szie;
}Queue;


//单链表的实现,FIFO

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

travelling_binary_tree

#define _CRT_SECURE_NO_WARNINGS

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

#include "queue.h"

//定义结构体

typedef int BTTypeData;

typedef struct BinaryTree
{
	BTTypeData data;

	struct BinaryTree* left;
	struct BinaryTree* right;
}BinaryTree;

//创建空间

BinaryTree* BuyBinaryTree(BTTypeData x)
{
	BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

//建树

BinaryTree* CreateBinaryTree()
{

	BinaryTree* node1 = BuyBinaryTree(1);
	BinaryTree* node2 = BuyBinaryTree(2);
	BinaryTree* node3 = BuyBinaryTree(3);
	BinaryTree* node4 = BuyBinaryTree(4);
	BinaryTree* node5 = BuyBinaryTree(5);
	BinaryTree* node6 = BuyBinaryTree(6);
	BinaryTree* node7 = BuyBinaryTree(7);
	BinaryTree* node8 = BuyBinaryTree(8);
	BinaryTree* node9 = BuyBinaryTree(9);

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


	return node1;
}

//前序遍历
void PreOrder(BinaryTree* root)
{
	
	
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历

void InOrder(BinaryTree* root)
{


	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}

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

}

//后序遍历
void PostOrder(BinaryTree* root)
{


	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}

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

}

//层序遍历

void LevelOrder(BinaryTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	Queue TBT;
	QueueInit(&TBT);

	if (root)
		QueuePush(&TBT, root);
	
	while (!QueueEmpty(&TBT))
	{
		BinaryTree* front = QueueTop(&TBT);
		QueuePop(&TBT);
		printf("%d ", front->data);

		if (front->left)
			QueuePush(&TBT, front->left);
		if (front->right)
			QueuePush(&TBT, front->right);

	}

	QueueDestroy(&TBT);

}

//树的结点个数

int TreeSize(BinaryTree* root)
{

	return root == 0 ? 0:TreeSize(root->left) + TreeSize(root->right) + 1;

}

//树的高度

int TreeHeight(BinaryTree* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int left = TreeHeight(root->left) ;
	int right = TreeHeight(root->right);

	return left > right ? left + 1 : right + 1;

}

//层的个数

int TreeKLevel(BinaryTree* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}


	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);


}

//查找节点

BinaryTree* TreeFind(BinaryTree* root, BTTypeData x)
{

	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}

	BinaryTree* lret = TreeFind(root->left, 7);
	if (lret)
		return lret;
	BinaryTree* rret = TreeFind(root->right, 7);
	if (rret)
		return rret;
	return NULL;
}

int main()
{
	BinaryTree* root = CreateBinaryTree();


	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	LevelOrder(root);
	printf("\n");


	printf("TreeSize : %d\n", TreeSize(root));

	printf("TreeHeight : %d\n", TreeHeight(root));

	printf("TreeKLevel : %d\n", TreeKLevel(root, 3));

	printf("TreeFind : %p\n", TreeFind(root, 1));




	return 0; 
}

}

//查找节点

BinaryTree* TreeFind(BinaryTree* root, BTTypeData x)
{

if (root == NULL)
{
	return NULL;
}

if (root->data == x)
{
	return root;
}

BinaryTree* lret = TreeFind(root->left, 7);
if (lret)
	return lret;
BinaryTree* rret = TreeFind(root->right, 7);
if (rret)
	return rret;
return NULL;

}

int main()
{
BinaryTree* root = CreateBinaryTree();

PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
LevelOrder(root);
printf("\n");


printf("TreeSize : %d\n", TreeSize(root));

printf("TreeHeight : %d\n", TreeHeight(root));

printf("TreeKLevel : %d\n", TreeKLevel(root, 3));

printf("TreeFind : %p\n", TreeFind(root, 1));




return 0; 

}


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

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

相关文章

Windows 11 中安装 Docker Desktop 并安装镜像

本该主要介绍在 Windows 11 中安装 Docker Desktop 时的一些准备工作&#xff0c;以及该如何下载和安装&#xff0c;然后分别使用管理界面和 Docker 命令安装两个镜像。 一、准备工作 在 Windows 11 中安装 Docker Desktop 前&#xff0c;需要做一些准备。打开 【Windows 功能…

大模型是什么?能干嘛?怎么学?

引言 随着人工智能技术的飞速发展&#xff0c;大模型研究已成为该领域的一大热点。这些研究覆盖了众多方向&#xff0c;每个方向都面临着独特的研究焦点和挑战。本文将逐一探讨一些备受关注的研究方向&#xff0c;包括检索增强生成RAG、大模型Agent、Mamba、MoE、LoRA等&#…

字符数组基础知识及题目

死识。。。 字符该如何存储呢&#xff1f;这一点我们在以前就接触过了。用char来存储。 如何输入一个单词呢&#xff1f; char a[10002]; scanf("%s",a); 就不用地址符了。 如何输入句子呢&#xff1f; char a[100002]; gets(a); gets是读入句子的&#xff0c…

如何阅读?从阅读中学阅读—《海绵阅读法》

大家好&#xff0c;我是老三&#xff0c;最近读了《海绵阅读法&#xff1a;如何吸收一本书的精华》&#xff0c;第一次阅读教如何阅读的书&#xff0c;整理一番读书笔记&#xff0c;分享给大家。 读书动机 我前一阵子写了篇文章&#xff0c;2024Q1&#xff0c;盘点我看过的54本…

防止Selenium被检测 Google Chrome 125

背景 最近在使用selenium自动播放学习课程&#xff0c;相信大家也有一些类似的使用场景。 能自动化的事情&#xff0c;绝不自己干。 为防止被检测是机器人做题&#xff0c;刷视频&#xff0c;需要做一些小调整。 先来看作为服务方维护者&#xff0c;是如何检测是Selenium打…

【算法-力扣】73.矩阵置零,一文彻底搞懂!

目录 一、题目描述 二、解题思路 三、参考答案 一、题目描述 矩阵置零 给定一个 m x n 的矩阵&#xff0c;如果一个元素为 0 &#xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 进阶&#xff1a; 一个直观的解决方案是使用 O(mn) 的额外空间&#x…

甄嬛传熹贵妃上户口:如果让他陪你过冬天,那朕能不能睡中间?贝叶斯模型推导爸爸去哪儿

关注微信公众号 数据分析螺丝钉 免费领取价值万元的python/java/商业分析/数据结构与算法学习资料 背景 《甄嬛传》是大家耳熟能详的宫廷剧&#xff0c;其中复杂的宫斗情节和深刻的人物刻画让人津津乐道。甄嬛因为与皇帝(四郎)闹翻了&#xff0c;去甘露寺待了一段时间&#x…

0613,基本数据类型,表达式

题目1&#xff0c;选做&#xff1a; 假设 int n 0xCAFE; 请用表达式完成下面操作 (拓展题&#xff1a;不要求每个同学都写) (a) 测试最后 4 位中是不是最少有 3 位为 1. (b) 逆转字节序(i.e.,使 n 0xFECA) (c) 旋转 4 位 (i.e., 使 n 0xECAF) 答案代码/补&#xff1a; …

Elasticsearch 认证模拟题 - 18

一、题目 为一个索引&#xff0c;按要求设置以下 dynamic Mapping 一切 text 类型的字段&#xff0c;类型全部映射成 keyword一切以 int_ 开头命名的字段&#xff0c;类型都设置成 integer 1.1 考点 字段的动态映射 1.2 答案 # 创建索引和索引模板 PUT my_index {"m…

关于Linux ping 不通外网

网关为第三段为137那么子网ip第三段必须为137且IPaddr必须为137 将主机虚拟适配器连接到此网络必须勾上&#xff0c;不然vmnet适配器在windows将找不到 ping www.baidu.com不行的话试着勾上桥接模式应该是不行在勾上取消勾上桥接模式最后勾上nat模式

【Pr剪辑】工具栏的认识

目录 1.选择工具&#xff08;快捷键V&#xff09;1.1 选择1.2 移动素材1.3 框选1.4缩放1.5复制 2.钢笔工具&#xff08;快捷键P&#xff09;3.文字工具&#xff08;T&#xff09;4.剃刀&#xff08;C &#xff09;5.比例拉伸工具&#xff08;R&#xff09;6.波纹编辑工具&#…

从零开始开发知识付费APP:在线教育系统源码详解

今天&#xff0c;小编将从零开始&#xff0c;详细讲解在线教育系统的源码开发过程&#xff0c;帮助你打造一款功能完善的知识付费APP。 一、需求分析与规划 1.1 市场调研 在开始开发之前&#xff0c;首先要进行市场调研&#xff0c;了解当前市场上的主要竞争对手和用户需求。…

易保全网络赋强公证系统,“公证赋强+科技赋能”双重增信

网络赋强公证系统是一种创新的法律服务模式&#xff0c;旨在通过线上方式赋予债权文书强制执行效力。具体来说&#xff0c;该系统结合了互联网技术与公证业务&#xff0c;允许公证机构根据当事人的申请&#xff0c;利用互联网公证技术手段对互联网上的债权文书进行公证&#xf…

【SpringBoot系列】覆盖重写第三方Jar包中类

要覆盖或重写一个第三方JAR包中的类&#xff0c;你可以使用以下几种方法&#xff1a; 方法一&#xff1a;使用类路径优先级 Java的类加载机制会优先加载类路径&#xff08;classpath&#xff09;中最先找到的类。因此&#xff0c;如果你在自己的项目中定义了一个与第三方JAR包…

ESP32-C6 闪耀 Apple WWDC24|使用 Embedded Swift 构建 Matter 设备

WWDC 是苹果公司的年度全球开发者大会&#xff0c;旨在向全球开发者展示最新技术和工具。在今年的 WWDC 2024 上&#xff0c;苹果宣布将 Swift 语言扩展至嵌入式设备领域。大会技术讲座中&#xff0c;乐鑫 ESP32-C6 也现身官方 Demo “Go Small with Embedded Swift​​​​​​…

【译】SQLAlchemy文档:SQLAlchemy 统一教程

SQLAlchemy Unified Tutorial SQLAlchemy 是 Python SQL工具包和ORM&#xff0c;它为应用程序开发人员提供了 SQL 的全部功能和灵活性。它提供了一整套企业级持久性模式&#xff0c;专为高效和高性能的数据库访问而设计。 SQLAlchemy呈现为两层API&#xff1a;Core和ORM&…

沃尔玛自养号测评:优势与技术要求解析

沃尔玛自养号测评是一种卖家在沃尔玛平台上提升店铺权重和排名的营销手段。传统运营策略的局限性日益显现&#xff0c;如营销手段单一、难以应对市场竞争等。因此&#xff0c;许多卖家为了提升店铺权重和排名&#xff0c;选择了自养号测评这一技术手段。 以下是对沃尔玛自养号…

使用CSS常见问题解答卡片

常见问题解答卡片 效果展示 CSS 知识点 CSS 选择器的使用background 渐变背景色运用CSS 综合知识运用 页面整体布局 <div class"container"><h1>经常问的问题</h1><!-- 这里只是展示一个项目 --><div class"tab"><in…

Apollo9.0 PNC源码学习之Control模块(三)—— 基于双环PID的纵向控制

本文将对Apollo的纵向控制器进行讲解&#xff0c;看完本文&#xff0c;你将会对百度Apollo的纵向控制有更深的理解 前面文章&#xff1a; Apollo9.0 PNC源码学习之Control模块&#xff08;一&#xff09; Apollo9.0 PNC源码学习之Control模块&#xff08;二&#xff09; 1 纵向…

如何用Vue3和p5.js打造一个令人惊叹的3D球体在线展示

本文由ScriptEcho平台提供技术支持 项目地址&#xff1a;传送门 使用 p5.js 创建交互式 3D 图形 应用场景介绍 p5.js 是一个用于创建交互式图形和动画的 JavaScript 库。它被广泛用于教育、艺术和设计领域&#xff0c;让开发者可以轻松创建具有吸引力的可视化效果。 代码基…