二叉树二叉链表的非递归中序遍历（C语言）

#include <stdio.h>
#include <stdlib.h>

/**
* 二叉树二叉链表之非递归遍历：中序遍历
*算法思想：建立一个栈；根结点进栈，遍历左子树；根结点出栈，访问根结点，遍历右子树。 
*/

#define OK 1;
#define TURE 1;
#define FALSE 0;
const int OVERFLOW = -2;


typedef int Status;
typedef char TElemType;
//二叉链表结构定义 
typedef struct BiNode{
    TElemType data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

//链栈的定义 
typedef struct StackNode {
    BiTree data;  //数据域
    struct StackNode *next;  //指针域
}StackNode,*LinkStack;

//由字符序列创建二叉树
Status CreateBiTree(BiTree *tree,TElemType data[],int *j,int len){
    if((*j)<=len-1){
        if(data[(*j)]==‘#‘){
            (*tree)=NULL;
            (*j)++;
        } else {
            (*tree)=(BiTree)malloc(sizeof(BiNode));
            if(!(*tree)) return OVERFLOW;
            (*tree)->data=data[(*j)];  //生成根结点 
            (*j)++;
            CreateBiTree(&((*tree)->lchild),data,j,len);  //构造左子树 
            CreateBiTree(&((*tree)->rchild),data,j,len);  //构造右子树
        }
    }
    return OK;
}

//访问二叉树结点 
Status Visit(BiTree tree){
    printf("%c",tree->data);
    return OK;
}

//借助栈实现二叉链表的非递归中序遍历 
Status InOrderTraverse_ByStack(BiTree tree){
    LinkStack stack1;
    InitStack(&stack1);
    BiTree q,p=tree;
    
    while(p||!StackIsEmpty(stack1)){
        if(p){
            Push(&stack1,p);
            p=p->lchild;
        } else {
            Pop(&stack1,&q);
            Visit(q);
            p=q->rchild;
        }
    }
    return OK;    
}


/***用到栈的相关函数***/ 
//链栈初始化
Status InitStack(LinkStack *stack){
    //构造一个空栈，栈顶指针置为空
    *stack=NULL;
    return OK;
}
//判断链栈是否为空
Status StackIsEmpty(LinkStack stack){
    if(stack==NULL){
        return TURE;
    } else {
        return FALSE;
    }
}
//元素进入链栈 
Status Push(LinkStack *stack,BiTree elem){
    StackNode *newNode;  //定义指向新结点指针
    newNode=(StackNode*)malloc(sizeof(StackNode));  //新节点分配空间
    newNode->data=elem;  //新结点数据域赋值
    newNode->next=(*stack);  //新结点指针域指向原栈顶
    (*stack)=newNode;  //更新栈顶
    return OK;
}
//顺序栈的出栈操作
Status Pop(LinkStack *stack,BiTree *elem){
    StackNode *waitDeleted;  //定义指向待出栈结点指针
    waitDeleted=(*stack);  //待出栈结点(栈顶结点)
    *elem=waitDeleted->data;  //elem存放出栈元素值
    (*stack)=(*stack)->next;  //更新栈顶
    free(waitDeleted);  //释放已出栈的结点空间
    return OK;
}

int main(void){
    //示例二叉树的结构
    /*
                A
              /
            B
          /          C      D
            /             E    F
                         G
    */ 
    
    //指向二叉树的指针 
    BiTree bitree1;
    
    //创建二叉树 待用数据 
    TElemType data1[]={‘A‘,‘B‘,‘C‘,‘#‘,‘#‘,‘D‘,‘E‘,‘#‘,‘G‘,‘#‘,‘#‘,‘F‘,‘#‘,‘#‘,‘#‘,};  //先序遍历序列 
    int len1=sizeof(data1)/sizeof(data1[0]);
    int* j1=(int*)malloc(sizeof(int));
    *j1=0;
    
    //按先序遍历序列创建二叉树 
    Status createBiTreeResult = CreateBiTree(&bitree1,data1,j1,len1);
    printf("二叉树创建结果：%d\n",createBiTreeResult);
    
    //非递归中序遍历二叉树 
    Status inOrderTraverse_ByStack = InOrderTraverse_ByStack(bitree1);
    printf("\n二叉树非递归中序遍历结果：%d\n",inOrderTraverse_ByStack);
    
    printf("\nEND");
    return 0;
}