btree_postorder_norecursion_traverse.cpp

二叉树的各种操作

/*=================================================*/
/*程序名称：BTree_Inorder_NoRecursion_Traverse.cpp */
/*程序目的：函数实现                               */
/*Written by :Wang Qiang.                          */
/*=================================================*/
#include "BTree_Postorder_NoRecursion_Traverse.h"
#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 100
#define STACKINCREMENT 10


/*--------------------------------------------*/
/*使用递归方式建立二叉树                      */
/*--------------------------------------------*/

b_tree create_btree(int *nodelist, int position)
{
	b_tree newnode;

	if (nodelist[position] == 0 || position > 15) //递归终止条件
		return NULL;
	else
	{
		newnode=(b_tree) malloc (sizeof(treenode));
		newnode->data=nodelist[position];
		newnode->left=create_btree(nodelist,2*position);
		newnode->right=create_btree(nodelist,2*position+1);
		return newnode;
	}
}

/*--------------------------------------------*/
/*二叉树中序遍历打印节点的内容                */
/*--------------------------------------------*/
void inorder_print_btree(b_tree point)
{
	if ( point!=NULL)
	{
		inorder_print_btree(point->left);
		printf("【%2d】",point->data);
		inorder_print_btree(point->right);
	}
}

/*--------------------------------------------------------*/
/*初始化栈                                                */
/*--------------------------------------------------------*/
void InitStack(TrStack &S)
{
	S.base=(b_tree *)malloc(INIT_SIZE*(sizeof(b_tree)));
	if(!S.base)
		printf("栈分配失败\n");
	S.top=S.base;
	S.stacksize=INIT_SIZE;
}

/*--------------------------------------------------------*/
/*               判断栈是否为空                           */
/*--------------------------------------------------------*/
int StackEmpty(TrStack S) 
{
	if(S.top==S.base)
		return 1;
	else 
		return 0;
}

/*--------------------------------------------------------*/
/*       取栈顶元素                                       */
/*--------------------------------------------------------*/
b_tree GetTop(TrStack S,b_tree &p)
{
	if(!StackEmpty(S))
	{
		p=*(S.top-1);
		return p;
	}
	else
		return NULL;
}

/*--------------------------------------------------------*/
/*压栈                                                    */
/*--------------------------------------------------------*/
void Push(TrStack &S,b_tree node)
{
	if((S.top-S.base)>=S.stacksize)
	{
		S.base=(b_tree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(b_tree));
		if(!S.base)
			printf("重新分配失败\n");
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=node;
	//if (node!=NULL)
		//printf("成功入栈:%d\n",node->data);
	//else
		//printf("空节点入栈\n");
}

/*--------------------------------------------------------*/
/*出栈                                                    */
/*--------------------------------------------------------*/
int Pop(TrStack &S,b_tree &p)
{
	if(S.top==S.base)
		return 0;
	p=*(--S.top);
	    return 1;
}

/*--------------------------------------------------------*/
/*              后序非递归遍历二叉树                      */
/*--------------------------------------------------------*/
void PostorderTraverse(b_tree T)
{
	TrStack S;
	InitStack(S);
	b_tree p=T;
	b_tree tag;

	while(p || !StackEmpty(S))
	{
		if (p)
		{
			Push(S,NULL);
			Push(S,p);
			p=p->left;
		}
		else
		{
			Pop(S,p);
			Pop(S,tag);

			if(tag==NULL)
			{
				Push(S,p);
				Push(S,p);
				p=p->right;
			}
			else
			{
				printf("%d",p->data);
				p=NULL;
			}
		}
	}
	
}