读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw
二叉树后序遍历 二叉树的遍历方式主要由先序遍历、中序遍历和后续遍历,还后就是层次遍历
感受完前两篇的遍历方式,本节来看看后序遍历
后序遍历过程 a. 先序遍历其左子树 ;
b. 先序遍历其右子树 ;
c. 访问根节点 ;
然后就是一直递归下去,在访问到节点的时候,可以进行节点的相关处理,比如说简单的访问节点值
下图是一棵二叉树,我们来手动模拟一下后序遍历过程
按照上述后序遍历的过程,得到后序遍历序列:
递归实现 二叉树的后序遍历利用上述的递归思想进行C语言代码实现:
树形结构按照上述树形结构进行初始化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 # 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 ; }
运行结果:
非递归实现 相比于之前的先序遍历和中序遍历非递归实现,后序遍历的非递归算法与之前有所不同,后续遍历需要先访问左右子结点后,才能访问该结点,而这也是非递归的难点所在。
考虑了几种实现的方案,这里我给出我认为比较清晰的一个方案供大家参考:借助两个栈(S1和S2)来进行操作
看下面伪代码:
1 2 3 4 5 6 7 8 初始化S1的top元素是树的根结点; while (top1 != -1 ) { 将栈顶元素push到S2; if (栈顶元素有孩子结点){ 按照孩子结点的左右顺序push进S1; } } 循环逐个弹出S2的栈顶元素
伪代码可能看了之后有些不太好懂,但是还算看着清晰吧,下面借助图,一定会思路清晰的(长图发放):
有了这个思路就应该会很清晰了,下面按照上述思路用C语言实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 #include <stdio.h> #include <string.h> #include <stdlib.h> #define ElementType char int top_S1 = -1 ; int top_S2 = -1 ; 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 push_S1 (BinTNode** stack ,BinTNode * elem) { stack [++top_S1] = elem; } void push_S2 (BinTNode** stack ,BinTNode * elem) { stack [++top_S2] = elem; } void pop_S1 () { if (top_S1 == -1 ) { return ; } top_S1--; } void 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); while (top_S1 != -1 ) { T = getTop_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); } } 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 ; }
运行结果
1 2 看到这样就对了: H D I B E A F C G 中序遍历: H D I B E A F C G
最后 在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取 有任何问题,欢迎随时交流!!!