(编程)二叉树前序、中序、后序遍历的非递归写法
前序和中序遍历的非递归写法都比较好实现,后序遍历稍微复杂一些.
数据结构定义:
struct Node{
char c;
pNode lchild, rchild;
Node(char c, pNode lchild = nullptr, pNode rchild = nullptr) :
c(c), lchild(lchild), rchild(rchild) {}
};
二叉树形态:
A
/ \
B C
/ / \
D E F G
/ \
H I
1
2
3
4
5
6
7
前序遍历:
先根遍历,拿到一个节点的指针,先判断是否为空,不为空就先访问该结点,然后直接进栈,接着遍历左子树;为空则要从栈中弹出一个节点来,这个时候弹出的结点就是其父亲,然后访问其父亲的右子树,直到当前节点为空且栈为空时,算法结束.
前提:若后期有需求购买阿里云任何产品的朋友,可以提前领取优惠劵。后期可为大家减少成本:点击领取2000元阿里云优惠劵
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; }
}
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; }
}
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); }
}
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) {}
};
pNode build()
{
/*
A / \ B C / \ / \
D E F G
/ \ H I
*/
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; }
}
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; }
}
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); }
}
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
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
(编程)10个Python练手小程序
【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码: for i in range(1,5): for j in range(1,5): for k in range(1,5): if( i != k ) and (i != j) and (j != k): print (i,j,k) 阿里云代金券2000元免费领取地址:https://promotion.aliyun.com/ntms/yunparter/invite.html新老阿里云账户均可领取!可用于购买阿里云服务器ECS、云数据库RDS、虚拟主机、安骑士、DDoS高防IP等100多云计算产品。 代金券自领取之日起,有效期是30天,请及时使用,过30天后还可以重新领取。 【程序2】 题目:企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高 于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可可提 成...
- 下一篇
【编程】如何提高代码可读性、可维护性
高质量代码的三大要素: 可读性、可维护性和可变更性 做好代码规范、提高代码质量,能显著增强代码的可读性、可维护性和可变更性。努力提高代码的读写可维护性,是做好代码规范的必要非充分条件。代码规范和架构设计是软件的灵魂所在,代码质量偏低,就像是人失去了三魂七魄中的一魄,就会丧失活力,影响正常运行,增加软件交付后维护成本,出现推迟完成、超出预算、特性缺失等现象。 任何语言都需要强调编码风格的一致性。只要是团队开发,每个人都以相同的方式编写代码就是至关重要的。这样大家才能方便地互相看懂和维护对方的代码。 实际上,每家公司都会有一份(或多份)代码规范,因此提高代码的读写可维护性的关键在于是否能落实公司的相关文档,公司的技术总监、项目经理或相关代码审查机关是否具有应有的执行力。如果不能落实,那么即便代码规范画得再美,具体的代码也会丑到崩溃。 阿里云代金券2000元免费领取地址:https://promotion.aliyun.com/ntms/yunparter/invite.html新老阿里云账户均可领取!可用于购买阿里云服务器ECS、云数据库RDS、虚拟主机、安骑士、DDoS高防IP等100多...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS7设置SWAP分区,小内存服务器的救世主
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题