五分钟C语言数据结构 之 二叉树后序遍历（非递归很重要）
五分钟C语言实现常见数据结构 之 二叉树后序遍历
五分钟C语言实现常见数据结构
今天的内容分享的是二叉树后序遍历
欢迎关注动态规划长文
二叉树后序遍历
二叉树的遍历方式主要由先序遍历、中序遍历和后续遍历，然后就是层次遍历
感受完前两篇的遍历方式，本节来看看后序遍历
后序遍历过程
a. 先序遍历其左子树；
b. 先序遍历其右子树；
c. 访问根节点；
然后就是一直递归下去，在访问到节点的时候，可以进行节点的相关处理，比如说简单的访问节点值
下图是一棵二叉树，我们来手动模拟一下后序遍历过程
按照上述后序遍历的过程，得到后序遍历序列：
H I D E B F G C A递归实现
二叉树的后序遍历利用上述的递归思想进行C语言代码实现：
树形结构按照上述树形结构进行初始化
# include <stdio.h># include <string.h># include <stdlib.h># define ElementType char//结点结构体typedef struct BinTNode{ElementType data;struct BinTNode * left;struct BinTNode * right;}BinTNode, *BinTree;// 初始化树形结构BinTNode * CreateBiTree(BinTNode *T){T=(BinTNode*)malloc(sizeof(BinTNode));T->data='A';T->left=(BinTNode*)malloc(sizeof(BinTNode));T->left->data='B';T->right=(BinTNode*)malloc(sizeof(BinTNode));T->right->data='C';T->left->left=(BinTNode*)malloc(sizeof(BinTNode));T->left->left->data='D';T->left->right=(BinTNode*)malloc(sizeof(BinTNode));T->left->right->data='E';T->left->right->left=NULL;T->left->right->right=NULL;T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));T->left->left->left->data='H';T->left->left->left->left=NULL;T->left->left->left->right=NULL;T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));T->left->left->right->data='I';T->left->left->right->left=NULL;T->left->left->right->right=NULL;T->right->left=(BinTNode*)malloc(sizeof(BinTNode));T->right->left->data='F';T->right->left->left=NULL;T->right->left->right=NULL;T->right->right=(BinTNode*)malloc(sizeof(BinTNode));T->right->right->data='G';T->right->right->left=NULL;T->right->right->right=NULL;return T;}// 遍历过程中，输出节点值void printElement(BinTNode * T){printf("%c ",T->data);}//先序遍历void PostOrderTraverse(BinTNode * T){if (T) {PostOrderTraverse(T->left); //递归访问左孩子PostOrderTraverse(T->right); //递归访问右孩子printElement(T); //输出节点值}// 当节点为空的时候，返回return;}int main() {BinTNode * Tree;Tree = CreateBiTree(Tree); // 初始化树形结构printf("后序遍历: ");PostOrderTraverse(Tree); // 先序递归进行printf("\n"); // 最后换行return 0;}
运行结果：
后序遍历: H I D E B F G C A非递归实现
相比于之前的先序遍历和中序遍历非递归实现，后序遍历的非递归算法与之前有所不同，后续遍历需要先访问左右子结点后，才能访问该结点，而这也是非递归的难点所在。
考虑了几种实现的方案，这里我给出我认为比较清晰的一个方案供大家参考：借助两个栈（S1和S2）来进行操作
看下面伪代码：
初始化S1的top元素是树的根结点;while(top1 != -1) {将栈顶元素push到S2;if(栈顶元素有孩子结点){按照孩子结点的左右顺序push进S1;}}循环逐个弹出S2的栈顶元素
伪代码可能看了之后有些不太好懂，但是还算看着清晰吧，下面借助图，一定会思路清晰的（长图发放）：
有了这个思路就应该会很清晰了，下面按照上述思路用C语言实现：
#include <stdio.h>#include <string.h>#include <stdlib.h>#define ElementType charint top_S1 = -1; //定义栈S1 top下标int top_S2 = -1; //定义栈S2 top下标// 结点结构体typedef struct BinTNode{ElementType data;struct BinTNode * left;struct BinTNode * right;}BinTNode, *BinTree;// 初始化树形结构BinTNode * CreateBiTree(BinTNode *T) {T=(BinTNode*)malloc(sizeof(BinTNode));T->data='A';T->left=(BinTNode*)malloc(sizeof(BinTNode));T->left->data='B';T->right=(BinTNode*)malloc(sizeof(BinTNode));T->right->data='C';T->left->left=(BinTNode*)malloc(sizeof(BinTNode));T->left->left->data='D';T->left->right=(BinTNode*)malloc(sizeof(BinTNode));T->left->right->data='E';T->left->right->left=NULL;T->left->right->right=NULL;T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));T->left->left->left->data='H';T->left->left->left->left=NULL;T->left->left->left->right=NULL;T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));T->left->left->right->data='I';T->left->left->right->left=NULL;T->left->left->right->right=NULL;T->right->left=(BinTNode*)malloc(sizeof(BinTNode));T->right->left->data='F';T->right->left->left=NULL;T->right->left->right=NULL;T->right->right=(BinTNode*)malloc(sizeof(BinTNode));T->right->right->data='G';T->right->right->left=NULL;T->right->right->right=NULL;return T;}// 栈S1 - 进栈pushvoid push_S1(BinTNode** stack,BinTNode * elem) {stack[++top_S1] = elem;}// 栈S2 - 进栈pushvoid push_S2(BinTNode** stack,BinTNode * elem) {stack[++top_S2] = elem;}//栈S1 - 弹栈popvoid pop_S1(){if (top_S1 == -1) {return ;}top_S1--;}//栈S2 - 弹栈popvoid pop_S2(){if (top_S2 == -1) {return ;}top_S2--;}// 遍历过程中，输出结点值void printElement(BinTNode* elem) {printf("%c ",elem->data);}//获取栈顶元素BinTNode * getTop_S1(BinTNode** stack){return stack[top_S1];}//获取栈顶元素BinTNode * getTop_S2(BinTNode** stack){return stack[top_S2];}//非递归遍历 - 左右根void PostOrderTraverse(BinTNode * Tree) {BinTNode * S1[30]; // 辅助栈BinTNode * S2[30];BinTNode * T = Tree; // 定义临时指针BinTNode * Temp;push_S1(S1, T); // 初始化S1的top元素是树的根结点while(top_S1 != -1) {T = getTop_S1(S1); // S1的栈顶元素弹出pop_S1(); // 栈顶元素弹栈push_S2(S2, T);if(T->left != NULL || T->right != NULL) { // 栈顶元素有孩子结点if(T->left != NULL)push_S1(S1, T->left);if(T->right != NULL)push_S1(S1, T->right);}}// 逐个弹出S2的元素while(top_S2 != -1) {printElement(getTop_S2(S2));pop_S2();}}int main() {BinTNode * Tree;Tree = CreateBiTree(Tree);printf("看到这样就对了: H I D E B F G C A\n");printf("后序遍历:\t");PostOrderTraverse(Tree);printf("\n");return 0;}
运行结果
看到这样就对了: H D I B E A F C G中序遍历: H D I B E A F C G
后续会将更多的数据结构用C语言代码实现，欢迎大家关注!
图片：凡科快图