二叉树前序、中序、后序遍历的非递归写法

简介: 二叉树前序、中序、后序遍历的非递归写法

前序和中序遍历的非递归写法都比较好实现,后序遍历稍微复杂一些.

数据结构定义:

struct Node{

char c;
pNode lchild, rchild;
Node(char c, pNode lchild = nullptr, pNode rchild = nullptr) :

c(c), lchild(lchild), rchild(rchild) {}
AI 代码解读

};

申请阿里云服务时,可以使用2000元阿里云代金券,阿里云官网领取网址:https://dashi.aliyun.com/site/yun/youhui

二叉树形态:

A
/ \
B C
/ / \
D E F G

/ \
H I

前序遍历:

先根遍历,拿到一个节点的指针,先判断是否为空,不为空就先访问该结点,然后直接进栈,接着遍历左子树;为空则要从栈中弹出一个节点来,这个时候弹出的结点就是其父亲,然后访问其父亲的右子树,直到当前节点为空且栈为空时,算法结束.

阿里云服务器1核2G低至82元/年,阿里云官活动网址:https://dashi.aliyun.com/site/yun/aliyun 可以用20代金券,即102-20=82。

void preVisitStack(pNode root)
{

stack st;
pNode p = root;
while (p || !st.empty()) {

if (p) {
    visit(p);
    st.push(p);
    p = p->lchild;
} else {
    p = st.top();
    st.pop();
    p = p->rchild;
}
AI 代码解读

}
cout << endl;
}

中序遍历:

和前序遍历一样,只不过在访问节点的时候顺序不一样,访问节点的时机是从栈中弹出元素时访问,如果从栈中弹出元素,就意味着当前节点父亲的左子树已经遍历完成,这时候访问父亲,就是中序遍历.

void midVisitStack(pNode root)
{

stack st;
pNode p = root;
while (p || !st.empty()) {

if (p) {
    st.push(p);
    p = p->lchild;
} else {
    p = st.top();
    visit(p);
    st.pop();
    p = p->rchild;
}
AI 代码解读

}
cout << endl;
}

后序遍历:

后续遍历就不一样了,首先肯定是先访问左子树,把父亲节点保存于栈中,问题是当元素从栈中弹出的时候,我们无法判断这个时候是该访问其右子树还是访问父亲节点,于是我们就需要一个标记,当访问左子树时我们把父亲节点的标记设为1,表示下一步如果弹出该节点,就访问其右子树;弹出一个节点时,我们要判断该节点的标记,如果是1,则访问其右子树,并把该节点的标记设置成2,表示下一步就访问该节点,然后把该节点继续入栈,如果是2,那么表示访问该节点,访问并且丢弃该节点.

为了不继续添加新的数据结构,我是用了STL中的pair来封装节点与标记.

void backVisitStack(pNode root)
{

stack > st;
pNode p = root;
while (p || !st.empty()) {

if (p) {
    st.push(make_pair(p, 1));
    p = p->lchild;
} else {
    auto now = st.top();
    st.pop();
    if (now.second == 1) {
        st.push(make_pair(now.first, 2));
        p = now.first->rchild;
    } else
        visit(now.first);
}
AI 代码解读

}
cout << endl;
}

完整测试代码:

include
using namespace std;

typedef struct Node *pNode;

struct Node{

char c;
pNode lchild, rchild;
Node(char c, pNode lchild = nullptr, pNode rchild = nullptr) :

c(c), lchild(lchild), rchild(rchild) {}
AI 代码解读

};

pNode build()
{

/*

     A
   /  \
 B     C
/ \   / \
AI 代码解读

D E F G

    / \
   H   I
AI 代码解读

*/
pNode root = new Node('A');
root->lchild = new Node('B');
root->rchild = new Node('C');
root->lchild->lchild = new Node('D');
root->lchild->rchild = new Node('E');
root->rchild->lchild = new Node('F');
root->rchild->rchild = new Node('G');
root->rchild->lchild->lchild = new Node('H');
root->rchild->lchild->rchild = new Node('I');
return root;
}

void visit(pNode x)
{

cout << x->c << " ";
}

void preVisitStack(pNode root)
{

stack st;
pNode p = root;
while (p || !st.empty()) {

if (p) {
    visit(p);
    st.push(p);
    p = p->lchild;
} else {
    p = st.top();
    st.pop();
    p = p->rchild;
}
AI 代码解读

}
cout << endl;
}

void midVisitStack(pNode root)
{

stack st;
pNode p = root;
while (p || !st.empty()) {

if (p) {
    st.push(p);
    p = p->lchild;
} else {
    p = st.top();
    visit(p);
    st.pop();
    p = p->rchild;
}
AI 代码解读

}
cout << endl;
}

void backVisitStack(pNode root)
{

stack > st;
pNode p = root;
while (p || !st.empty()) {

if (p) {
    st.push(make_pair(p, 1));
    p = p->lchild;
} else {
    auto now = st.top();
    st.pop();
    if (now.second == 1) {
        st.push(make_pair(now.first, 2));
        p = now.first->rchild;
    } else
        visit(now.first);
}
AI 代码解读

}
cout << endl;
}

int main()
{

pNode root = build();
preVisitStack(root);
midVisitStack(root);
backVisitStack(root);
}

测试结果:

依次为前序、中序、后序遍历的结果.

A B D E C F H I G
D B E A H F I C G
D E B H I F G C A

目录
打赏
0
0
0
0
119
分享
相关文章
java202303java学习笔记第三十四天try...catch疑问1
java202303java学习笔记第三十四天try...catch疑问1
108 0
kde
|
10天前
|
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
6446 14
|
7天前
typora免费版,激活方法,Typora使用教程
Typora是一款简洁高效的Markdown编辑器,支持即时渲染。本教程涵盖安装方法、文件操作、视图控制、格式排版、字体样式及Markdown语法,助你快速上手使用Typora进行高效写作。
1656 1
Dify MCP 保姆级教程来了!
大语言模型,例如 DeepSeek,如果不能联网、不能操作外部工具,只能是聊天机器人。除了聊天没什么可做的。
1604 25
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
988 4
【保姆级图文详解】大模型、Spring AI编程调用大模型
【保姆级图文详解】大模型、Spring AI编程调用大模型
658 9
【保姆级图文详解】大模型、Spring AI编程调用大模型
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
本文详细介绍了Maven的项目管理工具特性、安装步骤和配置方法。主要内容包括: Maven概述:解释Maven作为基于POM的构建工具,具备依赖管理、构建生命周期和仓库管理等功能。 安装步骤: 从官网下载最新版本 解压到指定目录 创建本地仓库文件夹 关键配置: 修改settings.xml文件 配置阿里云和清华大学镜像仓库以加速依赖下载 设置本地仓库路径 附加说明:包含详细的配置示例和截图指导,适用于各种操作系统环境。 本文提供了完整的Maven安装和配置
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问