首先非常感谢‘hicjiajia’的博文:二叉树后序遍历(非递归)
这篇随笔开启我的博客进程,成为万千程序员中的一员,坚持走到更远!
折磨了我一下午的后序遍历中午得到解决,关键在于标记右子树是否被访问过,考虑过修改二叉树结点的数据结构,增加一个visit域,或者建一个栈存储已访问的结点。都比较麻烦没有调试成功。若将右子树也入栈,如果没有访问标记的话,会改变访问的次序,甚至出现死循环,这是比较危险的情况。从借鉴的博文里,摘录并改写为C的代码,基本上没有改动。后续问题努力写出自己的原创代码。
二叉树存储的数据类型为int型,用数字0表示子树为空
输入:1 2 3 0 8 0 0 4 0 0 5 6 0 0 7 0 0
得到后序遍历结果:83426751
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define MaxSize 100 typedef int ElemType; typedef int Status; typedef struct BTNode{ ElemType data; struct BTNode *lchild,*rchild; }BTree; typedef struct St{ struct BTNode* data[MaxSize]; int top; }Stack; //1.按先序次序生成二叉树 BTree* CreateT(){ BTree *BT; ElemType ch; scanf("%d",&ch); ) BT=NULL; else{ BT=(BTree*)malloc(sizeof(BTree)); if(!BT){exit(OVERFLOW);} BT->data=ch; BT->lchild=CreateT(); BT->rchild=CreateT(); } return BT; } //4.后序遍历 Status PostOrder(BTree *BT) { if(BT){ PostOrder(BT->lchild); PostOrder(BT->rchild); printf("%3d",BT->data); return OK; } else return ERROR; } //4.后序遍历-非递归 Status PostOrder2(BTree *BT) { Stack s,s2; BTree *T; int flag[MaxSize]; s.top=; T=BT; ||T){ while(T) { s.data[s.top++]=T; flag[s.top-]=; T=T->lchild; } &&flag[s.top-]==){ T=s.data[--s.top]; printf("%3d",T->data); } ){ flag[s.top-]=; T=s.data[s.top-]; T=T->rchild; } else break; } return OK; } int main(){ BTree *BT; BT=CreateT(); if(PostOrder(BT)){ printf("\n后序遍历完成!\n"); } if(PostOrder2(BT)){ printf("\n非递归后序遍历完成!\n"); } }
//-------------------------华丽的分割线-------------------------------------
下面是我自己写的后序遍历程序
//非递归后序遍历-test void PostOrder3(BTree *T){ BTree *p=T;Stack s;s.top=-; int tag[MaxSize]; ){ if(p){ s.data[++s.top]=p; tag[s.top]=; p=p->lchild; } else{ ){ p=s.data[s.top--]; printf("%d",p->data); } p=s.data[s.top]; p=p->rchild; tag[s.top]=; } ) break; } }