二叉树中序遍历(非递归)算法实现–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)


相关推荐

  • AvalonDock 2.0 的简单运用

    AvalonDock 2.0 的简单运用最近在研究AvalonDock的一些使用,碰到了一些问题。现在拿出来跟大家分享分享。网上找了一大把AvalonDock1.3版本的资料,弄出Demo后发现属性面板(DockableContent)设置成浮动后不能停靠其它的面板。最后只得试试AvalonDock2.0版本的,还好2.0版本没让我们失望。首先需要库文件:Xceed.Wpf.AvalonDock…

  • java可重入锁与不可重入锁

    java可重入锁与不可重入锁所谓重入锁,指的是以线程为单位,当一个线程获取对象锁之后,这个线程可以再次获取本对象上的锁,而其他的线程是不可以的。synchronized和  ReentrantLock都是可重入锁。可重入锁的意义在于防止死锁。实现原理是通过为每个锁关联一个请求计数器和一个占有它的线程。当计数为0时,认为锁是未被占有的;线程请求一个未被占有的锁时,JVM将记录锁的占有者,并且将请求计数器置为1…

  • yum卸载重装[通俗易懂]

    yum卸载重装[通俗易懂]莫名原因(之前操作不小心删除了某相关文件)导致虚拟机的yum使用不了,在重新安装之前需要卸载原来的相关数据1.删除/usr/share目录下的yum-cli、yum-pluginrm-rfyum-cli/yum-plugins/2.清理与yum相关的文件rpm-qa|grepyumrpm-eyum-3.4.3-161.el7.centos.noarch…

  • 电脑加速 2010年最新方法

    电脑加速 2010年最新方法
    1、加快开关机速度

      XP中关机时,系统会发送消息到运行程序和远程服务器,告诉它们系统要关闭,并等待接到回应后系统才开始关机。加快开机速度,可以先设置自动结束任务,首先找到HKEY_CURRENT_USERControlPanelDesktop,把AutoEndTasks的键值设置为1;然后在该分支下有个“HungAppTimeout”,把它的值改为“4000(或更少),默认为50000;最后再找到HKEY_LOCAL_MACHINESystemCurrentContr

  • 在form里面,放了四个UEditor,怎么在后台分别获取它们值

    在form里面,放了四个UEditor,怎么在后台分别获取它们值

  • JAVA高并发的三种实现

    提到锁,大家肯定想到的是sychronized关键字。是用它可以解决一切并发问题,但是,对于系统吞吐量要求更高的话,我们这提供几个小技巧。帮助大家减小锁颗粒度,提高并发能力。初级技巧-乐观锁乐观锁使用的场景是,读不会冲突,写会冲突。同时读的频率远大于写。悲观锁的实现:悲观的认为所有代码执行都会有并发问题,所以将所有代码块都用sychronized锁住乐观锁的实现:…

发表回复

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

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