二叉树后序遍历(非递归)算法实现--C语言

左手的ㄟ右手 2022-04-08 14:25 192阅读 0赞

一直说要写二叉树的后序非递归遍历算法，但是前两天各种事情，今天终于有时间好好写一写二叉树的后序遍历算法。  
  二叉树的后序遍历算法比先序和中序的遍历算法要复杂一些。其出栈条件有两种情况：

1.  栈顶元素所指向的节点的左子树和右子树均为空；
2.  栈顶元素所指向的节点的左子树和右子树均被访问过。

第一种情况比较好判断，但是对于第二种情况就比较麻烦一点。要先判断其左子树和右子树是否分别被访问过。  
  对于第二种情况，多加一个指针指向上一次循环访问过的节点(如果栈顶元素指向节点的左子树或右子树的值与该指针的值相等，则说明该栈顶元素可以出栈)，并且进栈顺序是先进右子树，再进左子树，这样当右子树被访问过时，其左子树一定已经被访问过了。

代码如下：

#include "stdafx.h"
    #include <stdlib.h>
    #include <stdio.h>
    #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;
    }

建立的二叉树的形状为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_16_color_FFFFFF_t_70]

测试结果如下图所示：  
![在这里插入图片描述][20181218161355177.png]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_16_color_FFFFFF_t_70]: /images/20220404/83560596969747b489f864bb8a40ea2c.png
[20181218161355177.png]: /images/20220404/a602b4dfda5a42fa9142168b06b7d431.png