【数据结构】二叉树<遍历>

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

  • <二叉树的遍历>
    • 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;
}

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

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

相关文章

最新 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&#xff01;如果你是一个漫画党&#xff0c;相信这个话题一定会让你感到兴奋。通过这个 API&#xff0c;你可以将你的照片变成漫画风格&#xff0c;让它们变得更加有趣和艺术&#xff01; 我们先来看…

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

​《Protein Actions Principles and Modeling》-《蛋白质作用原理和建模》 本人能力有限&#xff0c;如果错误欢迎批评指正。 第六章&#xff1a;The principles of protein folding kinetics &#xff08;蛋白质折叠动力学的原理&#xff09; -Levinthal悖论促进蛋白质折…

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

根据电影数据&#xff0c;使用pyecharts进行可视化分析。 数据介绍 import pandas as pd datapd.read_csv(./电影.csv) data.head()前5行数据如下: 需要安装的python库 pip install pandas pip install pyecharts文章目录数据介绍数据清洗数据可视化上映年份及电影数量导演…

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环境

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进行特征解释 小P&#xff1a;小H&#xff0c;如果我只想尽可能的提高准确率&#xff0c;有什么好的办法吗&#xff1f; 小H&#xff1a;优化数据、调参侠、集成学习都可以啊 小P&#xff1a;什么是集成学习啊&#xff0c;听起来就很厉害的…

SSM—【笔记】1.2 SpringMVC

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

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集群三主三从1、安装redis集群2、编写redis启动脚本2.1、建立启动脚本2.2、复制多份redis启动脚本给集群使用2.3、添加可执行权限3、配置开机自启动1、安装redis集群 参考: redis三主三从集群安装 2、编写redis启动脚本 2.1、建…

RabbitMQ 07 发布订阅模式

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

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

HTTP2.0 HTTP2为了解决HTTP1.1中存在的问题。其中慢启动和TCP连接竞争是TCP本身导致的&#xff0c;在H2中依赖的还是TCP协议&#xff0c;不过思路换了一下。 HTTP/2 的思路就是一个域名只使用一个 TCP 长连接来传输数据&#xff0c;这样整个页面资源的下载过程只需要一次慢启动…

【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

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

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接口

目录 抽象类 抽象类的概述 如何使用抽象类 抽象类的使用 抽象特征 关于抽象需要注意的几个事情 接口(interface) 常量 如何实现接口 接口与接口多继承 接口的注意事项 抽象类 抽象类的概述 父类中的方法&#xff0c;被它的子类们重写&#xff0c;子类各自的实现都不…

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

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

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,该如何回答或者反驳?

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