二叉树.cpp

杭州电子科技大学ACM题

#include<iostream>
#include<stdlib.h>
#include<malloc.h>
#define null 0
using namespace std;

typedef struct BitNode
{
	char data;
    struct BitNode *lchild,*rchild;
}BitNode,*BitTree;

typedef struct node
{
    BitTree data1[100];
	int  top;
}SqStack;

SqStack s;

void  InitStack(SqStack &s)
{
	s.top=0;  
}

bool GetTop(SqStack &s)
{
	if(s.top==0) return null;
	else return 1;

}

void Push(BitTree e)
{
	s.data1[s.top++]=e;
}

BitTree  PoP()
{
	BitTree  e;
	e=s.data1[--s.top];
	return e;
}


BitTree createtree(BitTree root)
{
	char ch;
	cin>>ch;
	if (ch=='0') 
	{ root=null;} 
	else 
	{
		root=(BitTree)malloc(sizeof(BitNode));
		root->data=ch;
		root->lchild=createtree(root->lchild);
		root->rchild=createtree(root->rchild);
	}
	return root;
}

void travel(BitTree root)
{
	if(root!=null)
	{
		travel(root->lchild);
		cout<<root->data<<"  ";
		travel(root->rchild);
	}
}

void travel1(BitTree root)
{
	BitTree p=root;
	Push(p);
	while(GetTop(s)!=null)
	{
		while(p->lchild!=null)
		{
			Push(p->lchild);
			p=p->lchild;
		}
		if(GetTop(s)!=null)
		{	
			p=PoP();
			cout<<p->data<<"  ";
			if(p->rchild!=null)
		    {
			   Push(p->rchild);
			   p=p->rchild;
		    }
		}	

	}
	cout<<endl;
}

int main()
{
    BitTree root=null;
	root=createtree(root);
    travel(root);
	cout<<endl;
    travel1(root);
	return 0;
}