二叉树的遍历（非递归写法）-JZTXT

//二叉树的遍历（非递归算法）

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild,*rchild;//存储二叉树的左孩子和右孩子
}BiTNode,*BiTree;

typedef struct SNode
{
    BiTree data;//压入栈内的是BiTree型数据（即树的节点）
    struct SNode *next;
}SNode,*LinkStack;
//栈的主要操作是在栈顶进行插入和删除，所以将链表的头部看为栈顶最合适
bool initLinkStack(LinkStack &S)//链表初始化,将头指针所在的地址传进来
{
    S=NULL;//头指针应该指向栈顶，所以初始化赋为NULL
    return true;
}

void Push(LinkStack &S,BiTree value)//入栈操作
{
    SNode *p;
    p=(SNode *)malloc(sizeof(SNode));
    p->next=S;//链表的头部为头指针
    p->data=value;
    S=p;
}

bool isEmpty(LinkStack S)//判断栈是否为空
{
    if(S==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool Pop(LinkStack &S,BiTree &e)//出栈操作
{
    if(S==NULL)
    {
        return false;
    }
    else
    {
        e=S->data;
        SNode *q;//存储删除的节点来进行释放
        q=S;
        S=S->next;
        free(q);
        return true;
    } 
}



void InitTree(BiTree &root)
{
    root = (BiTNode *)malloc(sizeof(BiTNode));
    root->data = -1;
    root->lchild = NULL;
    root->rchild = NULL;
}

void visit(BiTNode *T)//访问函数
{
    printf("%d",T->data);
}

void InOrder2(BiTree T)//中序遍历
{
    LinkStack S;
    initLinkStack(S);
    BiTree p=T;//p是遍历指针
    while(p||!isEmpty(S))//用或运算来进行判定
    {
        if(p)
        {
            Push(S,p);//当前节点入栈
            p=p->lchild;
        }
        else
        {
            Pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}

void PreOrder2(BiTree T)//先序遍历
{
    LinkStack S;
    initLinkStack(S);
    BiTree p=T;
    while(p||!isEmpty(S))
    {
        if(p)
        {
            visit(p);
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            Pop(S,p);
            p=p->rchild;
        }
    }
}

int main()
{
    BiTree Tree;
    InitTree(Tree);
    printf("%d",Tree->data);
    return 0;
}