二叉树遍历-非递归算法

2024-02-17 17:05:58

构建一颗二叉树

         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);    //创建右子树
    }
}

中序遍历（非递归算法）

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

以上面二叉树的中序遍历为例，遍历过程如下（建议对照代码分析）；

结点A、B、D入栈，栈内元素【A，B，D】
结点D的左子树为空，然后D退栈并输出，栈内元素【A，B】
进入D的右子树，D的右子树为空，栈内元素【A，B】
继续退栈，即输出B 栈内元素【A】
访问B的右子树E，E进栈栈内元素【A，E】
访问E的左子树为空，退栈输出E 栈内元素【A】
访问E的右子树为空，退栈输出A 栈内元素【】
访问A的右子树，C，F入栈栈内元素【C，F】
F的左右子树均为空，退栈输出F，C 栈内元素【】
访问C的右子树G 栈内元素【G】
G的左右子树均为空，退栈并输出G 栈内元素【】
此时结点指针为空，并且栈也为空，遍历结束

代码：

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;
        }
    }
}

遍历过程：

输出A，A入栈栈内元素【A】
输出B，B入栈栈内元素【A，B】
输出D，D入栈栈内元素【A，B，D】
D退栈，输出E，E入栈栈内元素【A，B，E】
E退栈，输出C，C入栈栈内元素【A，B，C】
输出F，F入栈栈内元素【A，B，C，F】
F退栈，输出G，G入栈栈内元素【A，B，C，G】
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);
    }
}

遍历过程：

A，C，G入栈栈1【A，C，G】栈2【A，C，G】
G退，F进栈1【A,C,F 】栈2【A,C,G,F】
F,C 退，B进栈1【A，B 】栈2【A,C,G,F,B】
E进栈1【A，B，E】栈2【A,C,G,F,B,E】
E退，D进栈1【A，B，D】栈2【A,C,G,F,B,E,D】
输出栈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
*/

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

码农公寓

构建一颗二叉树

中序遍历（非递归算法）

先序遍历（非递归算法）

后序遍历（非递归算法）

完整代码：

相关文章