二叉树遍历-非递归算法

构建一颗二叉树

         A
        / \
       B    C
      / \  / \
     D   E F  G
    前序:ABDECFG
    中序:DBEAFCG
    后序:DEBFGCA

上述完全二叉树可以利用先序遍历(递归)的方式输入,代码如下(‘#’代表空树):

void CreateBiTree(BiTree *T)
{
    TElemType e;
    
    if ((e=getchar()) == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree) malloc(sizeof(BiTNode));
        if (!T)
        {
            exit(0);
        }
        (*T)->data = e;
        CreateBiTree(&(*T)->lchild);    //创建左子树
        CreateBiTree(&(*T)->rchild);    //创建右子树
    }
}

中序遍历(非递归算法)

原理: 依次访问二叉树的左子树,并将指向结点的指针存入栈中,当指针为空时,表示左子树访问完毕,此时应退栈输出结点数据,然后访问右子树;

以上面二叉树的中序遍历为例,遍历过程如下(建议对照代码分析);

  1. 结点A、B、D入栈 , 栈内元素【A,B,D】
  2. 结点D的左子树为空,然后D退栈并输出 ,栈内元素【A,B】
  3. 进入D的右子树,D的右子树为空, 栈内元素【A,B】
  4. 继续退栈,即输出B 栈内元素【A】
  5. 访问B的右子树E,E进栈 栈内元素【A,E】
  6. 访问E的左子树为空,退栈输出E 栈内元素【A】
  7. 访问E的右子树为空,退栈输出A 栈内元素【】
  8. 访问A的右子树,C,F入栈 栈内元素【C,F】
  9. F的左右子树均为空,退栈输出F,C 栈内元素【】
  10. 访问C的右子树G 栈内元素【G】
  11. G的左右子树均为空,退栈并输出G 栈内元素【】
  12. 此时结点指针为空,并且栈也为空,遍历结束

代码:

void InorderTraverse(BiTree T,Stack *s)
{
    BiTree P=T;
    while(P||s->stacksize!=0)
    {
        if(P)
        {
            Push(s, P);
            P=P->lchild;
        }
        else
        {
            P=Pop(s);
            printf("%c ",P->data);
            P=P->rchild;
        }
    }
}

先序遍历(非递归算法)

先序遍历的思想与中序的思想基本一致,只是代码在输出位置上的不同;

void preOrderTraverse(BiTree T,Stack *s)
{
    BiTree p=T;
    while(p||s->stacksize!=0)
    {
        if(p)
        {
            printf("%c ",p->data);
            Push(s, p);
            p=p->lchild;
        }
        else
        {
            p=Pop(s);
            p=p->rchild;
        }
    }
}

遍历过程:

  1. 输出A,A入栈 栈内元素【A】

  2. 输出B,B入栈 栈内元素【A,B】

  3. 输出D,D入栈 栈内元素【A,B,D】

  4. D退栈,输出E,E入栈 栈内元素【A,B,E】

  5. E退栈,输出C,C入栈 栈内元素【A,B,C】

  6. 输出F,F入栈 栈内元素【A,B,C,F】

  7. F退栈,输出G,G入栈 栈内元素【A,B,C,G】

  8. G,C,B,A的右子树均为空,依次出栈

后序遍历(非递归算法)

后序遍历为 左、右、根,和先序,中序相比较为复杂;因为先序与后序遍历,根结点与左孩子都是相邻输出的,而后序遍历需要最后输出根结点,因此应先访问右子树,下面的算法,借助另外一个栈完成后序遍历;

void PostOrderTraverse(BiTree T,Stack *s1,Stack *s2)
{
    BiTree p=T;
    while(p||s1->stacksize!=0)
    {
        if(p)
        {
            Push(s1,p);
            Push(s2,p);
            p=p->rchild;
        }
        else
        {
            p=Pop(s1);
            p=p->lchild;
        }
    }
    while(s2->stacksize!=0)
    {
        p=Pop(s2);
        printf("%c ",p->data);
    }
}

遍历过程:

  1. A,C,G入栈 栈1【A,C,G】 栈2【A,C,G】
  2. G退,F进 栈1【A,C,F 】 栈2【A,C,G,F】
  3. F,C 退,B进 栈1【A,B 】 栈2【A,C,G,F,B】
  4. E进 栈1【A,B,E】 栈2【A,C,G,F,B,E】
  5. E退,D进 栈1【A,B,D】 栈2【A,C,G,F,B,E,D】
  6. 输出栈2,即为后序序列

这种算法,要求二叉树的所有结点都要进栈,因此比较消耗存储空间

完整代码:

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

typedef char TElemType;
//树结构
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//栈结构
typedef struct Stack
{
    BiTree  date;
    int stacksize;  //记录元素个数
    struct Stack *next;
    struct Stack *base;  //栈底指针
    struct Stack *top;  //栈顶指针
}Stack;


//栈初始化
void InitStack(Stack *s)
{
    s->stacksize=0;
    s->base=NULL;
    s->top=s->base;
}

//插入数据
void Push(Stack *s,BiTree T)
{
        Stack *p;
        p=(Stack *)malloc(sizeof(Stack));
        if(!p)
            exit(0);
        p->date=T;
        if(s->stacksize==0)  //当插入第一个元素时,指针的变化
        {
            s->base=p;    //赋给栈底指针
            s->top=p;
            p->next=NULL;
        }
        else
        {
            p->next=s->top;
            s->top=p;
            
        }
        s->stacksize++;
}


//删除并返回栈顶元素
BiTree Pop(Stack *s)
{
    BiTree t;
    Stack *p;
    p=s->top;
    t=p->date;
    s->top=p->next;
    free(p);
    s->stacksize--;
    return t;
}

/*构建二叉树*/
void CreateBiTree(BiTree *T)
{
    TElemType e;
    
    if ((e=getchar()) == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree) malloc(sizeof(BiTNode));
        if (!T)
        {
            exit(0);
        }
        (*T)->data = e;
        CreateBiTree(&(*T)->lchild);    //创建左子树
        CreateBiTree(&(*T)->rchild);    //创建右子树
    }
}

//中序遍历(非递归)
void InorderTraverse(BiTree T,Stack *s)
{
    BiTree P=T;
    while(P||s->stacksize!=0)
    {
        if(P)
        {
            Push(s, P);
            P=P->lchild;
        }
        else
        {
            P=Pop(s);
            printf("%c ",P->data);
            P=P->rchild;
        }
    }
}

//先序遍历(非递归)
void preOrderTraverse(BiTree T,Stack *s)
{
    BiTree p=T;
    while(p||s->stacksize!=0)
    {
        if(p)
        {
            printf("%c ",p->data);
            Push(s, p);
            p=p->lchild;
        }
        else
        {
            p=Pop(s);
            p=p->rchild;
        }
    }
}

//后序遍历
void PostOrderTraverse(BiTree T,Stack *s1,Stack *s2)
{
    BiTree p=T;
    while(p||s1->stacksize!=0)
    {
        if(p)
        {
            Push(s1,p);
            Push(s2,p);
            p=p->rchild;
        }
        else
        {
            p=Pop(s1);
            p=p->lchild;
        }
    }
    while(s2->stacksize!=0)
    {
        p=Pop(s2);
        printf("%c ",p->data);
    }
}

int main()
{
    printf("请输入二叉树,#代表空树:\n");
    BiTree T;
    Stack stack1,stack2,*p1,*p;
    p=&stack1;p1=&stack2;
    InitStack(p);
    InitStack(p1);
    CreateBiTree(&T);
    printf("前序遍历结果为:");
    preOrderTraverse(T, p);
    printf("\n");
    printf("中序遍历结果为:");
    InorderTraverse(T, p);
    printf("\n");
    printf("后序遍历结果为:");
    PostOrderTraverse(T, p,p1);
    printf("\n");
    return 0;
}
/* 测试
ABD##E##CF##G##
前序遍历结果为:A B D E C F G 
中序遍历结果为:D B E A F C G 
后序遍历结果为:D E B F G C A 
Program ended with exit code: 0
*/

后记:我不知道这篇博客算不算详解,在写的过程中,对代码有了更深的理解,也对整个遍历过程有了更深的了解,希望这篇文章对你可以有一点点帮助

上一篇:数据结构实验二


下一篇:c语言描述-栈的基本操作