（数据结构）二叉树后序遍历

二叉树后序遍历

二叉树后序遍历的实现思想是：

访问当前节点的左子树
访问当前节点的右子树
访问根节点

图 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

因此，图 1 中二叉树采用中序遍历得到的序列为： $4 5 2 6 7 3 1$

二叉树后序遍历代码实现

先谈一下递归实现！！！

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

再谈一下非递归实现！！！

#include <stdio.h>
#include <stdlib.h>int top = -1;  // top变量表示栈顶元素所在位置typedef struct MyBiTNode{int data;  // 数据域struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode;BiTNode *CreateBiTree(BiTNode *T){// 结点 1 T = (BiTNode*)malloc(sizeof(BiTNode));T->data = 1;// 结点 2T->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->data = 2;// 结点 3T->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->data = 3;// 结点 4 T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->lchild->data = 4;T->lchild->lchild->lchild = NULL;T->lchild->lchild->rchild = NULL;// 结点 5T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->rchild->data = 5;T->lchild->rchild->lchild = NULL;T->lchild->rchild->rchild = NULL;// 结点 6T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->lchild->data = 6;T->rchild->lchild->lchild = NULL;T->rchild->lchild->rchild = NULL;// 结点 7T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->rchild->data = 7; T->rchild->rchild->lchild = NULL;T->rchild->rchild->rchild = NULL;return T;
}// 模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){printf("%d ", elem->data);
}// 弹栈函数 
void pop(){if(top == -1){return;}top--;
}// 后序遍历非递归算法
typedef struct SNode{BiTNode *p;int tag;
} SNode;// 后序遍历使用的进栈函数
void postpush(SNode *a, SNode sdata){a[++top] = sdata;
}// 后序遍历函数
void PostOrderTraverse(BiTNode *Tree){SNode a[20];BiTNode *p;int tag;SNode sdata;p = Tree;  // 根结点 while(p || top!=-1) {while(p){sdata.p = p;sdata.tag = 0;postpush(a, sdata);// a[0] = {Tree, 0};a[1] = {Tree->lchild, 0};a[2] = {Tree->lchild->lchild, 0}// a[2] = {Tree->lchild->rchild, 0}p = p->lchild;  // 指向左结点 }sdata = a[top];// sadta = a[2] = {Tree->lchild->lchild, 0} -- 4// sadta = a[2] = {Tree->lchild->lchild, 1} -- 4// sadta = a[1] = {Tree->lchild, 0} -- 2// sadta = a[2] = {Tree->lchild->rchild, 0} -- 5 pop();  // top == 1; top == 1; top == 0; top == 1 p = sdata.p;  // Tree->lchild->lchild;Tree->lchild->lchild;Tree->lchild;Tree->lchild->rchildtag = sdata.tag;  // 0 1 0 0if(tag == 0) {sdata.p = p;  // Tree->lchild->lchild;Tree->lchildsdata.tag = 1;  // 1 1postpush(a, sdata);  // a[2] = {Tree->lchild->lchild, 1};a[1] = {Tree->lchild, 1}p = p->rchild;  // NULL Tree->lchild->rchild}else{displayElem(p);  // 4p = NULL;}}
}int main() {BiTNode *Tree = NULL;  // 结构体指针指向空 Tree = CreateBiTree(Tree);  // 传入结构体指针 printf("%d\n",Tree->rchild->lchild->data);  // 4 PostOrderTraverse(Tree);return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/253786.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！