当前位置： 首页 > article >正文

二叉树遍历（前序、中序、后续）

article 2024/10/22 9:16:39

目录

  • 什么是二叉树
  • 二叉树遍历
  • 以递归创建树的角度看前、中、后序遍历
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 栈来实现前、中、后序遍历
    • 栈的实现
    • 栈操作进行前序、中序遍历
    • 代码实现中序遍历和先序遍历
    • 栈操作进行后序遍历

什么是二叉树

树：树的根节点没有前驱，除根节点以外，其他所有节点有且只有一个前驱。

二叉树：是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。

在这里插入图片描述
以此图为例，F为根节点，C为F的左子节点，E为F的右子节点。

二叉树遍历

二叉树遍历分为：前序、中序、后序

前序遍历方式：根节点 -> 左节点 -> 右节点
前序遍历上图：FCADBEHGM

中序遍历方式：左节点 -> 根节点 -> 右节点
中序遍历上图：ACBDFHEMG
(ps：在根节点切换到右节点时，需要认为此时解析的是以右节点为根的二叉树，由最左的节点开始遍历)

后序遍历方式：左节点 -> 右节点 -> 根节点
后序遍历上图：ABDCHMGEF

以递归创建树的角度看前、中、后序遍历

这一部分主要以递归的方法创建树，并让读者直观了解前中后序遍历之间的关系。
代码逻辑：

1. 输入一个以#代表空节点，的前序树结构
2. 通过递归，生成二叉树
3. 并返回前序、后序、中序的遍历结果

前序遍历

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

typedef struct TreeNode
{
	char data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;

/*
#名称# createTree
#功能# 根据前序遍历的字符串创建一个树 
#参数# T：树的头指针的指针 
	   str：前序遍历字符串 
	   index：记录字符串访问到的地址 
#返回值# 无 
*/ 
void createTree(TreeNode** T,char* str,int* index)
{
	if(str[*index]=='#')
	{
		(*index)++;
		*T = NULL;
	}
	else
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = str[*index];
		printf("%c",str[*index]);
		(*index)++;
		createTree(&((*T)->lchild),str,index);
		createTree(&((*T)->rchild),str,index);
	}
	
}

/*
#名称# preOrder
#功能# 对二叉树进行前序遍历读值 
#参数# T：树的头指针
#返回值# 无 
*/ 
void preOrder(TreeNode* T) {
	if(T == NULL)	
	{
		return;
	}
	else
	{
		printf("%c ",T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}


int main(void)
{
	char* str[1024];
	TreeNode* T;
	int i=0;
	
	scanf("%s",str);
	createTree(&T,str,&i);
	preOrder(T);
}

中序遍历

/*
#名称# inOrder
#功能# 对二叉树进行中序遍历读值 
#参数# T：树的头指针
#返回值# 无 
*/ 
void inOrder(TreeNode* T) {
	if(T == NULL)	
	{
		return;
	}
	else
	{
		inOrder(T->lchild);
		printf("%c ",T->data);
		inOrder(T->rchild);
	}
}

后序遍历

/*
#名称# postOrder
#功能# 对二叉树进行后序遍历读值 
#参数# T：树的头指针
#返回值# 无 
*/ 
void postOrder(TreeNode* T) {
	if(T == NULL)	
	{
		return;
	}
	else
	{
		postOrder(T->lchild);
		postOrder(T->rchild);
		printf("%c ",T->data);
	}
}

栈来实现前、中、后序遍历

栈的实现

栈：先进后出，使用链表实现，由栈顶入，栈顶出

下述代码逻辑：S为栈顶

typedef struct StackNode {
    TreeNode* data;
    struct StackNode* next;
}StackNode;

/*
#名称# initStack
#功能# 初始化链表 
#参数# 无
#返回值# 链表头指针
*/
StackNode* initStack() {
    StackNode* S = (StackNode*)malloc(sizeof(StackNode));
    S->data = NULL;
    S->next = NULL;
    return S;
}

/*
#名称# isEmpty
#功能# 判断该链表是否为空 （栈顶后面没有值）
#参数# S：链表的指针
#返回值# 1空，0非空
*/
int isEmpty(StackNode* S){
	if(S->next == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

/*
#名称# pop
#功能# 出栈操作 （将栈顶后面的第一个成员出栈）
#参数# 无
#返回值# 链表头指针
*/
StackNode* pop(StackNode* S){
	if(isEmpty(S))
	{
		return NULL;
	}
	else
	{
		StackNode* node = S->next;
		s->next = node->next;
		return node;
	}
}

/*
#名称# push
#功能# 入栈操作 （将数据加入到栈顶后面的第一个成员）
#参数# 无
#返回值# 链表头指针
*/
StackNode* push(TreeNode* data,StackNode* S){
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->data = data;
	node->next = S->next;
	S->next = node;
}

栈操作进行前序、中序遍历

原理：

1、入栈根节点
2、循环，判断当前节点是否为空
3、不空，将节点入栈并把节点推向左子节点
4、空，出栈，并推将节点推至出栈节点的右子节点
5、回到循环

以下图为例，红色为进站顺序，蓝色为出栈顺序，黄色为当前节点

1、先将根节点和一条链路上的左节点按顺序入栈，当前节点为A的左子节点
在这里插入图片描述

2、A的左子节点为当前节点，当前节点为空，则出栈一个节点，然后将当前节点推到出栈节点的右子节点
在这里插入图片描述
3、当前节点为空，则出栈一个节点，然后将当前节点推到出栈节点的右子节点
在这里插入图片描述
4、当前节点有值入栈，推到左节点，有值也入栈
在这里插入图片描述
按上述原理完整的入栈和出栈顺序为：
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
可以得到入栈顺序为：FCADBEHGM
出栈顺序为：ACBDFHEMG

可以看出入栈顺序即为先序遍历，出栈顺序为中序遍历

代码实现中序遍历和先序遍历

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

typedef struct TreeNode
{
	char data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;

typedef struct StackNode {
    TreeNode* data;
    struct StackNode* next;
}StackNode;

/*
#名称# initStack
#功能# 初始化链表 
#参数# 无
#返回值# 链表头指针
*/
StackNode* initStack() {
    StackNode* S = (StackNode*)malloc(sizeof(StackNode));
    S->data = NULL;
    S->next = NULL;
    return S;
}

/*
#名称# isEmpty
#功能# 判断该链表是否为空 （栈顶后面没有值）
#参数# S：链表的指针
#返回值# 1空，0非空
*/
int isEmpty(StackNode* S){
	if(S->next == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

/*
#名称# pop
#功能# 出栈操作 （将栈顶后面的第一个成员出栈）
#参数# 无
#返回值# 链表头指针
*/
StackNode* pop(StackNode* S){
	if(isEmpty(S))
	{
		return NULL;
	}
	else
	{
		StackNode* node = S->next;
		S->next = node->next;
		return node;
	}
}

/*
#名称# push
#功能# 入栈操作 （将数据加入到栈顶后面的第一个成员）
#参数# 无
#返回值# 链表头指针
*/
StackNode* push(TreeNode* data,StackNode* S){
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->data = data;
	node->next = S->next;
	S->next = node;
}

/*
#名称# createTree
#功能# 根据前序遍历的字符串创建一个树 
#参数# T：树的头指针的指针 
	   str：前序遍历字符串 
	   index：记录字符串访问到的地址 
#返回值# 无 
*/ 
void createTree(TreeNode** T,char* str,int* index)
{
	if(str[*index]=='#')
	{
		(*index)++;
		*T = NULL;
	}
	else
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = str[*index];
		(*index)++;
		createTree(&((*T)->lchild),str,index);
		createTree(&((*T)->rchild),str,index);
	}
	
}

/*
#名称# preOrder
#功能# 对二叉树使用栈进行前序读值 
#参数# T：树的头指针
#返回值# 无 
*/ 
void preOrder(TreeNode* T) {
	TreeNode* node;
	node = T;
	StackNode* S = initStack();
	while(node||!isEmpty(S))
	{
		if(node)
		{
			push(node,S);
			printf("%c ",node->data);
			node = node->lchild;
		}
		else
		{
			node = pop(S)->data;
			node = node->rchild;
			
		}
	}
}

/*
#名称# inOrder
#功能# 对二叉树使用栈进行中序读值 
#参数# T：树的头指针
#返回值# 无 
*/ 
void inOrder(TreeNode* T) {
	TreeNode* node;
	node = T;
	StackNode* S = initStack();
	while(node||!isEmpty(S))
	{
		if(node)
		{
			push(node,S);
			node = node->lchild;
		}
		else
		{
			node = pop(S)->data;
			printf("%c ",node->data);
			node = node->rchild;
			
		}
	}
}

int main(void)
{
	char* str[1024];
	TreeNode* T;
	int i=0;
	
	scanf("%s",str);
	createTree(&T,str,&i);
	preOrder(T);
	printf("\n");
	inOrder(T); 
}

栈操作进行后序遍历

1、从根节点开始，寻找最左边的节点，并依次入栈，遇到空节点出栈
2、出栈前，判断栈顶元素是否有右子树，如果有先将右子树入栈
（还要判断右子树是否已经被访问过，不能进行重复访问）
3、若右子树未被访问过，重复12步骤遍历子树

将二叉树最左的链路全部进栈后，每出栈一个左子节点，均会判断是否
拥有右子节点并入栈，且判断是否是树，是树重复上述操作。
（注：当前节点node变化只会由左子节点跳到右子节点，不会返回根节
点（无论前、中、后序遍历均如此），后序遍历中使用top转存中间节点
，并不直接对node赋值，node只可能为左右节点，不会是根节点，规避
了node=根节点带来的死循环）

故树的节点代码需要增加一个标志位

typedef struct TreeNode
{
	char data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
    int flag;
}TreeNode;

加入获取栈顶节点的代码

/*
#名称# getTop
#功能# 获取栈顶节点操作
#参数# S栈顶指针 
#返回值# 栈顶节点 
*/
StackNode* getTop(StackNode* S){
	if(isEmpty(S))
	{
		return NULL;
	}
	else
	{
		return S->next;
	}
}

后序遍历函数

/*
#名称# postOrder
#功能# 对二叉树进行后序遍历读值 
#参数# T：树的头指针
#返回值# 无 
*/ 
void postOrder(TreeNode* T) {
	TreeNode* node;
	node = T;
	StackNode* S = initStack();
	while(node||!isEmpty(S))
	{
		if(node)
		{
			push(node,S);
			node = node->lchild;
		}
		else 
		{
			/*可能会在if（node）中重复进栈，所以定义一个top，跳过根节点，跨到右子节点*/
            TreeNode* top  = getTop(S) -> data;
            if (top -> rchild && top -> rchild -> flag == 0) 
			{
                top = top -> rchild;
                node = top;
            }
            else 
			{
                top = pop(S) -> data;
                printf("%c ", top -> data);
                top -> flag = 1;
            }
        }
	}
}

http://www.kler.cn/news/359947.html

相关文章：

  • OpenCV高级图形用户界面(14)交互式地选择一个或多个感兴趣区域函数selectROIs()的使用
  • 【大模型实战篇】大模型分词算法Unigram及代码示例
  • 【进阶OpenCV】 （11）--DNN板块--实现风格迁移
  • 电动汽车嵌入式软件开发过程中的难题有哪些？
  • JavaGuide(10)
  • commonjs和esmodule的导入导出细节
  • opencv实战项目（三十二）：opencv汽车360全景影像制作
  • 【嵌入式软件-STM32】STM32外设
  • 常用数据库获取表，视图，列，索引信息
  • AndroidStudio移动开发：使用Service播放音乐【步骤】
  • 【分布式微服务云原生】《Redis RedLock 算法全解析：应对时钟漂移与网络分区挑战》
  • Python异常检测-3Sigma
  • exchange_proxy exchange 安全代理
  • SqlDbx连接oracle(可用)
  • PDF.js的使用及其跨域问题解决
  • 力扣244题详解：最短单词距离 II 的多种解法与模拟面试
  • 携手并进，智驭教育！和鲸科技与智谱 AI 签署“101 数智领航计划”战略合作协议
  • Apache Doris简介
  • Items View 项目视图
  • 基于Spring Boot、Vue和MyBatis的前后端分离座位管理系统：增删改查功能入门指南