二叉树遍历的非递归算法

article/2025/10/8 17:19: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){}elseprintf("Init error!\n");return s;
}void DestroyStack(SqStack *s) {//销毁栈函数free(s->data);
}int StackEmpty(SqStack *s) {//判断是否为空栈,是返回1，否 返回0if (s->top == -1)return 1;elsereturn 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) {}elseprintf("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){}elseprintf("Init error!\n");return s;
}void DestroyStack_1(SqStack *s) {//销毁栈函数free(s->data_1);
}int StackEmpty_1(SqStack *s) {//判断是否为空栈,是返回1，否 返回0if (s->top == -1)return 1;elsereturn 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) {}elseprintf("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.测试输出

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


http://chatgpt.dhexx.cn/article/kxRjRCRt.shtml

相关文章

二叉树的中序遍历算法

二叉树的中序遍历算法

一&#xff0c;简介 二叉树的中序遍历在计算机行业有着重要的作用&#xff0c;其中一个应用就是判断一棵二叉树是否二叉排序树。 下面介绍递归和非递归两种方式实现中序遍历。 二&#xff0c;递归实现 递归实现非常简单&#xff0c;左根右依次进行即可。 void mid_scan2(n…
阅读更多...
JavaScript算法 — 二叉树遍历

JavaScript算法 — 二叉树遍历

目录 1、构造二叉树2、递归遍历3、非递归遍历3.1 先序3.2 中序3.3 后序 1、构造二叉树 树节点&#xff1a; // 二叉树节点的构造函数 function TreeNode(val, left, right) {this.val (valundefined ? 0 : val)this.left (leftundefined ? null : left)this.right (righ…
阅读更多...
二叉树遍历算法之一：前序遍历

二叉树遍历算法之一：前序遍历

递归实现前序遍历 二叉树的前序遍历是指从根节点出发&#xff0c;按照先根节点&#xff0c;再左子树&#xff0c;后右子树的方法遍历二叉树中的所有节点&#xff0c;使得每个节点都被访问一次。 当调用遍历算法的时候前序遍历的具体过程如下&#xff1a; 首先访问根节点&…
阅读更多...
二叉树遍历小结

二叉树遍历小结

前言 二叉树是相当重要的数据结构&#xff0c;目前我还只会玩玩它的遍历&#xff08;年轻不懂事没好好学&#xff0c;不然早就达到人生巅峰了&#xff09;&#xff0c;LeetCode上二叉树的简单题&#xff0c;大部分通过遍历加一点小逻辑即可解决&#xff0c;所以总结一下几种遍…
阅读更多...
二叉树遍历之层次遍历算法入门详解

二叉树遍历之层次遍历算法入门详解

一、引言 二叉树的遍历常见的方法有先序遍历、中序遍历、后序遍历和层次遍历等&#xff0c;本文给出了C语言版本的层次遍历二叉树的算法。 层次遍历的原理很简单&#xff0c;总结为一句话就是“从上到下&#xff0c;从左到右”&#xff0c;就是从树根开始逐层访问二叉树的结点&…
阅读更多...
二叉树的四种遍历算法

二叉树的四种遍历算法

二叉树作为一种重要的数据结构&#xff0c;它的很多算法的思想在很多地方都用到了&#xff0c;比如STL算法模板&#xff0c;里面的优先队列、集合等等都用到了二叉树里面的思想&#xff0c;先从二叉树的遍历开始&#xff1a; 看二叉树长什么样子&#xff1a; 我们可以看到这颗…
阅读更多...
实现二叉树各种遍历算法

实现二叉树各种遍历算法

目录 前言一、题目1.二叉树的各种遍历过程及遍历算法设计。2.实现二叉树各种遍历算法 总结 前言 提示&#xff1a;记得关注我哦&#xff01;&#xff01;&#xff01; 一、题目 1.二叉树的各种遍历过程及遍历算法设计。 &#xff08;1&#xff09; 先序遍历二叉树&#xff1…
阅读更多...
算法分析之二叉树遍历

算法分析之二叉树遍历

算法相关数据结构总结&#xff1a; 序号数据结构文章1动态规划动态规划之背包问题——01背包 动态规划之背包问题——完全背包 动态规划之打家劫舍系列问题 动态规划之股票买卖系列问题 动态规划之子序列问题 算法&#xff08;Java&#xff09;——动态规划2数组算法分析之数…
阅读更多...
二叉树遍历算法总结

二叉树遍历算法总结

A. 二叉树的遍历 1.前序遍历二叉树&#xff1a; (1)若二叉树为空&#xff0c;则为空操作&#xff0c;返回空。 (2)访问根结点。 (3)前序遍历左子树。 (4)前序遍历右子树。 a.二叉树前序遍历的递归算法&#xff1a; void PreOrderTraverse(BiTree BT)…
阅读更多...
二叉树的遍历算法

二叉树的遍历算法

遍历是对树的一种最基本的运算&#xff0c;所谓遍历二叉树&#xff0c;就是按一定的规则和顺序走遍二叉树的所有节点&#xff0c;使每一个节点都被访问一次&#xff0c;而且只被访问一次。由于二叉树是非线性结构&#xff0c;因此&#xff0c;树的遍历实质上是将二叉树的各个节…
阅读更多...
【算法】二叉树遍历算法总结：前序中序后序遍历

【算法】二叉树遍历算法总结：前序中序后序遍历

前言 二叉树遍历是非常经典的算法题&#xff0c;也是二叉树的一道基础算法题。 但是在平常的笔试面试中&#xff0c;其出现的频率其实并不是特别的高&#xff0c;我推测是这种题目相对来说比较基础&#xff0c;算是一个基础知识点。 比如剑指offer中出现的后序遍历题目&…
阅读更多...
二叉树遍历算法的应用

二叉树遍历算法的应用

目录 一、二叉树遍历算法的应用——二叉树的创建 二、二叉树遍历算法的应用——复制二叉树 三、二叉树遍历算法的应用——计算二叉树的深度 四、二叉树遍历算法的应用——计算二叉树节点总数 五、二叉树遍历算法的应用——计算二叉树叶子节点数 一、二叉树遍历算法的应用—…
阅读更多...
一文弄懂二叉树的三种遍历方式

一文弄懂二叉树的三种遍历方式

关注公众号【高性能架构探索】&#xff0c;后台回复【pdf】&#xff0c;免费获取计算机必备经典书籍 俗话说&#xff1a;学如逆水行舟,不进则退;心似平原走马,易放难收。这句话对程序员而言&#xff0c;体会更深。这行已经越来越卷了&#xff0c;时刻准备着&#xff0c;&#x…
阅读更多...
二叉树遍历算法

二叉树遍历算法

目录 先序遍历 中序遍历 后序遍历 层序遍历 938. 二叉搜索树的范围和 110. 平衡二叉树 114. 二叉树展开为链表 117. 填充每个节点的下一个右侧节点指针 II 116. 填充每个节点的下一个右侧节点指针 1&#xff0c;三种遍历都是先把二叉树的最左结点循环入栈(DFS迭代)&am…
阅读更多...
二叉树的四种遍历算法（结构体数组）

二叉树的四种遍历算法（结构体数组）

一、二叉树的定义 以字符串的形式定义一棵二叉树的先序序列&#xff0c;若字符是‘#’&#xff0c;表示该二叉树是空树&#xff0c;否则该字符是相应结点的数据元素。 例&#xff1a;ABDG##HI####CE#J##F## 对应的二叉树&#xff1a; 思路讲解&#xff1a; 想要遍历二叉树&am…
阅读更多...
二叉树的四种遍历方式

二叉树的四种遍历方式

概要 树本身是一种简单化的图 &#xff1b; DFS对应前中后序遍历&#xff0c;BFS对应层序遍历 二叉树结构 struct treenode {int val;treenode *left;treenode *right;treenode() : val(0), left(nullptr), right(nullptr) {}treenode(int x) : val(x), left(nullptr), right(n…
阅读更多...
针对Linux学习，值得阅读的五本书籍，不看可能错失机会

针对Linux学习，值得阅读的五本书籍，不看可能错失机会

今天为了总结一些可以帮助各位在学习过程中提供帮助的一些书籍。 一.鸟叔的私房菜&#xff1a; 本书是知名度颇高的Linux入门书《鸟哥的Linux私房菜基础学习篇》的新版,而详细地介绍了Linux操作系统。全书分为五部分;第一部分部分着重说明计算机的基础知识、Linux的学习方法&a…
阅读更多...
从零开始学习Linux（一）关闭虚拟机系统

从零开始学习Linux（一）关闭虚拟机系统

关闭系统&#xff0c;需要输入如下命令 poweroff然而&#xff0c;你只能得到如下反馈 -bash: poweroff:command not found此项错误是因为poweroff命令是一个系统管理命令。执行此项命令需要高级使用者特权。 因此&#xff0c;为了关闭系统&#xff0c;我们首先需要切换到root…
阅读更多...
个人随笔/小白应该如何学习Linux，我的一些心得分享.

个人随笔/小白应该如何学习Linux，我的一些心得分享.

大家好&#xff0c;今天给大家分享一下0基础的人如何入门Linux&#xff0c;此文来源&#xff1a;我在上班的路上看到一篇文章&#xff0c;也是写的0基础的人如何学习Linux的文章。当时我在想&#xff0c;我写博文一年多&#xff0c;都是相关Linux及Python等技术的文章&#xff…
阅读更多...
Linux学习路线

Linux学习路线

&#xfeff;&#xfeff; 关于 Linux Linux 因其开源&#xff0c;免费&#xff0c;可裁剪&#xff0c;被应用到很多领域&#xff0c;尤其是嵌入式设备上。 Android 系统内核也是基于 Linux 的。 另外还有各种服务器和工作站也是用的 Linux。 什么是嵌入式设备&#xff1f;…
阅读更多...
推荐文章

Copyright @ 2022~2023