程序员经验分享-hwhale

二叉树遍历的非递归算法

2023-11-10

非递归的算法主要采用的是循环出栈入栈来实现对二叉树的遍历，下面是过程分析

以下列二叉树为例：（图片来自懒猫老师《数据结构》课程相关内容）

1.前序遍历

前序遍历的顺序为：根结点->左子树->右子树

基本过程：

（1）访问根结点，将根结点入栈

（2）循环逐个访问左子树，执行（1）中步骤；当访问到没有左子树的结点时，跳出循环

（3）栈不为空，根结点出栈，访问右子树

这里以A的左子树为例进行栈的变化过程说明：

可以总结成，没有左子树->出栈+右子树入栈；没有右子树->出栈

代码实现：

void PreOrder(BiNode *bt) { //树的前序遍历
	SqStack s;
	s = InitStack();
	BiNode *p = bt;
	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
		while (p != NULL) {
			visit(p->data);//访问根结点
			Push(&s, p); //将指针p的节点压入栈中
			p = p->Lchild; //遍历左子树
		}
		if (StackEmpty(&s) != 1) { //栈不为空
			p = Pop(&s); //根结点出栈,相当于回退
			p = p->rchild; //遍历右子树
		}
	}
	DestroyStack(&s);
}

2.中序遍历

中序遍历的顺序为：左子树->根结点>右子树

基本过程：

（1）将根结点入栈

（2）循环逐个访问左子树，执行（1）中步骤；当访问到没有左子树的结点时，跳出循环

（3）栈不为空，根结点出栈，访问根结点，再访问右子树

其实就是将访问根结点的位置换了

代码实现： 

void MidOrder(BiNode *bt) { //树的中序遍历
	SqStack s;
	s = InitStack();
	BiNode *p = bt;
	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
		while (p != NULL) {
			Push(&s, p); //将指针p的节点压入栈中
			p = p->Lchild; //遍历左子树
		}
		if (StackEmpty(&s) != 1) { //栈不为空
			p = Pop(&s); //根结点出栈,相当于回退
			visit(p->data);//访问根结点
			p = p->rchild; //遍历右子树
		}
	}
	DestroyStack(&s);
}

3.后序遍历

 前两种遍历的栈数据类型都是BiNode *，但后序遍历的栈的数据类型要进行重新定义，因为后序遍历的顺序是左子树->右子树>根结点，结点要进入两次栈，出两次栈，为什么会有两次呢？

（1）第一次出栈：只遍历完左子树，该结点不能出栈，需要第二次入栈；找到右子树并遍历

（2）第二次出栈：遍历完左右子树，该结点出栈，并访问

需要注意的是，第二次出栈并访问之后，需要将p指针置空，这样才能在下一次循环的时候，重新从栈中取到一个元素（或者理解成二叉树中的回退操作）

这里设置一个flag标志来区分两次出入栈，并进行不同的操作

栈元素类型定义如下：

typedef struct element {
	BiNode *ptr;
	int flag;
} element;

代码实现：

（因为后序遍历和前两种数据类型不一样，这里定义了两套栈函数分别来用，用_1下标区分）

void PostOrder(BiNode *bt) { //树的后序遍历
	SqStack s;
	s = InitStack_1();
	BiNode *p = bt;
	element elem;
	while (p != NULL || StackEmpty_1(&s) != 1) { //当p为空，栈也为空时退出循环
		if (p != NULL) {//第一次入栈，访问左子树
			elem.ptr = p;
			elem.flag = 1; //标记flag为1，表示即将第一次入栈
			Push_1(&s, elem); //将指针p的结点第一次压入栈中
			p = p->Lchild;
		} else {
			elem = Pop_1(&s); //出栈
			p = elem.ptr; //p指向当前要处理的结点
			if (elem.flag == 1) {
				//flag==1时，说明只访问过左子树，还要访问右子树
				elem.flag = 2;
				Push_1(&s, elem); //结点第二次压入栈中
				p = p->rchild;
			} else {
				//flag==2时，左右子树都已经访问过了
				visit(p->data);
				p = NULL; //访问后，p赋为空，确保下次循环时继续出栈（相当于回退）
			}
		}
	}
	DestroyStack_1(&s);
}

4. 完整代码

分为三个文件包，一个是存放栈的操作函数，一个是存放二叉树的非递归遍历函数，一个是对二叉树的非递归遍历功能进行的测试，第三个文件调用前两个头文件就可以测试完整功能

（1）数组堆栈_二叉树非递归.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char Datatype;

typedef struct BiNode {
	Datatype data;//数据内容
	struct BiNode  *Lchild;//指向左孩子结点
	struct BiNode  *rchild;//指向右孩子结点
} BiNode;

typedef BiNode *Elemtype;
typedef struct element {
	BiNode *ptr;
	int flag;
} element;

typedef element Elemtype_1;
typedef struct {
	Elemtype *data;//用于前序和中序遍历
	Elemtype_1 *data_1;//用于后序遍历
	int top;//栈顶指针，这里用int类型表示指针的下标
	int stacksize;
} SqStack;
Elemtype Pop(SqStack *s);

SqStack InitStack() {//空栈构造函数
	SqStack s;
	s.data = (Elemtype *)malloc(STACK_INIT_SIZE * sizeof(Elemtype));
	s.top = -1; //表示栈空
	s.stacksize = STACK_INIT_SIZE;
	if (s.data != NULL)
	{}
	else
		printf("Init error!\n");
	return s;
}

void DestroyStack(SqStack *s) {//销毁栈函数
	free(s->data);
}

int StackEmpty(SqStack *s) {//判断是否为空栈,是返回1，否 返回0
	if (s->top == -1)
		return 1;
	else
		return 0;
}

void Push(SqStack *s, Elemtype e) {//添加元素入栈
	if (s->top >= s->stacksize) {
		s->data = (Elemtype *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype));
		s->stacksize += STACKINCREMENT;
		if (s->data != NULL) {}
		else
			printf("Push error!\n");
	} else {
		s->top++;
		s->data[s->top] = e;
	}
}

Elemtype Pop(SqStack *s) {
	if (StackEmpty(s) != 1 && s->top >= 0) {
		Elemtype e = s->data[s->top];
		s->top--;
		return e;
	}
	printf("Pop error!\n");
}

SqStack InitStack_1() {//空栈构造函数
	SqStack s;
	s.data_1 = (Elemtype_1 *)malloc(STACK_INIT_SIZE * sizeof(Elemtype_1));
	s.top = -1; //表示栈空
	s.stacksize = STACK_INIT_SIZE;
	if (s.data != NULL)
	{}
	else
		printf("Init error!\n");
	return s;
}

void DestroyStack_1(SqStack *s) {//销毁栈函数
	free(s->data_1);
}

int StackEmpty_1(SqStack *s) {//判断是否为空栈,是返回1，否 返回0
	if (s->top == -1)
		return 1;
	else
		return 0;
}

void Push_1(SqStack *s, Elemtype_1 e) {//添加元素入栈
	if (s->top >= s->stacksize) {
		s->data_1 = (Elemtype_1 *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype_1));
		s->stacksize += STACKINCREMENT;
		if (s->data_1 != NULL) {}
		else
			printf("Push error!\n");
	} else {
		s->top++;
		s->data_1[s->top] = e;
	}
}

Elemtype_1 Pop_1(SqStack *s) {
	if (StackEmpty(s) != 1 && s->top >= 0) {
		Elemtype_1 e = s->data_1[s->top];
		s->top--;
		return e;
	}
	printf("Pop error!\n");
}

 （2）二叉树遍历（非递归）.h

#include "数组堆栈_二叉树非递归.h"

BiNode *Creat(char *str, int *i, int len) { //树的创建
	struct BiNode *bt = NULL;
	char ch = str[(*i)++];
	if (ch == '#' || *i >= len) {
		bt = NULL;
	} else {
		bt = (struct BiNode *)malloc(sizeof(BiNode));
		if (bt != NULL) {
			bt->data = ch;
			bt->Lchild = Creat(str, i, len); //这里的递归要赋值，这样才能建立不同域中的连接关系
			bt->rchild = Creat(str, i, len);
		}
	}
	return bt;//返回的一直是根结点
}

void visit(Datatype e) {
	printf("%c ", e);
}

void PreOrder(BiNode *bt) { //树的前序遍历
	SqStack s;
	s = InitStack();
	BiNode *p = bt;
	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
		while (p != NULL) {
			visit(p->data);//访问根结点
			Push(&s, p); //将指针p的节点压入栈中
			p = p->Lchild; //遍历左子树
		}
		if (StackEmpty(&s) != 1) { //栈不为空
			p = Pop(&s); //根结点出栈,相当于回退
			p = p->rchild; //遍历右子树
		}
	}
	DestroyStack(&s);
}

void MidOrder(BiNode *bt) { //树的中序遍历
	SqStack s;
	s = InitStack();
	BiNode *p = bt;
	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
		while (p != NULL) {
			Push(&s, p); //将指针p的节点压入栈中
			p = p->Lchild; //遍历左子树
		}
		if (StackEmpty(&s) != 1) { //栈不为空
			p = Pop(&s); //根结点出栈,相当于回退
			visit(p->data);//访问根结点
			p = p->rchild; //遍历右子树
		}
	}
	DestroyStack(&s);
}

void PostOrder(BiNode *bt) { //树的后序遍历
	SqStack s;
	s = InitStack_1();
	BiNode *p = bt;
	element elem;
	while (p != NULL || StackEmpty_1(&s) != 1) { //当p为空，栈也为空时退出循环
		if (p != NULL) {//第一次入栈，访问左子树
			elem.ptr = p;
			elem.flag = 1; //标记flag为1，表示即将第一次入栈
			Push_1(&s, elem); //将指针p的结点第一次压入栈中
			p = p->Lchild;
		} else {
			elem = Pop_1(&s); //出栈
			p = elem.ptr; //p指向当前要处理的结点
			if (elem.flag == 1) {
				//flag==1时，说明只访问过左子树，还要访问右子树
				elem.flag = 2;
				Push_1(&s, elem); //结点第二次压入栈中
				p = p->rchild;
			} else {
				//flag==2时，左右子树都已经访问过了
				visit(p->data);
				p = NULL; //访问后，p赋为空，确保下次循环时继续出栈（相当于回退）
			}
		}
	}
	DestroyStack_1(&s);
}

 （3）二叉树遍历（非递归）.c

#include "二叉树遍历（非递归）.h"

main() {
	printf("测试二叉树遍历（非递归）算法\n");
	printf("建立一个二叉树-->");
	BiNode *bt;
	int i = 0, len;
	char str[50];
	printf("输入一个字符串用于建立二叉树:");
	scanf("%s", str);
	len = strlen(str);
	bt = Creat(str, &i, len);
	printf("测试遍历操作:\n");
	printf("测试树的前序遍历:");
	PreOrder(bt);
	printf("\n");
	printf("测试树的中序遍历:");
	MidOrder(bt);
	printf("\n");
	printf("测试树的后序遍历:");
	PostOrder(bt);
	printf("\n");
}

5.测试输出

 初学小白，有错误的话欢迎指正喔！~

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构初步

算法

数据结构

c语言

二叉树遍历的非递归算法 的相关文章

随机推荐

  • EasyAVFilter代码示例之将视频点播文件转码成HLS（m3u8+ts）视频点播格式

    以下是一套完整的视频点播功能开发源码 就简简单单几行代码 就可以完成原来ffmpeg很复杂的视频点播转码调用流程 而且还可以集成在自己的应用程序中调用 例如java php cgo c nodejs 不需要再单独一个ffmpeg的进程来调用

  • 随机数产生函数总是产生相同随机数的原因

    1 没有设置随机数种子 下面的程序直接调用rand 函数 结果产生的20个随机数虽然各不相同 但是每次运行得到的20个随机数与上次运行的结果都是一样的 就是因为没有设置随机数种子 虽然程序运行过程中可以产生不同随机数 但是下次运行产生的随机

  • protobuf-gen-lua 编译dll文件

    vs 创建dll空项目 引入protobuf gen lua工程里的pb c文件 修改原程序 1 ifndef WIN32 2 include

  • 机器学习——聚类——密度聚类法——OPTICS

    目录 理论部分 1 1 提出背景 1 2 OPTICS算法 1 2 1 基本概念 1 2 2 算法流程 1 2 3 优点 1 2 4 缺点 1 3 其它算法 代码部分 2 1 自行实现 2 2 sklearn实现 理论部分 1 1 提出背景

  • 33.输入捕获原理与配置

    输入捕获原理与配置 参考资料 STM32Fx开发板 STM32Fx开发指南 HAL库版本 第x章 输入捕获实验 STM32Fxx官方资料 STM32Fxx中文参考手册 第x章 通用定时器 笔记基于正点原子官方视频 视频连接https www

  • Face++人脸识别之情绪识别、视线估计

    1 定义 什么是情绪识别 是指分析识别图片中人脸的各类情绪并返回该人脸在各类不同情绪上的置信度分数 某种情绪的置信度分数越高 则可认为此种情绪与人脸真实情绪越接近 目前 Face 能够识别愤怒 厌恶 恐惧 高兴 平静 伤心 惊喜等七类最重要

  • windows10系统下nextcloud服务的webdav网盘挂载方法

    目录 前言 一 下载挂载服务修复批处理文件 保存到本地并运行 二 复制网盘地址 并挂载网盘 三 webdav网盘挂载成功 前言 许多朋友都有使用过网盘 像比较大的百度网盘 天翼云盘等 但是也有不少小微企业希望搭建企业内部的私有网盘 这就需要

  • 为什么说 Apache APISIX 是最好的 API 网关？

    今天 我们可以通过手机和各种 APP 完成各种各样的事情 比如社交 网购等 这些行为的背后 API 起到了关键的作用 作为 API 的使用者 我们并不关心 API 的稳定 安全和高效 但是通过 API 提供数据服务的企业则需要选择一个合适的

  • 思科模拟器实现Telnet和SSH远程管理

    思科模拟器实现Telnet和SSH远程管理 Telnet实现远程管理 明文传输 安全性不高 SSH实现远程访问 密文传输 前提 1 要保证设备之间能够进 2 设置enable密码 Telnet实现远程管理 明文传输 安全性不高 R0的配置

  • git生成ssh密钥详细步骤

    首先右键点击电脑桌面 点击 git bash here 打开git命令窗口 如果git用户名和邮箱等已经完成配置 则跳过此步骤 直接操作第3条 假如没有配置 继续如下操作 1 在命令窗口配置用户 输入命令 git config global

  • python如何实现监听微信应用新消息通知中心弹窗提醒

    可以使用第三方库如 itchat 来实现对微信应用新消息通知中心弹窗提醒的监听 首先需要安装 itchat 可以使用 pip 安装 pip install itchat 然后可以使用 itchat 提供的相关接口来登录微信 并设置消息处理回

  • OpenStack自动化安装部署实战（附OpenStack实验环境）

    packstack是openstack自动化安装工具 packstack程序中写入了openstack的安装过程 可以自动化对服务器进行openstack软件包的安装 packstack可以在answer file设置安装参数 在安装时 p

  • 在个人电脑上部署ChatGLM2-6B中文对话大模型

    简介 ChatGLM2 6B 是清华大学开源的一款支持中英双语的对话语言模型 经过了 1 4T 中英标识符的预训练与人类偏好对齐训练 具有62 亿参数的 ChatGLM2 6B 已经能生成相当符合人类偏好的回答 结合模型量化技术 用户可以在

  • 5、特征选择(filter)：方差分析(ANOVA)

    方差分析ANOVA特征筛选 一 方差分析 Analysis of Variance 简称ANOVA 基本原理 二 连续变量和离散变量的方差分析 2 1 提出假设 2 2 采集数据 2 3 设计统计量 2 4 事件发生概率计算与统计推断 三

  • win hook codeproject

    http www codeproject com Articles 32131 Dynamically Add Edit Environment Variables of Remo

  • 【蓝桥杯Python】2023.2.5-成绩统计

    题目描述 小蓝给学生们组织了一场考试 卷面总分为 100 分 每个学生的得分都是一个 0 到 100 的整数 如果得分至少是 60 分 则称为及格 如果得分至少为 85 分 则称为优秀 请计算及格率和优秀率 用百分数表示 百分号前的部分四舍

  • 吴恩达ChatGPT《LangChain for LLM Application Development》笔记

    基于 LangChain 的 LLM 应用开发 1 介绍 现在 使用 Prompt 可以快速开发一个应用程序 但是一个应用程序可能需要多次写Prompt 并对 LLM 的输出结果进行解析 因此 需要编写很多胶水代码 Harrison Cha

  • 【Python数据挖掘课程】六.Numpy、Pandas和Matplotlib包基础知识

    前面几篇文章采用的案例的方法进行介绍的 这篇文章主要介绍Python常用的扩展包 同时结合数据挖掘相关知识介绍该包具体的用法 主要介绍Numpy Pandas和Matplotlib三个包 目录 一 Python常用扩展包 二 Numpy科学

  • RabbitMQ中重试机制的坑

    当我们消息消费失败的时候 可以进行重试 虽然SpringAMQP集成了retry机制 但是发现使用过程有点坑 等会细说 重试机制使用场景 1 如果是业务代码 比如空指针之类的异常那重试机制其实没什么用 2 如果是调用第三方系统 网络抖动之类

  • 二叉树遍历的非递归算法

    非递归的算法主要采用的是循环出栈入栈来实现对二叉树的遍历 下面是过程分析 以下列二叉树为例 图片来自懒猫老师 数据结构 课程相关内容 1 前序遍历 前序遍历的顺序为 根结点 gt 左子树 gt 右子树 基本过程 1 访问根结点 将根结点入栈

热门标签