C# · 12月 20, 2021

二叉树后序遍历(非递归)算法实现–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;

}

建立的二叉树的形状为:

测试结果如下图所示:

写完这个后序遍历,我发现自己的坏习惯还真的是很难改正,依然很粗心,这一点代码占用了自己将近一天的时间,就是卡在了中间的那个循环那里,导致出现死循环。总是审题不严,急躁,这一点我会慢慢改正,及时时间不够,但是写出来的要保证是对的,否则还不如不写。