二叉树中序遍历(非递归)算法实现--C语言

落日映苍穹つ 2022-04-08 13:00 164阅读 0赞

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

首先给出今天的二叉树的示例图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_16_color_FFFFFF_t_70]

代码如下：

#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;
    }

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_16_color_FFFFFF_t_70]: /images/20220405/29a48e0c64614533a1a89f94c107d6dc.png
[20181214103600610.png]: /images/20220405/298d8b2cdae349b9a5598ded3cd31678.png