tree.cpp

利用二叉数对数据进行排序,体现二叉树的优点

#include<iostream.h>
#include<stdio.h>

class OTree
{

private:
	int data;
	OTree *Llink;
	OTree *Rlink;
public:
	OTree *root;
	OTree *p;
	OTree *q;
    OTree(){}
	OTree(int x)
	{
		root=new OTree;
		cout<<"Begin constructing........";
		root->data=x;
		root->Llink=NULL;
		root->Rlink=NULL;
		p=root;
	}
	void PreOrder(OTree *proot)
	{
		cout<<proot->data<<endl;
		if(proot->Llink!=NULL)
			PreOrder(proot->Llink);
		if(proot->Rlink!=NULL)
			PreOrder(proot->Rlink);
	}
	void PostOrder(OTree *proot)
	{
		if(proot->Llink!=NULL)
			PostOrder(proot->Llink);
		if(proot->Rlink!=NULL)
			PostOrder(proot->Rlink);
		cout<<proot->data<<endl;
	}
	void PutIn()
	{
		q=new OTree;
		int flag=1;
		q->Llink=NULL;
		q->Rlink=NULL;
		cout<<"Put in the number:"<<endl;
		cin>>q->data;
		cout<<"You have put in :"<<q->data<<endl;
		while(flag==1)
		{
			if((q->data<p->data)&&(p->Llink==NULL))
			{
    	    	p->Llink=q;
				flag=0;
			}
	    	else
				if((q->data<p->data)&&(p->Llink!=NULL))
			{
				p=p->Llink;
			}
		    else
				if((q->data>=p->data)&&(p->Rlink==NULL))
			{
     	    	p->Rlink=q;
				flag=0;
			}
			else
				if((q->data>=p->data)&&(p->Rlink!=NULL))
			{
				p=p->Rlink;
			}
			
		}
		flag=1;
		p=root;
	}
	void InOrder(OTree *proot)
	{
		if(proot->Llink!=NULL)
			InOrder(proot->Llink);
		cout<<proot->data<<endl;
		if(proot->Rlink!=NULL)
			InOrder(proot->Rlink);
	}
	void ReInOrder(OTree *proot)
	{
		if(proot->Rlink!=NULL)
			ReInOrder(proot->Rlink);
		cout<<proot->data<<endl;
		if(proot->Llink!=NULL)
			ReInOrder(proot->Llink);
	}
};
void main()
{
	char temp;
	OTree A(10);
	A.PreOrder(A.p);
	temp='y';
	while(temp=='y')
	{
		A.PutIn();
		cout<<"Do you want to go on?"<<endl;
	    cout<<"If yes please input y"<<endl;
		cout<<"if no please input any other key."<<endl;
	    cin>>temp;
		
	}
	cout<<"Now print the OTree in order: "<<endl;
	A.InOrder(A.p);
	cout<<"Now print the OTree in reversed order: "<<endl;
	A.ReInOrder(A.p);
	cout<<"construction is completed!"<<endl;
	

}