[数据结构与算法]二叉树的非递归遍历

## 二叉树的非递归遍历，无可避免要使用栈的相关知识那么下面我们就先复习一下有关于栈的基础知识。

好啦！咱们复习完关于栈的知识就可以开始非递归遍历的分析啦。

咱先创建好栈以及出入栈的函数备用。

pStack CreatStack()
{
    pStack top = NULL;
    top = (pStack)malloc(sizeof(stack));
    top->pTop = NULL;
    return top;
}

void push(pStack pS,pNode pTree)
{
    pStack pNew = (pStack)malloc(sizeof(stack));
    pNew->tree = pTree;

    pStack p = pS->pTop;
    pS->pTop = pNew;
    pNew->pTop = p;
}

pNode pop(pStack p)
{
    pStack pRes = p->pTop;
    p->pTop = p->pTop->pTop;

    return pRes->tree;
}

int isEmpty(pStack p)
{
    if(p->pTop)return 0;
    return 1;
}

先进行先序遍历

void Fprint(pNode root)
{
    pStack stack = CreatStack();
    pNode pCur = root;

    while (pCur || !isEmpty(stack))
    {
        while(pCur){
            printf("%c",pCur->Data);
            push(stack,pCur);
            pCur = pCur->Lchild;
        }
        if(!isEmpty(stack)){
            pCur = pop(stack);
            pCur = pCur->Rchild;
        }
    }
    return;
}

然后再看看中序遍历

void Sprint(pNode root)
{
    pNode pCur = root;
    pStack stack = CreatStack();
    while(pCur ||!isEmpty(stack))
    {
        while(pCur)
        {
            push(stack,pCur);
            pCur = pCur->Lchild;
        }
        if(!isEmpty(stack))
        {
            pCur = pop(stack);
            printf("%c",pCur->Data);
            pCur = pCur->Rchild;
        }
    }

    return;
}

最后再看看后续遍历

void Tprint(pNode root)
{
    if(!root) return ;
    Tprint(root->Lchild);
    Tprint(root->Rchild);
    printf("%c",root->Data);
    return;
}

完整代码

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

typedef struct Node
{
    char Data;
    struct Node * Lchild;
    struct Node * Rchild;
}node,*pNode;

typedef struct Stack
{
    pNode tree;
    struct Stack * pTop;
}stack,*pStack;

pStack CreatStack();
void push(pStack,pNode);
pNode pop(pStack);
int isEmpty(pStack);

pNode CreatTree();
void Fprint(pNode);
void Sprint(pNode);
void Thprint(pNode);
void Tprint(pNode);

int main(void)
{
    pNode root = CreatTree();
    Fprint(root);
       printf("\n");
    Sprint(root);
    printf("\n");
    Thprint(root); 

    return 0;
}

pNode CreatTree()
{
    pNode root;

    char ch = getchar();
    if(ch == '#') return NULL;
    
    root = (pNode)malloc(sizeof(node));
    root->Data = ch;
    root->Lchild = CreatTree();
    root->Rchild = CreatTree();

    return root;
}
//先序遍历 
void Fprint(pNode root)
{
    pStack stack = CreatStack();
    pNode pCur = root;

    while (pCur || !isEmpty(stack))
    {
        while(pCur){
            printf("%c",pCur->Data);
            push(stack,pCur);
            pCur = pCur->Lchild;
        }
        if(!isEmpty(stack)){
            pCur = pop(stack);
            pCur = pCur->Rchild;
        }
    }
    return;
}
//中序遍历 
void Sprint(pNode root)
{
    pNode pCur = root;
    pStack stack = CreatStack();
    while(pCur ||!isEmpty(stack))
    {
        while(pCur)
        {
            push(stack,pCur);
            pCur = pCur->Lchild;
        }
        if(!isEmpty(stack))
        {
            pCur = pop(stack);
            printf("%c",pCur->Data);
            pCur = pCur->Rchild;
        }
    }

    return;
}
//后续遍历 
void Thprint(pNode root)
{
    if(!root) return ;
    Tprint(root->Lchild);
    Tprint(root->Rchild);
    printf("%c",root->Data);
    return;
}


void Tprint(pNode root)
{
    
    if(!root) return;
    if(root->Lchild){
        Tprint(root->Lchild);
    }
    if(root->Rchild){
        Tprint(root->Rchild);
    }
    printf("%c",root->Data);

    return;
}


pStack CreatStack()
{
    pStack top = NULL;
    top = (pStack)malloc(sizeof(stack));
    top->pTop = NULL;
    return top;
}

void push(pStack pS,pNode pTree)
{
    pStack pNew = (pStack)malloc(sizeof(stack));
    pNew->tree = pTree;

    pStack p = pS->pTop;
    pS->pTop = pNew;
    pNew->pTop = p;
}

pNode pop(pStack p)
{
    pStack pRes = p->pTop;
    p->pTop = p->pTop->pTop;

    return pRes->tree;
}

int isEmpty(pStack p)
{
    if(p->pTop)return 0;
    return 1;
}

上面就是二叉树的非递归啦。
下次再见！！