用栈实现二叉树的遍历(非递归)
先实现栈
#include <stdio.h>
#include <stdlib.h>#include <string.h>
typedef char ElemType;
#define STACKSIZE 20
typedef struct st
{
ElemType *data;
int top;
int MaxSize;
}stack;
void Init_stack(stack *p);//初始化栈
bool Is_Empty(stack *p);//判断是否为空栈
bool Is_Full(stack *p);//判断栈是否为满栈
int GetLength(stack *p);//获取栈内元素个数
bool push(stack *p, ElemType value);//入栈
ElemType top(stack *p);//弹出栈顶元素
ElemType pop(stack *p);//出栈
void show_stack(stack *p);//展示栈内元素
void Init_stack(stack *p)
{
if (p == NULL)
return;
p->top = -1;
p->MaxSize = STACKSIZE;
p->data = (ElemType *)malloc(sizeof(ElemType)*p->MaxSize);
memset(p->data, 0, sizeof(ElemType)*p->MaxSize);
}
bool Is_Empty(stack *p)
{
if (p->top = -1 || p == NULL)
{
return true;
}
return false;
}
bool Is_Full(stack *p)
{
if (p->top + 1 == p->MaxSize || p == NULL)
{
return true;
}
return false;
}
int GetLength(stack *p)
{
return p->top+1;
}
bool push(stack *p, ElemType value)
{
bool res = false;
if (!Is_Full(p))
{
p->data[++p->top] = value;
res = true;
}
return res;
}
//出栈操作分为两步,是为了保证出栈精确
ElemType top(stack *p)
{
if ( p != NULL )
{
return p->data[p->top];}
}
ElemType pop(stack *p)
{
if (p->top >= 0 && p != NULL)
{
p->top--;
}
}
void show_stack(stack *p)
{
int count = p->top;
while (count != -1)
{
printf("%c ", p->data[count]);
count--;
}
}
假设二叉树的结构为:
则其前序遍历为:ABCDEFGH. 中序遍历为:CBEDFAGH . 后序遍历为:CEFDBHGA
用栈实现中序遍历的思想:让二叉树左-中-右遍历,若不为空则入栈,若为空出栈
过程如下所示:
将其转化为代码,如下:
void NiceInOrder ( BtNode *ptr )
{
if ( NULL == ptr ) return ;
stack st;
Init_Stack ( &st ) ;
while ( ptr !=NULL || ! Is_empty ( &st ) )
{
while ( ptr !=NULL )
{
push ( & st , ptr -> data ) ;
ptr = ptr -> LiftChild ;
}
ptr = top ( &st ) ; pop( &st ) ; // 遇到空直接出栈
printf ( " %c ", ptr -> data ) ;
ptr = ptr -> RightChild ;
}
}
后序遍历思想为:每个节点都要进栈两次,第二次退栈是才访问节点。第一次进栈时,在遍历左子树的过程中将根节点进栈,待左子树访问完后,回溯的节点退栈,即退出这个根节点,但不能立即访问,只能借助于这个根去找该根的右子树,并遍历这棵右子树,直到该右子树全部遍历以后,再退出该根节点,并访问它。所以,为了记录节点是第一次还是第二次进栈,需单独定义一个节点作为标志。
代码如下:
void NicePastOrder ( BtNode *ptr )
{
if ( NULL == ptr ) return ;
stack st;
Init_Stack ( &st ) ;
BtNode *tag=NULL;
while ( ptr !=NULL || ! Is_empty ( &st ) )
{
while ( ptr !=NULL )
{
push ( & st , ptr -> data ) ;
ptr = ptr -> LiftChild ;
}
ptr = top ( &st ) ; pop( &st ) ; // 遇到空直接出栈
if ( ptr -> RightChild == NULL || ptr -> RightChild == tag )
{
printf ( "%c", ptr -> data ) ;
tag = ptr ;
ptr = NULL ;
}
else
{
push ( &st, ptr ) ;
ptr = ptr -> RightChild ;
}
}
}
前序遍历的思想:若栈不为空且ptr不为空时入栈即出栈并打印,然后将其右孩子入栈,再继续访问其左孩子;若ptr为空,则出栈。
代码如下:
void NicePerOrder ( BtNode *ptr )
{
if ( ptr == NULL ) return ;
stack st ;
Init_Stack ( &st ) ;
while ( ptr !=NULL || ! Is_Empty ( &st ) )
{
if ( ptr )
{
push ( &st , ptr ) ;
ptr = top ( &st ) ; pop ( &st ) ;
printf ( "%c " , ptr -> data ) ;
push ( &st , ptr -> RightChild ) ;
ptr = ptr -> LeftChild ;
}else
{
ptr = top ( &st ) ; pop ( &st ) ;
}
}
}