二叉树的非递归遍历

simpleset / 2023-08-14 / 原文

//非递归操作

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

#define MaxSize 200 

typedef struct TreeNode{
    int data;
    struct TreeNode *lchild,*rchild;
}TreeNode,*Tree;

typedef struct{
    Tree data[MaxSize];
    int top;
}Stack;

void InitStack(Stack &S)
{
    S.top=-1;
}

bool isEmpty(Stack S)
{
    if(S.top==-1)
    {
        return true;
    }
    return false;
}

int Push(Stack &S,Tree x)
{
    if(S.top==MaxSize-1)
    {
        return -1;
    }
    S.data[++S.top]=x;
    return 0;
}

int Pop(Stack &S,Tree &x)
{
    if(S.top==-1)
    {
        return -1;
    }
    x=S.data[S.top--];
    return 0;
}

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;
    }
    else
    {
        T=(Tree)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

//先序遍历非递归操作
void PreOrderTree(Tree T)
{
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    while(p || !isEmpty(S))
    {
        if(p)
        {
            printf("%d ",p->data);
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            Pop(S,p);
            p=p->rchild;
        }
    }    
} 

//中序遍历非递归操作
void MidOrderTree(Tree T)
{
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    while(p || !isEmpty(S))
    {
        if(p)
        {
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            Pop(S,p);
            printf("%d ",p->data);
            p=p->rchild;
        }
    }
}  
/*
//后序遍历非递归操作
void LatOrderTree(Tree T)
{
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    while(p || !isEmpty)
    {
        if(p)
        {
            Push(S,p);
            p=p->lchild;    
        }    
        else
        {
            
            Pop(S,p);
            p=p->rchild;
        }
    }    
} 
*/

int main()
{
    Tree T;
    CreateTree(T);
    PreOrderTree(T);
    
    return 0;
    
}