数据结构学习笔记——二叉树的遍历和链式存储代码实现二叉树

目录

  • 一、二叉树的遍历
    • （一）二叉树的先序遍历（DLR）
    • （二）二叉树的中序遍历（LDR）
    • （三）二叉树的后序遍历（LRD）
    • （四）二叉树的层次遍历
  • 二、二叉树的实现代码（链式存储）
    • （一）二叉树的定义
    • （二）二叉树的建立
    • （三）广义表输出二叉树
    • （四）二叉树的先、中、后遍历
    • （五）二叉树的层次遍历
    • （六）二叉树的深度
    • （七）二叉树的叶子结点数
    • （八）二叉树的结点总数

一、二叉树的遍历

二叉树的遍历是按某种规定的顺序来对访问树中的所有结点，且每个结点仅被访问一次，由于二叉树由根结点（D）、左子树（L）和右子树（R）组成，以下是二叉树的先、中、后以及层次遍历。
在这里插入图片描述

二叉树的先、中、后序遍历都可以通过递归算法实现，递归结束的条件是T==NULL，即当二叉树为空时，遍历结束。

（一）二叉树的先序遍历（DLR）

二叉树的先序遍历中，首先是根结点，遍历完根结点的左子树，然后再遍历完根结点的右子树，依次下去至所有结点都遍历到，例如上图二叉树，其先序遍历就是abefcgh。

（二）二叉树的中序遍历（LDR）

二叉树的中序遍历中，首先是遍历完根结点的左子树，然后是根结点，最后遍历完根结点的右子树，依次下去至所有结点都遍历到，通过中序遍历可以得到一个递增的有序序列。

例如，一个二叉树中，根据中序遍历可知，中序遍历序列的最后一个结点一定是从根结点开始沿着右子树走到最底的结点，若它为叶子结点，则先序遍历序列和中序遍历序列的最后一个结点都为该结点【如上图二叉树】；若不为叶子结点，它还有一个左子结点，则该左子结点是前序遍历序列的最后一个结点。

在这里插入图片描述
它的先序遍历序列为：ABDECF，中序遍历序列为：DBEAFC，由于中序遍历序列的最后一个结点一定是从根结点开始沿着右子树走到最底的结点，所以中序遍历序列的最后一个结点为C，且结点C并不是叶子结点，它还有一个左子结点F，所以该结点F为先序遍历序列的最后一个结点。

（三）二叉树的后序遍历（LRD）

二叉树的后序遍历中，首先是遍历完根结点的左子树，然后遍历完根结点的右子树，最后是根结点，依次下去至所有结点都遍历到，也就是从二叉树的底层往上层依次遍历。

  • 在二叉树的前序遍历、中序遍历和后序遍历序列中，所有叶子结点的先后顺序是相同的。
  • 若一棵二叉树为空树或只有根结点，则其先序遍历序列和后序遍历序列相同；若二叉树为单右支二叉树或孤立结点，则其先序遍历序列和中序遍历序列相同。
  • 若一棵二叉树为空树或任一结点至多只有左子树，则其中序遍历序列和后序遍历序列相同。
  • 若一棵非空的二叉树只有一个叶子结点，或二叉树的高度等于结点个数，则其先序遍历序列和后序遍历序列相反。

（四）二叉树的层次遍历

层次遍历中，层次优先，当对一层的结点都遍历完后，遍历下一层，按照次序对每个结点的左、右孩子进行遍历。

  • 层次遍历二叉树中可以通过链式队列实现，首先二叉树的根结点入队，然后进入循环，循环条件为队列是否为空，若不为空，则当前队头结点出队，此时该结点被访问到，并将该结点的左、右孩子结点插入到队列的队尾。
  • 若一棵二叉树为空树或任一结点至多只有右子树，则其中序遍历序列与层次遍历序列相同。

二、二叉树的实现代码（链式存储）

（一）二叉树的定义

通过链式存储结构实现代码如下，其中包含数据域和两个指针：

#incldue<stdio.h>
/*二叉树的定义*/
typedef struct BNode {
	int data;		//数据域
	struct BNode *lchild,*rchild;		//左孩子、右孩子指针
} *BTree;

（二）二叉树的建立

创建一个二叉树，按二叉树的顺序（二叉树带空指针的顺序，空指针也算进去），即根结点、左子树、右子树的顺序依次输入结点的值【使用的顺序是先序序列】，若其中有空结点，用0表示，其中使用到递归的方法建立左右孩子结点，实现代码如下：

#include <malloc.h>
/*二叉树的建立*/
BTree CreateTree() {
	BTree T;
	char ch;
	scanf("%c",&ch);
	getchar();	//getchar()用于接收每次输入字符结点后的回车符，从而以便输入下一个字符结点
	if(ch=='0')	//当为0时，将结点置空
		T=NULL;
	else {
		T=(BTree)malloc(sizeof(BTree));	//分配一个新的结点
		T->data=ch;
		printf("请输入%c结点的左孩子结点：",T->data);
		T->lchild=CreateTree();		//通过递归建立左孩子结点
		printf("请输入%c结点的右孩子结点：",T->data);
		T->rchild=CreateTree();		//通过递归建立右孩子结点
	}
	return T;
}

（三）广义表输出二叉树

通过广义表来显示建立的二叉树，一个非空的二叉树T，当对于左孩子结点或右孩子结点时，此时输出一个左括号“(”，递归处理左子树，输出一个“,”用于隔开结点，然后递归处理右子树，输出一个右括号“)”，从而完成一个根结点以下的两个左/右结点处理。

/*广义表输出二叉树*/
void ShowTree(BTree T) {
	if(T!=NULL) {
		//当二叉树不为空时
		printf("%c",T->data);	//输入出该结点的数据域
		if(T->lchild!=NULL) {		//若该结点的左子树不为空
			printf("(");	//输出一个左括号
			ShowTree(T->lchild);	//通过递归继续输出结点的左子树结点下的各结点
			if(T->rchild!=NULL) {	//若该结点右子树不为空
				printf(",");	//输出一个逗号
				ShowTree(T->rchild);	//通过递归继续输出结点的右子树结点下的各结点
			}
			printf(")");	//输出一个右括号
		} else {	//若左子树为空，右子树不为空
			if(T->rchild!=NULL) {
				printf("(");	//输出一个左括号
				ShowTree(T->lchild);	//通过递归继续输出结点的左子树结点下的各结点
				if(T->rchild!=NULL) {		//若该结点的右子树不为空	
					printf(",");	//输出一个逗号
					ShowTree(T->rchild);	//通过递归继续输出结点的右子树结点下的各结点
				}
				printf(")");	//输出一个右括号
			}
		}
	}
}

例如，一个二叉树如下图，通过链式存储结构实现建立二叉树并输出。
在这里插入图片描述
代码如下：

#include <stdio.h>
#include <malloc.h>
/*1、二叉树的定义*/
typedef struct BNode {
	int data;		//数据域
	struct BNode *lchild,*rchild;		//左孩子、右孩子指针
} *BTree;

/*2、二叉树的建立*/
BTree CreateTree() {
	BTree T;
	char ch;
	scanf("%c",&ch);
	getchar();	//getchar()用于接收每次输入字符结点后的回车符，从而以便输入下一个字符结点
	if(ch=='0')	//当为0时，将结点置空
		T=NULL;
	else {
		T=(BTree)malloc(sizeof(BTree));	//分配一个新的结点
		T->data=ch;
		printf("请输入%c结点的左孩子结点：",T->data);
		T->lchild=CreateTree();		//通过递归建立左孩子结点
		printf("请输入%c结点的右孩子结点：",T->data);
		T->rchild=CreateTree();		//通过递归建立右孩子结点
	}
	return T;
}

/*3、广义表输出二叉树*/
void ShowTree(BTree T) {
	if(T!=NULL) {
		//当二叉树不为空时
		printf("%c",T->data);	//输入出该结点的数据域
		if(T->lchild!=NULL) {		//若该结点的左子树不为空
			printf("(");	//输出一个左括号
			ShowTree(T->lchild);	//通过递归继续输出结点的左子树结点下的各结点
			if(T->rchild!=NULL) {	//若该结点右子树不为空
				printf(",");	//输出一个逗号
				ShowTree(T->rchild);	//通过递归继续输出结点的右子树结点下的各结点
			}
			printf(")");	//输出一个右括号
		} else {	//若左子树为空，右子树不为空
			if(T->rchild!=NULL) {
				printf("(");	//输出一个左括号
				ShowTree(T->lchild);	//通过递归继续输出结点的左子树结点下的各结点
				if(T->rchild!=NULL) {		//若该结点的右子树不为空	
					printf(",");	//输出一个逗号
					ShowTree(T->rchild);	//通过递归继续输出结点的右子树结点下的各结点
				}
				printf(")");	//输出一个右括号
			}
		}
	}
}

/*主函数*/
int main() {
	BTree T;
	T=NULL;
	printf("请输入二叉树的根结点：");
	T=CreateTree();		//建立二叉树
	printf("建立的二叉树如下：\n");
	ShowTree(T);		//通过广义表显示二叉树
}

依次输入各个结点的左右孩子结点，若结点不存在则输入0，例如树中结点d的左孩子结点不存在，结点f、g、h、i、j的左右孩子都不存在。
运行结果如下，结果通过广义表的定义显示：
在这里插入图片描述

（四）二叉树的先、中、后遍历

例如对下图这个二叉树，进行先、中、后遍历：
在这里插入图片描述
1、先序遍历二叉树：

/*先序遍历二叉树*/
bool ProTree(BTree T) {
	if(T==NULL)
		return false;			//递归结束
	else {
		printf("%c ",T->data);	//输出当前结点的数据域
		ProTree(T->lchild);		//递归继续遍历该结点的左子树
		ProTree(T->rchild);		//递归继续遍历该结点的右子树
		return true;
	}
}

运行结果如下：
在这里插入图片描述
2、中序遍历二叉树：

/*中序遍历二叉树*/
bool InTree(BTree T) {
	if(T==NULL)
		return false;			//递归结束
	else {
		InTree(T->lchild);		//递归继续遍历该结点的左子树
		printf("%c ",T->data);	//输出当前结点的数据域
		InTree(T->rchild);		//递归继续遍历该结点的右子树
		return true;
	}
}

运行结果如下：
在这里插入图片描述
3、后序遍历二叉树：

/*后序遍历二叉树*/
bool PostTree(BTree T) {
	if(T==NULL)
		return false;				//递归结束
	else {
		PostTree(T->lchild);		//递归继续遍历该结点的左子树
		PostTree(T->rchild);		//递归继续遍历该结点的右子树
		printf("%c ",T->data);		//输出当前结点的数据域
		return true;
	}
}

运行结果如下：
在这里插入图片描述

（五）二叉树的层次遍历

在这里插入图片描述
层次遍历二叉树：

/*7、层次遍历二叉树*/
void LevelTree(BTree T) {
	BTree q[MAXSIZE];		//MAXSIZE的值可自行定义
	int front=0,rear=0;		//初始化队头指针和队尾指针为0
	if(T!=NULL) {			//当二叉树不为空
		q[rear++]=T;					//根结点入队
		while(front!=rear) {			//当队列不为空时
			BTree head=q[front++];
			printf("%c ",head->data);	//访问队头结点的数据域
			if(head->lchild) 			//若当前结点的左孩子存在，将队头结点的左孩子入队
				q[rear++]=head->lchild;
			if(head->rchild) 			//若当前结点的右孩子存在，将队头结点的右孩子入队
				q[rear++]=head->rchild;
		}
	}
}

也是上图中的二叉树，进行层次遍历，运行结果如下：
在这里插入图片描述

（六）二叉树的深度

二叉树的深度也是求最大深度，也是采用递归思想，分别递归计算左、右子树的深度，然后从左、右子树的深度中返回最大值，即为二叉树的深度，实现代码如下：

/*二叉树的深度*/
int DepthTree(BTree T) {
	int ldepth=0,rdepth=0;		//分别代表左、右子树的深度，初始值都为0
	if(T==NULL)
		return 0;
	else {
		ldepth=DepthTree(T->lchild);	//递归继续统计结点的左子树深度
		rdepth=DepthTree(T->rchild);	//递归继续统计结点的右子树深度
		if(ldepth>rdepth)		//求最大深度
			return ldepth+1;
		else
			return rdepth+1;
	}
}

对于上图中的二叉树，运行结果如下：
在这里插入图片描述

（七）二叉树的叶子结点数

求一个二叉树的叶子结点数，也是递归方法实现，我们知道若一个结点的左、右孩子都为空，则这说明这是一个叶子结点，通过递归，最后return返回叶子结点数，实现代码如下：

/*二叉树的叶子结点数*/
int LeavesNum(BTree T) {
	if(T!=NULL) {	//当根结点不为空
		if(T->lchild==NULL&&T->rchild==NULL)	//若一个结点的左、右孩子都为空，即这是一个叶子结点 
			return 1;
	}
	return (LeavesNum(T->lchild)+LeavesNum(T->rchild));
}

对于上图中的二叉树，运行结果如下：
在这里插入图片描述

（八）二叉树的结点总数

也是递归，当二叉树不为空时，二叉树的结点总数等于左子树结点个数+右子树结点个数，然后加1（二叉树的根结点），实现代码如下：

/*求二叉树的结点总数*/
int SumLeaves(BTree T) {
	if(T!=NULL)
		return (SumLeaves(T->lchild)+SumLeaves(T->rchild)+1);
}

对于上图中的二叉树，运行结果如下：
在这里插入图片描述

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

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

相关文章

【古月居《ros入门21讲》学习笔记】07_创建工作空间和功能包

【古月居《ros入门21讲》学习笔记】07_创建工作空间和功能包

目录 说明&#xff1a; 1. 工作空间(workspace) 结构&#xff1a; 2. 创建工作空间和功能包 创建工作空间 编译工作空间 创建功能包 设置环境变量 3. 注意 同一个工作空间下&#xff0c;不能存在同名的功能包&#xff1b; 不同工作空间下&#xff0c;可以存在同名的功…
阅读更多...
学习程序员必知必会的基础算法(收藏)

学习程序员必知必会的基础算法(收藏)

近年来学习python的程序员愈来愈多&#xff0c;有的同学选择了python培训机构&#xff0c;也有的人觉得自己天赋好选择了自学不管大家怎么去学习&#xff0c;在学习python基础的过程中&#xff0c;肯定离不开的就是基础算法&#xff0c;今天就为大家介绍几大学习中的基础算法。…
阅读更多...
ffmpeg开发 环境配置

ffmpeg开发 环境配置

ffmpeg开发简图 1 下载ffmpeg开发包 https://ffmpeg.org/download.html 包含三个版本&#xff1a;Static、Shared以及Dev Static --- 包含3个应用程序&#xff1a;ffmpeg.exe , ffplay.exe , ffprobe.exe&#xff0c;体积都很大&#xff0c;相关的DLL已经被编译到exe里面去…
阅读更多...
TDA4VM EVM开发板调试笔记

TDA4VM EVM开发板调试笔记

文章目录 1. 前言2. 官网资料导读3. 安装 Linux SDK4. 制作SD 启动卡5. 验证启动1. 前言 TDA4作为一般经典的车规级SOC芯片，基于它的低阶智驾方案目前成为各家智驾方案公司的量产首选，这也使得基于TDA4的开发需求陡增，开发和使用TDA4既要熟悉Linux驱应用开发，还要熟悉传统…
阅读更多...
自建CA实战之 《0x02 Nginx 配置 https双向认证》

自建CA实战之 《0x02 Nginx 配置 https双向认证》

自建CA实战之 《0x02 Nginx 配置 https双向认证》 上一章节我们已经实现了Nginx上配置https单向认证&#xff0c;主要场景为客户端验证服务端的身份&#xff0c;但是服务端不验证客户端的身份。 本章节我们将实现Nginx上配置https双向认证&#xff0c;主要场景为客户端验证服…
阅读更多...
基于Java SSM框架+Vue实现汉服文化平台网站项目【项目源码+论文说明】计算机毕业设计

基于Java SSM框架+Vue实现汉服文化平台网站项目【项目源码+论文说明】计算机毕业设计

基于java的SSM框架Vue实现汉服文化平台系统演示 摘要 本论文主要论述了如何使用JAVA语言开发一个汉服文化平台网站 &#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;采用B/S架构&#xff0c;面向对象编程思想进行项目开发。在引言中&#xff0c;作者将…
阅读更多...
在gazebo里搭建一个livox mid360 + 惯导仿真平台测试 FAST-LIO2

在gazebo里搭建一个livox mid360 + 惯导仿真平台测试 FAST-LIO2

在gazebo里搭建一个livox mid360 惯导仿真平台测试 FAST-LIO2 前言立方体平台加入 livox mid360 激光雷达加入IMU模块调整底盘大小 并设计调用接口测试 Fast-Lio2 前言 livox mid360 在官网一直没有货&#xff0c;在gazebo里可以仿真该雷达形式的点云。 但是其只发布雷达的数…
阅读更多...
【电源专题】DC/DC电源FB分压电阻设计注意事项

【电源专题】DC/DC电源FB分压电阻设计注意事项

在DC/DC电源中我们不可避免的会遇到FB分压电阻的取值，PCB设计等问题。如下所示随意打开一份同步降压稳压器规格书TPS56320X，规格书中的简化电路原理图就已经存在VFB管脚上的两个分压电阻。 很多工程师朋友们会误认为分压电阻只是简单的将输出电压缩小到参考电压，通过此电压来…
阅读更多...
电子学会C/C++编程等级考试2023年03月（三级）真题解析

电子学会C/C++编程等级考试2023年03月（三级）真题解析

C/C++等级考试（1~8级）全部真题・点这里 第1题：和数(2023.3) 给定一个正整数序列，判断其中有多少个数，等于数列中其他两个数的和。 比如，对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。 时间限制：10000 内存限制：65536输入 共两行，第一行是数列中…
阅读更多...
【接口自动化】selenium库也有大用场（获取cookie）

【接口自动化】selenium库也有大用场（获取cookie）

相信有些童鞋在做接口、或者说接口自动化测试的过程中会遇到这样的场景&#xff1a;测试的接口&#xff0c;必须是需要登录后才能发起请求成功的。 那么怎么解决呢&#xff1f; 本着团队协作的精神&#xff0c;我们就去让开发同学开个后门&#xff0c;给你个“万能”值&#x…
阅读更多...
AntDB“超融合+流式实时数仓”——颠覆50年未变的数据库内核

AntDB“超融合+流式实时数仓”——颠覆50年未变的数据库内核

流式处理引擎&#xff0c;颠覆50年未变的数据库内核 流式处理的概念 2001年9月11日&#xff0c;美国世贸大楼被袭击&#xff0c;美国国防部第一次将“主动预警”纳入国防的宏观战略规划。而IBM作为当时全球最大的IT公司&#xff0c;承担了大量基础支撑软件研发的任务。其中200…
阅读更多...
R语言单因素方差分析+差异显著字母法标注+逐行详细解释

R语言单因素方差分析+差异显著字母法标注+逐行详细解释

R语言单因素方差分析 代码如下 df <- read.csv("data.csv",header TRUE,row.names 1) library(reshape2) df <- melt(df,idc()) names(df) <- c(trt, val) df aov1 <- aov(val~trt,datadf) summary(aov1)library(agricolae) data <- LSD.test(aov…
阅读更多...
双指针算法总结

双指针算法总结

双指针算法分为两类&#xff1a;第一类指向一个序列&#xff08;更多的情况&#xff09;&#xff0c;第二类指向两个序列。 基本的代码框架是&#xff1a; for (i 0, j 0; i < n; i) {while (j < i && check(i, j)) j;// 每道题目的具体逻辑 } 核心思想&…
阅读更多...
探索使用Quarkus和MicroProfile 构建Kubernetes原生微服务的秘诀！

探索使用Quarkus和MicroProfile 构建Kubernetes原生微服务的秘诀！

Kubernetes Native Microservices with Quarkus and MicroProfile 是一个基于Kubernetes原生微服务的开发框架&#xff0c;它结合了Quarkus和MicroProfile的优点&#xff0c;提供了一个高效、可扩展、易于管理的微服务解决方案。 Quarkus是一个针对Java虚拟机&#xff08;JVM&…
阅读更多...
代码demo-内部订单批量投料

代码demo-内部订单批量投料

为了简化用户操作&#xff0c;开发内部订单批量投料功能 用户可以批量上传&#xff0c;或者选择对应的物料&#xff0c;输入库位和内部订单号后进行过账操作 对用户选择的内部订单做校验&#xff0c;内部订单是否正确 内部订单的公司是否和工厂对应的公司一致等等 下面展示…
阅读更多...
[NOIP2016 普及组] 回文日期

[NOIP2016 普及组] 回文日期

枚举好题&#xff0c;直接枚举答案 看看在不在范围内就行了 注意二月份 92200229是合法的~ 82200228也是合法的&#xff01; #include<bits/stdc.h> using namespace std;map<int,int>mp;int main() {mp[1] mp[3] mp[5] mp[7] mp[8] mp[10] mp[12] 31;mp[…
阅读更多...
MMdetection3.0 问题

MMdetection3.0 问题

MMdetection3.0 问题 希望各位路过的大佬指教一下&#xff1a; 问题&#xff1a; 1、NWPU-VHR-10有标注的数据一共650张&#xff0c;我将其分为了455张训练集&#xff0c;195张验证集。 2、然后使用MMdetection3.0框架中的Faster-rcnn网络进行训练&#xff0c;设置训练参数b…
阅读更多...
微信小程序体验版提交审核,提示接口未配置在app.json文件且无权限

微信小程序体验版提交审核,提示接口未配置在app.json文件且无权限

在火狐浏览器 打开微信公众平台 发布小程序 弹窗一闪而过 是因为 放开这里就可以了
阅读更多...
selenium元素定位方法之xpath

selenium元素定位方法之xpath

什么是xpath&#xff1f; XPath是XML的路径语言&#xff0c;通俗一点讲就是通过元素的路径来查找到这个标签元素XPath使用路径表达式在XML文档中进行导航 普通语法 注意&#xff01; 1.xpath中的值用引号引起来时&#xff0c;在代码中要注意区分&#xff0c;内单外双&#xf…
阅读更多...
Intellij IDEA 的安装和使用以及配置

Intellij IDEA 的安装和使用以及配置

IDE有很多种&#xff0c;常见的Eclipse、MyEclipse、Intellij IDEA、JBuilder、NetBeans等。但是这些IDE中目前比较火的是Intellij IDEA&#xff08;以下简称IDEA&#xff09;&#xff0c;被众多Java程序员视为最好用的Java集成开发环境&#xff0c;今天的主题就是IDEA为开发工…
阅读更多...
最新文章

Copyright @ 2022~2023