202637.cpp

数据结构（清华版）

#include<iostream.h>
#include <malloc.h>
typedef char TElemtype ;

//创建二叉树结构体=====================================================================
typedef struct BiTNode
{
	TElemtype data;
	BiTNode *lchild,*rchild,*parent;
} *BiTree;
typedef BiTree SElemtype ;
//先序序列创建二叉数=====================================================================
void CreateBiTree(BiTree &T,char s[],int &i)
{
	i++;
	if(s[i]=='#') T=NULL;
	else
	{
		T=new BiTNode;
		T->data=s[i];
		CreateBiTree(T->lchild,s,i);
		CreateBiTree(T->rchild,s,i);
	}
}
//用于调用的创建二叉树函数==============================================================
void CreateBiTree(BiTree &T,char s[])
{
	int i=-1;
	CreateBiTree(T,s,i);
}
//建立顺序栈===========================================================================
struct SStack
{
	SElemtype *top,*base;
	int Stacksize;
};
//判断栈是否为空=======================================================================
bool StackEmpty(SStack S)
{
	return S.top==S.base;
	
}
//出栈
bool Pop(SStack &S,SElemtype &e)
{
	if(S.top==S.base) return false;
	S.top--;
	e=*S.top ;
	return true;
}
//构建栈函数=================================================================
bool StackInit(SStack &S)
{
	S.base=new SElemtype[100];
	if(!S.base) return false;
	S.top=S.base;
	S.Stacksize=100;
	return true;
}
//入栈=========================================================================
bool Push(SStack &S,SElemtype e)
{
	SElemtype *newbase ;
	if(S.top-S.base==S.Stacksize)
	{
		newbase=(SElemtype*)realloc(S.base,(S.Stacksize+10)*sizeof(SElemtype));
		if(!newbase)return false;
		S.base=newbase;
		S.top=S.base+S.Stacksize;
		S.Stacksize+=10;
	}
	*(S.top)=e;
	S.top++;
}
void visit(TElemtype e)
{
	cout<<e<<"  ";
}
//先序遍历二叉树================================================================
void preorder(BiTree T,void visit(TElemtype))
{
	SStack S;
	StackInit(S);
	if(!T) return;
	Push(S,T);
	while(!StackEmpty(S))   
	{	
		if(T)
		{
			visit(T->data);      
			Push(S,T->rchild);    
		    T=T->lchild;        
		}
		else Pop(S,T);    
	}
	
}
//主函数=========================================================================
void main()
{
	BiTree T;
    TElemtype A[]={'a','s','d','#','#','#','c','t','#','m','#','#','#'};
	CreateBiTree(T,A);
	preorder(T, visit);
	
}