二叉树后序遍历(非递归)算法实现--C语言
|
??一直说要写二叉树的后序非递归遍历算法，但是前两天各种事情，今天终于有时间好好写一写二叉树的后序遍历算法。 ??二叉树的后序遍历算法比先序和中序的遍历算法要复杂一些。其出栈条件有两种情况： 栈顶元素所指向的节点的左子树和右子树均为空； 栈顶元素所指向的节点的左子树和右子树均被访问过。 ??第一种情况比较好判断，但是对于第二种情况就比较麻烦一点。要先判断其左子树和右子树是否分别被访问过。 ??对于第二种情况，多加一个指针指向上一次循环访问过的节点(如果栈顶元素指向节点的左子树或右子树的值与该指针的值相等，则说明该栈顶元素可以出栈)，并且进栈顺序是先进右子树，再进左子树，这样当右子树被访问过时，其左子树一定已经被访问过了。 代码如下： #include "stdafx.h" #include #include #define STACKINITSIZE 20//栈初始空间大小 #define INCREASEMENT 10//栈空间大小的增量 typedef struct BiTNode { char data;//二叉树节点数据 BiTNode *lchild,*rchild;//指向二叉树左子树和右子树的指针 }BiTNode,*BiTree;//定义二叉树节点结构 typedef struct SqStack { BiTNode *base;//栈底指针 BiTNode *top;//栈顶指针 int stacksize;//顺序栈空间大小 }SqStack;//定义顺序栈结构 //建立一个空栈，建立成功，返回1，失败，返回0 int InitStack(SqStack &S) { S.base = (BiTNode*)malloc(STACKINITSIZE * sizeof(BiTNode));//20为栈的大小，可以更改 if(!S.base) return 0; S.top = S.base; S.stacksize = STACKINITSIZE; return 1; } //进栈操作 int Push(SqStack &S,BiTNode e) { if(S.top - S.base >= S.stacksize) { S.base = (BiTNode*)realloc(S.base,(STACKINITSIZE + INCREASEMENT) * sizeof(BiTNode)); if(!S.base) return 0; S.stacksize = 30; } *S.top = e; S.top ++; return 1; } //获取栈顶元素 int GetTop(SqStack S,BiTNode &e) { if(S.base == S.top) return 0; e = *(S.top - 1); return 1; } //出栈操作，若栈为空，则返回0；栈不为空，则返回1 int Pop(SqStack &S,BiTNode &e) { if(S.base == S.top) return 0; S.top --; e = *S.top; return 1; } //判断栈是否为空，若栈为空，则返回true，栈不为空，则返回false bool StackEmpty(SqStack S) { if(S.base == S.top) return true; else return false; } //建立二叉树 void CreateBiTree(BiTree &T) { char ch; scanf("%c",&ch); if(ch == '#') T = NULL; else { T = (BiTNode *)malloc(sizeof(BiTNode)); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } //比较两个节点的值是否相等 bool Equal(BiTNode *e1,BiTNode *e2) { if(NULL == e1 || NULL == e2) return false; if(e1->data == e2->data && e1->lchild == e2->lchild && e1->rchild == e2->rchild) return true; else return false; } //后序遍历二叉树 int PostOrderTraverse(BiTree T) { if(!T) return 0; SqStack S; int n = InitStack(S);//建立空栈 if(!n) return 0; BiTree p = T; BiTree pre = NULL; BiTNode e,cur;//二叉树节点，用于存放从栈中取出的节点 Push(S,*p); while(!StackEmpty(S)) { GetTop(S,e);// if((NULL == e.lchild && NULL == e.rchild) || (NULL != pre && (Equal(pre,e.lchild) || Equal(pre,e.rchild)))) { /*这里之前出现过错误，造成死循环。当时写的是 Pop(S,e); printf("%c ",e.data); pre = &e; 由于pre = 对e取地址，则当前面GetTop(S,e)时，pre的值也改变了，之前保存的内容没有了，if条件永远不会为真 */ Pop(S,cur); printf("%c ",cur.data); pre = &cur; } else { if(NULL != e.rchild) { Push(S,*e.rchild); } if(NULL != e.lchild) { Push(S,*e.lchild); } } } printf("n"); return 1; } int main(int argc,char* argv[]) { BiTree T = NULL; printf("请输入二叉树-按照先序序列建立二叉树n"); CreateBiTree(T); printf("后序遍历二叉树结果为：n"); PostOrderTraverse(T); return 0; } 建立的二叉树的形状为：
测试结果如下图所示：
写完这个后序遍历，我发现自己的坏习惯还真的是很难改正，依然很粗心，这一点代码占用了自己将近一天的时间，就是卡在了中间的那个循环那里，导致出现死循环。总是审题不严，急躁，这一点我会慢慢改正，及时时间不够，但是写出来的要保证是对的，否则还不如不写。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
