cpp1.cpp

这是一个关于二叉树的运算程序,里面包有各种运算,大家可以看看.

#include<iostream.h>
//************建立二叉树*************
typedef  char   elemtype;
typedef struct BitTree
{
	elemtype  data;
	struct  BitTree  *lchild,*rchild;
}BitTree;
BitTree *CreatTree()
{
	BitTree  *q[100];         //定义q数组作为队列,用来存放结点,最大容量为100
	BitTree  *s;              //s为二叉链表中结点
	BitTree  *root;           //root为二叉链表中根结点
	int front=1,rear=0;       //定义队头,队尾指针
	char ch;                  //给出data
	root=NULL;
	cout<<"请依次输入二叉树结点中的数据,结点无时输入','符号,输入'#'符号表示结束"<<endl;
	cin>>ch;
	while(ch!='#')            //输入#时,结束
	{
		s=NULL;
		if(ch!=',')             //输入数据不为逗号,表示不为虚结点,否则为虚结点
		{
			s=new BitTree;
			s->data=ch;
			s->lchild=NULL;
			s->rchild=NULL;
		}
		rear++;
		q[rear]=s;                //新结点或虚结点进队列
    	if(rear==1)root=s;
		else
		{
			if((s!=NULL)&&(q[front]!=NULL))
			{
				if(rear%2==0)q[front]->lchild=s;
				else q[front]->rchild=s;
			}
			if(rear%2==1)front++;
		}
	cin>>ch;
	}
	return root;
}
//****************前序遍历**************
void PreOrder(BitTree *root)
{
	BitTree *p,*s[100];
	int top=0;
	p=root;
	while((p!=NULL)||(top>0))
	{
		while(p!=NULL)
		{
			cout<<p->data<<" ";
			s[++top]=p;
			p=p->lchild;
		}
		p=s[top--];
		p=p->rchild;
	}
}
//****************后序遍历**************
void PostOrder(BitTree *root)
{
	BitTree *p,*s1[100];
	int s2[100],top=0,b;
	p=root;
	do
	{
		while(p!=NULL)
		{
			s1[top]=p;s2[top++]=0;
			p=p->lchild;
		}
		if(top>0)
		{
			b=s2[--top];
			p=s1[top];
			if(b==0)
			{
				s1[top]=p;s2[top++]=1;
				p=p->rchild;
			}
			else
			{
				cout<<p->data<<" ";
				p=NULL;
			}
		}
	}while(top>0);
}
//****************主函数****************
void main()
{
	while(1)
	{
		BitTree *p;
	    p=CreatTree();
		cout<<"前序遍历结果为:";
		PreOrder(p);
		cout<<endl;
		cout<<"后序遍历结果为:";
		PostOrder(p);
		cout<<endl;
	}
}