6 inorder_traversebitree_feidigui.cpp

数据结构的必做编程题

#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>	
#define NULL 0
#define OVERFLOW 0
#define STACKSIZE 50
#define ADD	20		

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;		
}*BiTree;		

typedef struct stack
{
	BiTree *base;
	BiTree *top;
	int stacksize;		//规定堆栈的大小
}stack;


void CreateBiTree(BiTree &T)	//先序扩展序列建立二叉树的递归算法 
{  
	char ch;
	scanf("%c",&ch);
	if (ch=='*') 
	{
		T=NULL;		
	}
	else 
	{ 
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
		{
			exit(OVERFLOW);
		}
		T->data=ch;
		CreateBiTree(T->lchild); 
		CreateBiTree(T->rchild); 
	}  
} 




stack* CreateStack()	//构造一个空栈
{
	stack *s=(stack*)malloc(sizeof(stack));
	if(!s)	exit(OVERFLOW);
	
	s->base=(BiTree*)malloc(STACKSIZE*sizeof(BiTree));
	if(!s->base) exit (OVERFLOW);
	
	s->top=s->base;
	s->stacksize=STACKSIZE;
	return s;
}


void push(stack *s, BiTree i)			//压栈
{
	if(s->top-s->base>=s->stacksize)	//栈满，追加存储空间
	{
		s->base = (BiTree*)realloc(s->base,(s->stacksize+ADD)*sizeof(BiTree));
		if(!s->base)	exit(OVERFLOW);			
		s->top=s->base+s->stacksize;
		s->stacksize=s->stacksize+ADD;
	}
	*(s->top)=i;
	(s->top)++;
}


BiTree pop(stack *s)	//出栈
{
	BiTree i;
	if(s->top==s->base)
	{
		return 0;
	}
	else
	{
		i=*(--s->top);
		return i;
	}
}


BiTree GoLeft(BiTree T, stack *S)	//向左下搜索
{				
	if (!T)
	{
		return 0;
	}
	while (T->lchild)		
	{  
		push(S, T);			//把T压栈
		T=T->lchild;		//往左下方走一步
	}
	return T;
}


void main()	//中序遍历的非递归算法的主程序
{										
	BiTree t;
	printf("请按先序扩展序列输入二叉树,空用*表示\n");
	CreateBiTree(t);
	stack *S;
	printf("中序遍历的非递归算法");
	S=CreateStack();
	t=GoLeft(t, S);		// 找到最左下的结点
	while(t)							
	{ 
		printf("%c",t->data);	// 访问结点
		if (t->rchild)	//如果右子树非空，则走到右子树的最左端
		{
			t = GoLeft(t->rchild, S);
		}
		else if (!(S->top==S->base))//右子树为空时，弹出双亲节点		
			{
				t = pop(S);		
			}
			else
			{
				t = 0;		// 栈空则结束遍历
			}
	} 
	printf("\n");
}