二叉树中序遍历(非递归)算法实现–C语言「建议收藏」

二叉树中序遍历(非递归)算法实现–C语言「建议收藏」今天继续二叉树的学习。昨天写了一遍二叉树的先序遍历(非递归)算法,今天写一下二叉树的二叉树的中序遍历(非递归)算法。中序遍历的非递归算法有两种,但是个人觉得只要掌握一种就可以了,只要自己的逻辑清晰,会哪一种又有什么关系呢~首先给出今天的二叉树的示例图:代码如下://InOrderBiTreeTraverse.cpp:Definestheentrypointforthec…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

今天继续二叉树的学习。
昨天写了一遍二叉树的先序遍历(非递归)算法,今天写一下二叉树的二叉树的中序遍历(非递归)算法。中序遍历的非递归算法有两种,但是个人觉得只要掌握一种就可以了,只要自己的逻辑清晰,会哪一种又有什么关系呢~

首先给出今天的二叉树的示例图:
在这里插入图片描述

代码如下:


#include "stdafx.h"
#include <stdlib.h>
#define STACKINITSIZE 20//栈初始空间大小
#define INCREASEMENT 10//栈空间大小的增量
typedef struct BiTNode
{ 

char data;//二叉树节点数据
BiTNode *lchild,*rchild;//指向二叉树左子树和右子树的指针
}BiTNode,*BiTree;//定义二叉树节点结构
typedef struct SqStack
{ 

BiTNode *base;//栈底指针
BiTNode *top;//栈顶指针
int stacksize;//顺序栈空间大小
}SqStack;//定义顺序栈结构
//建立一个空栈,建立成功,返回1,失败,返回0
int InitStack(SqStack &S)
{ 

S.base = (BiTNode*)malloc(STACKINITSIZE * sizeof(BiTNode));//20为栈的大小,可以更改
if(!S.base)
return 0;
S.top = S.base;
S.stacksize = STACKINITSIZE;
return 1;
}
//进栈操作
int Push(SqStack &S,BiTNode e)
{ 

if(S.top - S.base >= S.stacksize)
{ 

S.base = (BiTNode*)realloc(S.base,(STACKINITSIZE + INCREASEMENT) * sizeof(BiTNode));
if(!S.base)
return 0;
S.stacksize = 30;
}
*S.top = e;
S.top ++;
return 1;
}
//出栈操作,若栈为空,则返回0;栈不为空,则返回1
int Pop(SqStack &S,BiTNode &e)
{ 

if(S.base == S.top)
return 0;
S.top --;
e = *S.top;
return 1;
}
//判断栈是否为空,若栈为空,则返回true,栈不为空,则返回false
bool StackEmpty(SqStack S)
{ 

if(S.base == S.top)
return true;
else
return false;
}
//建立二叉树
void CreateBiTree(BiTree &T)
{ 

char ch;
scanf("%c",&ch);
if(ch == '#')
T = NULL;
else
{ 

T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
//中序遍历二叉树
int InOrderTraverse(BiTree T)
{ 

if(!T)
return 0;
SqStack S;
int n = InitStack(S);//建立空栈
if(!n)
return 0;
BiTree p = T;
BiTNode e;//二叉树节点,用于存放从栈中取出的节点
while(p || !StackEmpty(S))
{ 

if(p)
{ 

Push(S,*p);
p = p->lchild;
}
else
{ 

Pop(S,e);
printf("%c ",e.data);
p = e.rchild;
}
}
printf("\n");
return 1;
}
int main(int argc, char* argv[])
{ 

BiTree T = NULL;
printf("请输入二叉树-按照先序序列建立二叉树\n");
CreateBiTree(T);
printf("中序遍历二叉树结果为:\n");
InOrderTraverse(T);
return 0;
}

测试结果:
在这里插入图片描述
代码相对于先序遍历来说,几乎改动不大,只在遍历函数里有改动。但是,为了多练习,还是应该再敲一遍,说不定会有新的启发。对于C语言,自己可能还是刚入门阶段,但是不去多练习,又怎么会有提高呢!就像做数学题一样,自己觉得看着都会,却又不去动手去做,那在真正考试的时候,很可能的结果就是大部分题目都做不出来。究其原因当然是平时动手太少,觉得自己都会而懒于去做。
写代码也是一样,之前看的时候觉得自己道理都懂,但是昨天自己心血来潮,想建立一个空栈竟然都成问题,当时内心感慨颇多,学了这么多年计算机,竟然到现在把最简单的东西都忘得差不多了。所以决定给自己定下小目标,每天至少更新一篇博客:博客上要附上自己今天敲的代码。无论自己是否从事这类的工作,都要坚持下去!虽然不能说自己有多么的喜欢这些内容,但是至少在敲代码的时候自己的内心是平静的!

关于二叉树的一些原理什么的,在更新完相应的内容之后会做一个汇总,形成知识框架,不止为了记录在博客上,也是为了更好的印在脑海里!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193943.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • arpspoof攻击_捕获arp请求

    arpspoof攻击_捕获arp请求把PC和iPhone链接到同一个路由器上攻击者和受害者需要在同一局域网内1.查看发起攻击者的网卡和IP地址:$ifconfigeno1:flags=4163mtu1500inet192.168.2.105netmask255.255.255.0broadcast192.168.2.255inet6fe80::a56b:455a:b152:634cprefixlen64…

  • SSRF漏洞总结

    SSRF漏洞总结0x00什么是SSRF?服务端请求伪造(SSRF)是指攻击者能够从易受攻击的web应用程序发送精心设计的请求,对其他网站进行攻击(利用一个可发起网络请求的服务当做跳板来攻击其他服务)例如:我在http://localhost:8888/pentest/ssrf/index.php有这样一个存在SSRF漏洞的index.php。即我得到了一个使用curl发起网络请求然后返回客户端并且我可以…

  • netty bytebuffer_netty源码剖析与实战

    netty bytebuffer_netty源码剖析与实战一、背景简介ByteBuf,顾名思义,就是字节缓冲区,是Netty中非常重要的一个组件。熟悉jdkNIO的同学应该知道ByteBuffer,正是因为jdk原生ByteBuffer使用比较复杂,某些场景下性能不是太好,netty开发团队重新设计了ByteBuf用以替代原生ByteBuffer。二、ByteBuf和ByteBuffer对比下面用图示来展示ByteBuf和ByteBuffer工作原理:①、ByteBufferByteBuffer依靠flip()来切换模式,在读模式下..

  • fiddler和charles哪个好用_charles手机设置代理后上不了网

    fiddler和charles哪个好用_charles手机设置代理后上不了网前言Charles是收费软件,可以免费试用30天。试用期过后,未付费的用户仍然可以继续使用,但是每次使用时间不能超过30分钟,并且启动时将会有10秒种的延时。此时,我们只需网上找一个注册码即可解

  • SQL聚合函数功能和用法解析

    SQL聚合函数功能和用法解析第一部分:介绍SUM和AVG  我们知道数据库通常包含大量数据,要从海量的数据中找到我们需要的某条记录无异于大海捞针,不过通过SQL语言我们可以找到很多方法从数据库中提取我们要查找的特定数据,就是通过这些方法我们才能找到“列举出七八两个月中购买了西伯利亚羊毛的所有顾客的姓名”这类问题的答案。  很多时候,我们还希望能够通过对数据进行分析,总结出规律和趋势或生成高水平的报表。例如,对于采购经理来说,…

  • 长江商学院营销学李洋教授分析大数据与精准营销

    长江商学院营销学李洋教授分析大数据与精准营销  精准营销是大数据应用领域的重要课题之一,大数据时代的精准营销可以让企业以最小的营销成本获得最大的收益。那么我们如何利用企业大数据做精准营销呢? …

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号