二叉树后序遍历(递归与非递归)
精华
小牛编辑
225浏览
2023-03-14
二叉树后序遍历的实现思想是:从根节点出发,依次遍历各节点的左右子树,直到当前节点左右子树遍历完成后,才访问该节点元素。
图 1 二叉树
如图 1 中,对此二叉树进行后序遍历的操作过程为:
后序遍历是在遍历完当前结点的左右孩子之后,才调用操作函数,所以需要在操作结点进栈时,为每个结点配备一个标志位。当遍历该结点的左孩子时,设置当前结点的标志位为 0,进栈;当要遍历该结点的右孩子时,设置当前结点的标志位为 1,进栈。
这样,当遍历完成,该结点弹栈时,查看该结点的标志位的值:如果是 0,表示该结点的右孩子还没有遍历;反之如果是 1,说明该结点的左右孩子都遍历完成,可以调用操作函数。
完整实现代码为:
图 1 二叉树
- 从根节点 1 开始,遍历该节点的左子树(以节点 2 为根节点);
- 遍历节点 2 的左子树(以节点 4 为根节点);
- 由于节点 4 既没有左子树,也没有右子树,此时访问该节点中的元素 4,并回退到节点 2 ,遍历节点 2 的右子树(以 5 为根节点);
- 由于节点 5 无左右子树,因此可以访问节点 5 ,并且此时节点 2 的左右子树也遍历完成,因此也可以访问节点 2;
- 此时回退到节点 1 ,开始遍历节点 1 的右子树(以节点 3 为根节点);
- 遍历节点 3 的左子树(以节点 6 为根节点);
- 由于节点 6 无左右子树,因此访问节点 6,并回退到节点 3,开始遍历节点 3 的右子树(以节点 7 为根节点);
- 由于节点 7 无左右子树,因此访问节点 7,并且节点 3 的左右子树也遍历完成,可以访问节点 3;节点 1 的左右子树也遍历完成,可以访问节点 1;
- 到此,整棵树的遍历结束。
4 5 2 6 7 3 1
递归实现
后序遍历的递归实现代码为:#include <stdio.h> #include <string.h> #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
4 5 2 6 7 3 1
非递归实现
递归算法底层的实现使用的是 栈存储结构,所以可以直接使用栈写出相应的非递归算法。后序遍历是在遍历完当前结点的左右孩子之后,才调用操作函数,所以需要在操作结点进栈时,为每个结点配备一个标志位。当遍历该结点的左孩子时,设置当前结点的标志位为 0,进栈;当要遍历该结点的右孩子时,设置当前结点的标志位为 1,进栈。
这样,当遍历完成,该结点弹栈时,查看该结点的标志位的值:如果是 0,表示该结点的右孩子还没有遍历;反之如果是 1,说明该结点的左右孩子都遍历完成,可以调用操作函数。
完整实现代码为:
#include <stdio.h> #include <string.h> #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
4 5 2 6 7 3 1