在线客服:
亚博直播 亚博直播
全国服务热线:010-34915482
您的位置:首页 > 新闻中心 >

二叉树后遍历(递归和非递归)算法C语言实现

浏览 146次 来源:【jake推荐】 作者:-=Jake=-    时间:2021-01-19 08:03:16
[摘要] 中二叉树进行后序遍历的结果为:递归实现后序遍历的递归实现代码为:非递归实现递归算法底层的实现使用的是栈存储结构,所以可以直接使用栈写出相应的非递归算法。后序遍历是在遍历完当前结点的左右孩子之后,才调用操作函数,所以需要在操作结点进栈时,为每个结点配备一个标志位。

实现二叉树的后序遍历的想法是:从根节点开始,依次遍历每个节点的左右子树亚博vip登陆 ,并访问节点元素直到当前的左右子树遍历该节点。

二叉树遍历非递归

图1二叉树

如图1所示,该二叉树的后遍历操作过程为:因此yobo体育 ,图1中二叉树的后遍历结果为:

4 5 2 6 7 3 1

用于后遍历的递归实现的递归实现代码为:

#include 
#include 
#define TElemType int
//构造结点的结构体
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
//模拟操作结点元素的函数,输出结点本身的数值
void displayElem(BiTNode* elem){
    printf("%d ",elem->data);
}
//后序遍历
void PostOrderTraverse(BiTree T){
    if (T) {
        PostOrderTraverse(T->lchild);//遍历左孩子
        PostOrderTraverse(T->rchild);//遍历右孩子
        displayElem(T);//调用操作结点数据的函数方法
    }
    //如果结点为空,返回上一层
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("后序遍历: \n");
    PostOrderTraverse(Tree);
}

运行结果:

后遍历:

4 5 2 6 7 3 1

非递归实现递归算法的基础实现使用堆栈存储结构五大联赛下注 ,因此您可以直接使用堆栈来编写相应的非递归算法。

后序遍历是在遍历当前节点的左,右子级之后调用操作函数。因此,当将操作节点压入堆栈时,必须为每个节点配备标志。遍历该节点的左子节点时,将当前节点的标志位设置为0并压入堆栈;遍历该节点的右子节点时,请将当前节点的标志位设置为1凤凰体育下载 ,然后推入堆栈。

这样二叉树遍历非递归,当遍历完成并且该节点弹出堆栈时,检查该节点的标志位的值:如果为0,则表示该节点的右子节点尚未遍历。 否则,如果为1,则表示遍历的左右子节点已完成二叉树遍历非递归,可以调用操作函数。

完整的实现代码为:

#include 
#include 
#define TElemType int
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
//弹栈函数
void pop( ){
    if (top==-1) {
        return ;
    }
    top--;
}
//模拟操作结点元素的函数,输出结点本身的数值
void displayElem(BiTNode* elem){
    printf("%d ",elem->data);
}
//后序遍历非递归算法
typedef struct SNode{
    BiTree p;
    int tag;
}SNode;
//后序遍历使用的进栈函数
void postpush(SNode *a,SNode sdata){
    a[++top]=sdata;
}
//后序遍历函数
void PostOrderTraverse(BiTree Tree){
    SNode a[20];//定义一个顺序栈
    BiTNode * p;//临时指针
    int tag;
    SNode sdata;
    p=Tree;
    while (p||top!=-1) {
        while (p) {
            //为该结点入栈做准备
            sdata.p=p;
            sdata.tag=0;//由于遍历是左孩子,设置标志位为0
            postpush(a, sdata);//压栈
            p=p->lchild;//以该结点为根结点,遍历左孩子
        }
        sdata=a[top];//取栈顶元素
        pop();//栈顶元素弹栈
        p=sdata.p;
        tag=sdata.tag;
        //如果tag==0,说明该结点还没有遍历它的右孩子
        if (tag==0) {
            sdata.p=p;
            sdata.tag=1;
            postpush(a, sdata);//更改该结点的标志位,重新压栈
            p=p->rchild;//以该结点的右孩子为根结点,重复循环
        }
        //如果取出来的栈顶元素的tag==1,说明此结点左右子树都遍历完了,可以调用操作函数了
        else{
            displayElem(p);
            p=NULL;
        }
    }
}
int main(){
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("后序遍历: \n");
    PostOrderTraverse(Tree);
}

运行结果

后遍历:

4 5 2 6 7 3 1

老王
本文标签:递归,后序遍历,递归算法

推荐阅读

最新评论