【数据结构】二叉树＜遍历＞

【二叉树遍历】|-前序-中序-后序-层序-|

  • <二叉树的遍历>
    • 1.前序遍历【递归】
    • 2.中序遍历【递归】
    • 3.后序遍历【递归】
    • 4.层序遍历【非递归】
      • 4.1判断是否是完全二叉树

<二叉树的遍历>

在学习二叉树遍历之前我们先了解下二叉树的概念。
二叉树是：
1.空树
2.非空：根节点，根节点的左子树，根节点的右子树构造。

在这里插入图片描述
学习二叉树结构，最简单的方式就是遍历了。
二叉树的遍历就是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个节点只操作一次。
访问结点所做的操作依赖于具体的应用问题。

二叉树的遍历分为
1.<前序遍历>[Preorder Traversal]
访问根节点的操作发生在遍历左右子树之前。
也就是对于一个节点，它要求先访问这个节点的内容，然后再去遍历左子树，当左子树遍历完后，再遍历右子树。

2.<中序遍历>[Inorder Traversal]
访问根节点的操作发生在遍历其左右子树之中
也就是对于一个节点，它要求先遍历左子树，当左子树都遍历完，再回来访问节点里的内容，然后再遍历右子树。

3.<后续遍历>[Postorder Traversal]
访问根节点的操作发生在遍历其左右子树之后
也就是对于一个节点，它要求先遍历完左子树，再遍历完右子树，最后回来的时候再访问节点的内容。
4.<层序遍历>
层序遍历，顾名思义，一层一层的遍历即可。
从第一层开始遍历，遍历完第一层再遍历下一层。

我们为了好验证二叉树的遍历操作，手动创造一个二叉树，也就是下图在这里插入图片描述
这样，用代码来实现就是这样：

#include <stdio.h>
#include <stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* ret =(BTNode*)malloc(sizeof(BTNode));
	ret->data = x;
	ret->left = NULL;
	ret->right = NULL;
	return ret;
}
BTNode* CreatBinaryTree()
{
	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;
	return node1;
}

1.前序遍历【递归】

我们为了真正展现前序遍历在二叉树中是如何实现的，将空节点也打印出来。这样就可以清晰的看出来遍历的过程。

// 二叉树前序遍历-<根节点-左子树-右子树>-
void PreOrder(BTNode* root)
{
	if (root == NULL)//如果遇到空节点就返回
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);//先访问根节点内容，打印完节点内容后再进入左子树。
	PreOrder(root->left);//进入左子树
	PreOrder(root->right);//进入右子树
}

在这里插入图片描述

在这里插入图片描述

根据结果你能想明白怎么遍历的吗？

递归展开图：

在这里插入图片描述

在这里插入图片描述

2.中序遍历【递归】

// 二叉树中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);//先遍历左子树
	printf("%d ", root->data);//遍历完左子树后再访问节点内容
	InOrder(root->right);//访问完节点内容后再遍历右子树
}

在这里插入图片描述
在这里插入图片描述
递归展开图
在这里插入图片描述

3.后序遍历【递归】

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

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

在这里插入图片描述
而后序遍历这种特点很适合用在二叉树的销毁上去。

因为相比较前序遍历，如果先销毁了节点，那它的左右子树就无法找到了。
但后续遍历不一样，后序遍历是先遍历左右子树，最后再访问节点。
所以我们只要使用后序遍历，先销毁左右子树，再销毁节点就可以了。
比如：二叉树的销毁

void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BTreeDestroy(root->left);//先销毁左子树
	BTreeDestroy(root->right);//再销毁右子树
	free(root);//最后再销毁节点
	root = NULL;
}

4.层序遍历【非递归】

上面三个都是属于递归形式的遍历，层序遍历是非递归的。

怎么进行层序遍历呢？
这个就需要用到队列来解决了。
思想：
出上一层，带入下一层。

一开始让根节点入队列，那队列中就有元素存在，不是空队列了。
然后接下来就是不断的出队列中的根节点，每一次出队列中的根节点时，都要将
该根节点的孩子插入到队列的后面去。 也就是出根节点，带入它们的孩子进来。直到队列中没有数据为止。

在这里插入图片描述
不过注意的是，队列中不是真正节点，而是指向节点的指针，如果将节点插入进去，那怎么找到它们的孩子呢？
所以我们插入进入的是指向节点的指针。

typedef struct BTreeNode* QData;//注意这里将队列中元素的类型改成指向节点的指针
typedef struct QNode
{
	struct QNode* next;
	QData data;//队列的元素是指向节点的指针
}QNode;
//因为队列的数据结构操作需要找尾，这就需要传多个参数了，很麻烦，所以我们再分装个结构体将多个数据变成一个
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
void QueueInit(Queue *pq);//初始化队列
void QueueDestroy(Queue *pq);//销毁队列
void QueuePush(Queue*pq ,QData x);//入队，从队尾插入一个数据，尾删
void QueuePop(Queue *pq);//出队，从队头删除数据，头删
bool QueueEmpty(Queue *pq);//判断队列是否为空
int QueueSize(Queue*pq);//获得队列有效数据个数大小
QData QueueFront(Queue*pq);//获取队头数据
QData QueueBack(Queue*pq);//获取队尾数据

#include "queue.h"
void QueueInit(Queue* pq)//初始化队列
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueueDestroy(Queue* pq)//销毁队列
{
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QData x)//入队，从队尾插入一个数据，尾删
{
	assert(pq);
/*	QNode* cur = pq->head;
	*/QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
	}
	newnode->data=x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		//赋值
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		//更新tail的位置
		pq->tail = newnode;
	}
	pq->size++;

}
void QueuePop(Queue* pq)//出队，从队头删除数据，头删
{
	assert(pq);
	//头删之前需要判断链队列是否为空
	assert(pq->head!=NULL);

		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
  
	if (pq->head==NULL)//只管头删，最后再处理。
	{
		
		pq->tail=NULL;
	}
	pq->size--;
}

bool QueueEmpty(Queue* pq)//判断队列是否为空----主要size的作用
{
	assert(pq);
	return pq->size == 0;
	//return pq->head=pq->tailk=NULL;
}
int QueueSize(Queue* pq)//获得队列有效数据个数大小
{
	assert(pq);
	return pq->size;
}

QData QueueFront(Queue* pq)//获取队头数据
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QData QueueBack(Queue* pq)//获取队尾数据
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

以上是创建一个队列，接下来就是进行二叉树的层序遍历了。

void LevOlder(BTNode* root)//层序遍历--
{
	Queue q;//定义一个队列
	QueueInit(&q);//初始化队列
	//首先将根 指针插入到队列里去
	if (root)
	{
		QueuePush(&q, root);
	}
	//再出上一层带入下一层
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);//保存一下这个要出队列的指向结点的指针
		QueuePop(&q);
		printf("%d ", front->data);
		//出完后再将它的孩子指针带入进来
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

在这里插入图片描述

4.1判断是否是完全二叉树

如何判断一个二叉树树是否是完全二叉树呢？
首先我们需要了解什么是完全二叉树

【完全二叉树】
1.前n-1层都是满的二叉树。
2.最后一层从左到右是连续的。

特点：
1.非空节点是连续的。
2.空节点也是连续的。
3.至多有一个度为1的节点。

我们根据完全二叉树非空节点都是连续的这一特性，来作下面的思路：

如果对完全二叉树进行层序遍历，那么第一次出现空节点的地方就是最后一个节点的后面。 而后面就不能再出现非空节点了，后面应该都是空。
所以我们可以做出这样判断：层序遍历二叉树，如果第一次出现空之后，再出现非空节点的一定不是完全二叉树，如果后面只有空则是完全二叉树。

不过要注意的是，这里的层序遍历与原来的层序遍历不一样，原来的层序遍历，只会将根节点插入到队列中去，不会将空节点插入到队中去，而现在需要将空节点也插入到队列中去，如果出队列中的元素，出出队列的是一个空节点，那么我们就可以进行判断，是否后面还会出现非空节点呢？

//判断是否是完全二叉树，利用完全二叉树性质--非空结点是连续的，一旦出现空，后面就不应该再出现空结点。所以利用层序遍历，当第一次出现
//空时，就可以进行判断后面是否会出现非空结点。这里不同与普通层序遍历，NULL也进队列，而且出队列的结点有两种可能一种为空，一种不为空，不像层序遍历只出非空结点
{
bool BTreeCompele(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)//将根节点插入到队列中
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);//出队列中的元素
		if (front == NULL)
		{
			break;
		}
		//如果front不为空，就将它的孩子插入到队列中去，空节点也插入进去，不需要讨论
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//break 跳出来需要判断是否后面还会出现非空节点
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);//出队列中的元素
		if (front)//如果队列中出的节点不为空节点
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

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

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

相关文章

最新 MySQL 8.0.32 在Win10安装部署（详细）

最新 MySQL 8.0.32 在Win10安装部署（详细）

一、前言 MySQL官方Windows版下载地址&#xff1a;https://dev.mysql.com/downloads/installer/   本教程详细指导如何在Win10系统下安装部署最新版MySQL-8.0.32。   【MySQL系列安装部署教程】 Docker安装最新版MySQL5.7&#xff08;mysql-5.7.40&#xff09;教程&…
阅读更多...
漫画党的福利——将图片转换成漫画风格 API，附超多免费可用API 推荐（四）

漫画党的福利——将图片转换成漫画风格 API，附超多免费可用API 推荐（四）

前言 今天来和大家聊聊一件非常有趣的事情——将图片转换成漫画风格的 API&#xff01;如果你是一个漫画党&#xff0c;相信这个话题一定会让你感到兴奋。通过这个 API&#xff0c;你可以将你的照片变成漫画风格&#xff0c;让它们变得更加有趣和艺术&#xff01; 我们先来看…
阅读更多...
24《Protein Actions Principles and Modeling》-《蛋白质作用原理和建模》中文分享

24《Protein Actions Principles and Modeling》-《蛋白质作用原理和建模》中文分享

​《Protein Actions Principles and Modeling》-《蛋白质作用原理和建模》 本人能力有限&#xff0c;如果错误欢迎批评指正。 第六章&#xff1a;The principles of protein folding kinetics &#xff08;蛋白质折叠动力学的原理&#xff09; -Levinthal悖论促进蛋白质折…
阅读更多...
pyecharts实现电影数据分析可视化

pyecharts实现电影数据分析可视化

根据电影数据&#xff0c;使用pyecharts进行可视化分析。 数据介绍 import pandas as pd datapd.read_csv(./电影.csv) data.head()前5行数据如下: 需要安装的python库 pip install pandas pip install pyecharts文章目录数据介绍数据清洗数据可视化上映年份及电影数量导演…
阅读更多...
python 数据、曲线平滑处理——基于Numpy.convolve实现滑动平均滤波——详解

python 数据、曲线平滑处理——基于Numpy.convolve实现滑动平均滤波——详解

文章目录1 基于Numpy.convolve实现滑动平均滤波1.1 滑动平均概念1.2 滑动平均的数学原理1.3 语法1.4 滑动平均滤波示例2 曲线平滑处理——Savitzky-Golay 滤波器——详解3 基于Numpy.convolve实现滑动平均滤波——详解1 基于Numpy.convolve实现滑动平均滤波 1.1 滑动平均概念 …
阅读更多...
linux 配置java环境

linux 配置java环境

1、上传jdk包到/usr/local/java目录下 2、解压jdk的tar包 tar -zxvf jdk-8u291-linux-x64.tar.gz 3、添加配置&#xff08;环境变量&#xff09; 注意&#xff1a;JAVA_HOME值为实际jdk路径 打开配置文件 vi /etc/profile 最下面添加: #set java environment JAVA_HOME/usr/…
阅读更多...
基于集成学习的用户流失预测并利用shap进行特征解释

基于集成学习的用户流失预测并利用shap进行特征解释

基于集成学习的用户流失预测并利用shap进行特征解释 小P&#xff1a;小H&#xff0c;如果我只想尽可能的提高准确率&#xff0c;有什么好的办法吗&#xff1f; 小H&#xff1a;优化数据、调参侠、集成学习都可以啊 小P&#xff1a;什么是集成学习啊&#xff0c;听起来就很厉害的…
阅读更多...
SSM—【笔记】1.2 SpringMVC

SSM—【笔记】1.2 SpringMVC

SpringMVC:用于表现层开发&#xff0c;同Servlet功能等同&#xff0c;但比Servlet技术使用更加简便&#xff0c;可以用更少代码量完成开发 项目结构&#xff1a; 后端采用的是三层架构模式&#xff1a; 数据层&#xff1a;先学的JDBC技术&#xff0c;后用MyBatis框架取代 表…
阅读更多...
ThreeJS-缩放、旋转(四)

ThreeJS-缩放、旋转(四)

代码&#xff1a; <template> <div id"three_div"> </div> </template> <script> import * as THREE from "three"; import {OrbitControls } from three/examples/jsm/controls/OrbitControls export default { name: &quo…
阅读更多...
在华为做了三年软件测试被裁了，我该怎么办

在华为做了三年软件测试被裁了，我该怎么办

近年来&#xff0c;随着经济环境的变化和企业战略的调整&#xff0c;员工被裁员的情况变得越来越普遍。无论是因为企业经营困难还是因为业务调整&#xff0c;员工们都可能面临被裁员的风险。如果你也遇到了这样的情况&#xff0c;那么你应该怎么办呢&#xff1f; 首先&#xf…
阅读更多...
centos7 SystemV 开机自启动脚本配置方法 redis集群三主三从

centos7 SystemV 开机自启动脚本配置方法 redis集群三主三从

centos7 SystemV 开机自启动脚本配置方法 redis集群三主三从1、安装redis集群2、编写redis启动脚本2.1、建立启动脚本2.2、复制多份redis启动脚本给集群使用2.3、添加可执行权限3、配置开机自启动1、安装redis集群 参考: redis三主三从集群安装 2、编写redis启动脚本 2.1、建…
阅读更多...
RabbitMQ 07 发布订阅模式

RabbitMQ 07 发布订阅模式

发布订阅模式 发布订阅模式结构图&#xff1a; 比如信用卡还款日临近了&#xff0c;那么就会给手机、邮箱发送消息&#xff0c;提示需要去还款了&#xff0c;但是手机短信和邮件发送并不一定是同一个业务提供的&#xff0c;但是现在又希望能够都去执行&#xff0c;就可以用到发…
阅读更多...
HTTP协议发展历程-HTTP2【协议篇】

HTTP协议发展历程-HTTP2【协议篇】

HTTP2.0 HTTP2为了解决HTTP1.1中存在的问题。其中慢启动和TCP连接竞争是TCP本身导致的&#xff0c;在H2中依赖的还是TCP协议&#xff0c;不过思路换了一下。 HTTP/2 的思路就是一个域名只使用一个 TCP 长连接来传输数据&#xff0c;这样整个页面资源的下载过程只需要一次慢启动…
阅读更多...
【Elastic (ELK) Stack 实战教程】04、ElasticSearch 集群进阶及优化

【Elastic (ELK) Stack 实战教程】04、ElasticSearch 集群进阶及优化

目录 一、ES 集群故障转移 1.1 什么是故障转移 1.2 模拟节点故障 1.2.1 重新选举 1.2.2 主分片调整 1.2.3 副本分片调整 二、ES 文档路由原理 2.1 文档的创建流程 2.2 文档的读取流程 2.3 文档批量创建的流程 2.4 文档批量读取的流程 ​三、ES扩展集群节点 3.1 …
阅读更多...
【目标检测论文阅读笔记】Multi-scene small object detection with modified YOLOv4

【目标检测论文阅读笔记】Multi-scene small object detection with modified YOLOv4

Abstract. 小目标检测的应用存在于我们日常生活中的许多不同场景中&#xff0c;该课题也是目标检测与识别研究中最难的问题之一。因此&#xff0c;提高小目标检测精度不仅在理论上具有重要意义&#xff0c;在实践中也具有重要意义。然而&#xff0c;当前的检测相关算法在这项任…
阅读更多...
Node.js学习笔记——Express.js

Node.js学习笔记——Express.js

一、express介绍 express是一个基于Node.js平台的极简、灵活的WEB应用开发框架&#xff0c;官方网址&#xff1a;https://www.expressjs.com.cn/ 二、express使用 2.1express下载 express本身是一个npm包&#xff0c;所以可以通过npm安装。 npm init npm i express 2.2expr…
阅读更多...
Java接口

Java接口

目录 抽象类 抽象类的概述 如何使用抽象类 抽象类的使用 抽象特征 关于抽象需要注意的几个事情 接口(interface) 常量 如何实现接口 接口与接口多继承 接口的注意事项 抽象类 抽象类的概述 父类中的方法&#xff0c;被它的子类们重写&#xff0c;子类各自的实现都不…
阅读更多...
《花雕学AI》02：人工智能挺麻利，十分钟就为我写了一篇长长的故事

《花雕学AI》02：人工智能挺麻利，十分钟就为我写了一篇长长的故事

ChatGPT最近火爆全网&#xff0c;上线短短两个多月&#xff0c;活跃用户就过亿了&#xff0c;刷新了历史最火应用记录&#xff0c;网上几乎每天也都是ChatGPT各种消息。国内用户由于无法直接访问ChatGPT&#xff0c;所以大部分用户都无缘体验。不过呢&#xff0c;前段时间微软正…
阅读更多...
Vulnhub:DC-3靶机

Vulnhub:DC-3靶机

kali&#xff1a;192.168.111.111 靶机&#xff1a;192.168.111.250 信息收集 端口扫描 nmap -A -v -sV -T5 -p- --scripthttp-enum 192.168.111.250 通过nmap得知目标CMS为Joomla 3.7.0 漏洞利用 搜索发现该版本存在sql注入 利用sqlmap获取目标后台用户密码 sqlmap -u &…
阅读更多...
测试行业3年经验，面试想拿 17K，HR说你只值 8K，该如何回答或者反驳？

测试行业3年经验，面试想拿 17K，HR说你只值 8K，该如何回答或者反驳？

面试最尴尬的不是被拒绝&#xff0c;而是直接说你不值那个价格... 最近朋友在面试的时候&#xff0c;HR 突然来了句&#xff1a;你只值 7K。朋友后面和我说了这个事。我想如果是我处在这种情况下&#xff0c;自己并不能很好地回答或者反驳。不知道大家会怎么回答或者反驳&…
阅读更多...
最新文章

Copyright @ 2022~2023