数据结构——C语言二叉树的非递归遍历的实现

先序遍历

• 先序遍历的思想是当栈不为空时就进行弹栈，并将数据输出，记得在每弹一个栈之后要进行两次压栈（这时候要判断其左右孩子是否为空，为空就不压），要注意的是这两次压栈是先压右孩子，再压左孩子，因为栈的先进后出原则。

void preord1(Bitree t){//先序遍历
    stack s;
    Bitree p;
    initstack(s);
    push(s,t);
    while(s.top!=s.base){
        while(gettop(s,p)&&p){
            pop(s,p);
            printf("%c",p->data);
            if(p->rchild!=NULL){
                push(s,p->rchild);
            }
            if(p->lchild!=NULL){
                push(s,p->lchild);
            }
        }
    }
}

中序遍历

• 中序遍历的大概思想是先一直向左压栈到头（空也压），然后每弹一个栈就转右，转右后再进行压左孩子的循环。
  

void inordl(Bitree t){//中序遍历
    stack s;
    Bitree p;
    initstack(s);
    push(s,t);
    while(s.top!=s.base){
        while(gettop(s,p)&&p){
            push(s,p->lchild);
        }
        pop(s,p);
        if(s.top!=s.base){
            pop(s,p);
            printf("%c",p->data);
            push(s,p->rchild);
        }
    }
}

后序遍历

• 用一个数组对其进行标记，只有当标记为1的时候才对其进行输出。

void posord1(Bitree t){//后序遍历
   int tag[100];
   int top=0;
   stack s;
   Bitree p;
   initstack(s);
   p=t;
   do{
       while(p){//扫描左子树
           top++;
           push(s,p);
           p=p->lchild;
           tag[top]=0;
       }
       while((s.top!=s.base)&&tag[top]==1){//p所指向的结点没有左子树或左子树已经访问过了
           pop(s,p);
           printf("%c",p->data);
           top--;
       }
       if(s.top!=s.base){
           gettop(s,p);
           p=p->rchild;
           tag[top]=1;
       }
       else{
           break;
       }
   }while(p||(s.top!=s.base));

输入

输出

代码

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

#define m 100

typedef char ElemType;
typedef struct Binodes{
    ElemType data;
    struct Binodes *lchild,*rchild;
}Nodes,*Bitree;
typedef Bitree sselemtype;  //别名的别名，有利于后续的更改
typedef struct stack{
    sselemtype *top,*base;
    int stacksize;
}stack;

int initstack(stack &s){
    s.base=(sselemtype *)malloc(m*sizeof(sselemtype));
    if(s.base==NULL){
        exit(-1);
    }
    s.top=s.base;
    s.stacksize=m;
    return 1;
}

int push(stack &s,sselemtype e){
    if(s.top-s.base>=s.stacksize){
        return 0;
    }
    *s.top++=e;
    return 1;
}
int pop(stack &s,sselemtype &e){
    if(s.top==s.base){
        return 0;
    }
    e=*--s.top;
    return 1;
}

int CreateTree(Bitree &T){//创建树
    ElemType value;
    scanf("%c",&value);
    if(value==' '){
        T=NULL;
    }
    else{
        T=(Nodes*)malloc(sizeof(Nodes));
        if(!T){
            exit(-2);
        }
        T->data=value;
        CreateTree(T->lchild);
        CreateTree(T->rchild);
    }
}
int gettop(stack s,Bitree &e){//读栈顶
    if(s.top==s.base){
        return 0;
    }
    e=*(s.top-1);
    return 1;
}
void preord1(Bitree t){//先序遍历
    stack s;
    Bitree p;
    initstack(s);
    push(s,t);
    while(s.top!=s.base){
        while(gettop(s,p)&&p){
            pop(s,p);
            printf("%c",p->data);
            if(p->rchild!=NULL){
                push(s,p->rchild);
            }
            if(p->lchild!=NULL){
                push(s,p->lchild);
            }
        }
    }
}
void inordl(Bitree t){//中序遍历
    stack s;
    Bitree p;
    initstack(s);
    push(s,t);
    while(s.top!=s.base){
        while(gettop(s,p)&&p){
            push(s,p->lchild);
        }
        pop(s,p);
        if(s.top!=s.base){
            pop(s,p);
            printf("%c",p->data);
            push(s,p->rchild);
        }
    }
}
void posord1(Bitree t){//后序遍历
    int tag[100];
    int top=0;
    stack s;
    Bitree p;
    initstack(s);
    p=t;
    do{
        while(p){//扫描左子树
            top++;
            push(s,p);
            p=p->lchild;
            tag[top]=0;
        }
        while((s.top!=s.base)&&tag[top]==1){//p所指向的结点没有左子树或左子树已经访问过了
            pop(s,p);
            printf("%c",p->data);
            top--;
        }
        if(s.top!=s.base){
            gettop(s,p);
            p=p->rchild;
            tag[top]=1;
        }
        else{
            break;
        }
    }while(p||(s.top!=s.base));
}

int main()
{
    Bitree T;
    CreateTree(T);
    printf("非递归的先根遍历顺序为：\n");
    preord1(T);
    printf("\n非递归的中根遍历顺序为：\n");
    inordl(T);
    printf("\n非递归的后根遍历顺序为：\n");
    posord1(T);
    return 0;
}