postorder.cpp

基于后序遍历的实现

#include <stdio.h>//后续遍历
typedef struct T{//定义二叉树节点
struct T *l;
struct T *r;
int value;
}TREE;

TREE *I(TREE *head,int q)//插入节点
{
TREE *p, *parent;
bool i;
TREE *newnode=new TREE;
p=NULL;
newnode->value=q;
newnode->l=NULL;
newnode->r=NULL;
if(!head)	return newnode;
p=head;
i=true;
while(p){
parent=p;
if(p->value>q)
	{
	p=p->l;
	i=true;
	}
else
	{
	p=p->r;
	i=false;
	}
}
if(i)
parent->l=newnode;
else
parent->r=newnode;
return head;
}

TREE *CREATE(TREE *head,int a[], int n)//建一棵二叉树
{
int i;
for(i=1;i<=n;i++)
   head=I(head,a[i]);
return head;
}

typedef struct NODE{//定义栈的元素
TREE *data;
NODE *next;
}NODE;

typedef struct STACK{//定义用来存放二叉树节点指针的栈
NODE *top;
int length;
}STACK;

void INI(STACK &stack){//栈的初始化
stack.top=NULL;
stack.length=0;
}

bool Empty(STACK &stack){//判断栈空函数
return(stack.length==0);
}

void PUSH(STACK &stack,TREE *p){//压栈函数
NODE *newnode=new NODE;
newnode->data=p;
newnode->next=stack.top;
stack.top=newnode;
stack.length++;
}

TREE *POP(STACK &stack){//弹栈函数
TREE *value;
NODE *p;
if(Empty(stack))	return NULL;
value=stack.top->data;
p=stack.top->next;
delete stack.top;
stack.top=p;
stack.length--;
return value;
}

int b[20];


void X(TREE *head, int n,STACK &stack)//按照根节点－>右节点－>左节点的顺序把各个节点值赋给栈b，经过弹栈输出后即为后续遍历
{
TREE *p=head;
int i=0;
while((p!=NULL)||!Empty(stack))
	{
	if(p!=NULL)
		{
		i++;
		b[i]=p->value;
	    PUSH(stack,p);	
		p=p->r;
		}
	else{
		p=POP(stack);
		p=p->l;
		}
	}
}

void main()
{
int i,n;
TREE *head=NULL;
STACK stack;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
INI(stack);
head=CREATE(head,b,n);
X(head,n,stack);
for(i=n;i>0;i--)
printf("%d ",b[i]);
return;
}