首页 > 代码库 > C语言非递归实现二叉树的先序、中序、后序遍历

C语言非递归实现二叉树的先序、中序、后序遍历

#include <stdio.h>      
#include <stdlib.h>      
#define INIT_STACK_SIZE 100      
#define STACKINCREMENT 10      
      
//*****二叉树的二叉链表存储结构*****//  
typedef struct BiNode      
{      
    char data;      
    struct BiNode *lchild, *rchild;     
    int visitcount;                 //访问次数(后序遍历会用到)  
}BiNode, *BiTree;      
      
typedef struct      
{      
    BiNode **base;      
    BiNode **top;      
    int stacksize;      
}SqStack;      
  
//*****初始化栈*****//     
void InitStack(SqStack &S)                   
{      
    if (!(S.base = (BiNode **)malloc(sizeof(BiTree) * INIT_STACK_SIZE)))      
    {      
        return;      
    }      
    S.top = S.base;      
    S.stacksize = INIT_STACK_SIZE;      
      
    return;      
}      
      
//*****元素进栈*****//  
void Push(SqStack &S, BiNode *e)             
{      
    if (S.top - S.base >= S.stacksize)      
    {      
        if (!(S.base = (BiNode **)realloc(S.base, sizeof(BiTree) * (STACKINCREMENT + S.stacksize))))    
        {      
            return;      
        }      
        S.stacksize += STACKINCREMENT;      
    }      
    *S.top++ = e;      
      
    return;      
}      
      
//*****元素出栈*****//  
void Pop(SqStack &S, BiNode **e)             
{      
    if (S.base == S.top)      
    {      
        return;      
    }      
    *e = *--S.top;      
      
    return;      
}      
  
//*****取栈顶元素*****//      
int GetTop(SqStack S, BiNode **e)      
{      
    if (S.base == S.top)      
    {      
        return 0;      
    }      
    *e = *(S.top - 1);      
          
    return 1;      
}      
      
//*****判断栈是否为空*****//    
int StackEmpty(SqStack S)           
{      
    if (S.top == S.base)      
        return 1;      
    else      
        return 0;      
}      
  
//*****按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树构造二叉链表表示的二叉树T*****//      
void CreateBiTree(BiTree &T)              
{                                         
    char ch;        
    scanf("%c", &ch);        
    if(ch == ' ')        
    {        
        T = NULL;        
    }        
    else        
    {        
        if(!(T = (BiNode *)malloc(sizeof(BiNode))))         
        {        
            return;        
        }        
        T->data = http://www.mamicode.com/ch;                    //生成根结点        >

以如下二叉树为例,给出按先序次序输入二叉树中结点的值(字符),从而按照本文给出的算法构造二叉树。


输入字符的顺序是:-+a空格空格*b空格空格-c空格空格d空格空格/e空格空格f空格空格,即可验证本文给出的遍历算法。

C语言非递归实现二叉树的先序、中序、后序遍历