二叉树.cpp

实现数据结构中的单链表、二叉树、顺序表和排序查找源码

#include "iostream.h"
#include "stdio.h"
#include "malloc.h"
typedef enum PointerTag{Link,Thread};

class ThrBiTree
{
private:
	char	data;
	int		ltag,rtag;
	ThrBiTree *lchild,*rchild;

public:
	ThrBiTree()	{data=' ';ltag=Link;rtag=Link;lchild=NULL;rchild=NULL;}
	void	CreateBiTree(ThrBiTree* &t);	
	int		PreOrderTraverse(ThrBiTree* t,int(* Visit)(char e));
	int		InOrderTraverse(ThrBiTree* t,int(* Visit)(char e));
	int		PostOrderTraverse(ThrBiTree* t,int(* Visit)(char e));
	void	InOrderThreading(ThrBiTree* &thrt,ThrBiTree* t);	
	void	InThreading(ThrBiTree* t);
	void    InOrderTraverse_Thr(ThrBiTree *t,int(* Visit)(char e));
};
struct BiTree
{
	int data;
	BiTree *lchild,*rchild;
};


ThrBiTree* pre;

void ThrBiTree::CreateBiTree(ThrBiTree* &t)
{
	char ch;
	cin>>ch;
	if (ch=='#')
		t=NULL;
	else 
	{
		if (!(t=new (ThrBiTree)))
		{
			cout<<"over flow"<<endl;
			return;
		}
		t->data=ch;
		CreateBiTree(t->lchild);
		CreateBiTree(t->rchild);
	}
}

int PrintElement(char e)
{
	cout<<e<<" ";
	return 1;
}

int ThrBiTree::PreOrderTraverse(ThrBiTree* t,int(* Visit)(char e))
{
	if (t)
	{
		if(PrintElement(t->data))
			if(PreOrderTraverse(t->lchild,Visit))
				if(PreOrderTraverse(t->rchild,Visit))
					return 1;

		return 0;
	}
	return 1;

}

int	ThrBiTree::InOrderTraverse(ThrBiTree* t,int(* Visit)(char e))
{
	if (t)
	{
		if(InOrderTraverse(t->lchild,Visit))
			if(PrintElement(t->data))
				if(InOrderTraverse(t->rchild,Visit))
					return 1;
		return 0;
	}
	return 1;
}

int	ThrBiTree::PostOrderTraverse(ThrBiTree* t,int(* Visit)(char e))
{
	if (t)
	{
		if(PostOrderTraverse(t->lchild,Visit))
			if (PostOrderTraverse(t->rchild,Visit))
				if(PrintElement(t->data))
					return 1;
		return 0;
	}
	return 1;
}

void ThrBiTree::InOrderThreading(ThrBiTree* &thrt,ThrBiTree* t)
{
	if (!(thrt=new (ThrBiTree)))
	{
		cout<<"over flow"<<endl;
		return;
	}
	thrt->ltag=Link;thrt->rtag=Thread;
	thrt->rchild=thrt;
	if (!t)
		thrt->lchild=thrt;
	else
	{
		thrt->lchild=t;
		pre=thrt;
		InThreading(t);
		pre->rchild=thrt;	pre->rtag=Thread;
		thrt->rchild=pre;

	}
	
}

void ThrBiTree::InThreading(ThrBiTree* t)
{
	if(t)
	{
		InThreading(t->lchild);
		if(!t->lchild)
		{
			t->ltag=Thread;
			t->lchild=pre;
		}
		if(!pre->rchild)
		{ 
			pre->rtag=Thread;
			pre->rchild=t;
		}
		pre=t;
		InThreading(t->rchild);
	}	
}

void ThrBiTree::InOrderTraverse_Thr(ThrBiTree *t,int(* Visit)(char e))
{
   ThrBiTree *p;
   p=t->lchild; 
   while(p!=t)
   { 
     while(p->ltag==Link) 
       p=p->lchild;
     Visit(p->data); 
     while(p->rtag==Thread&&p->rchild!=t) 
     {
       p=p->rchild;
       Visit(p->data); 
     }
     p=p->rchild; 
   }              
   Visit(p->data);

}

int level(BiTree *bt,BiTree *p)
{
	int n=0;
	BiTree *t=bt;
	if(bt!=NULL)
	{
		n++;
		while(t->data!=p->data)
		{
			if(t->data<p->data)
				t=t->rchild;
			else
				t=t->lchild;
			n++;
		}
		return n;
	}
}

void insert(BiTree *&b,BiTree *s)
{
	if(b==NULL)
		b=s;
	else if(s->data==b->data)
		return;
	else if(s->data<b->data)
		insert(b->lchild,s);
	else if(s->data>b->data)
		insert(b->rchild,s);
}

void BST()
{
	BiTree *b=NULL;	
	cout<< "输入数字创建二叉排序树(输入0结束）:\n";
	int a;
	cin>>a;
	while(a)
	{
		BiTree *t=new BiTree;
		t->data=a;
		t->lchild=NULL;
		t->rchild=NULL;
		insert(b,t);
		cin>>a;
	}
	cout<<"输入要查找的数: ";
	BiTree *bt = new BiTree;
	cin>>bt->data;
	int n=level(b,bt);
	cout<<bt->data<<"所选的数字在第"<<n<<"层!"<<endl;
}

int Traverse(ThrBiTree* tree,int order)
{   cout<<"                  遍历                  \n";
	while (1)
{   
	cout<<endl;
	cout<<"1先序遍历  2中序遍历  3后序遍历  4退出\n请选择：";
	cin>>order;
			switch(order)
	{
	case 1:
		tree->PreOrderTraverse(tree,PrintElement);
		break;
	case 2:
		tree->InOrderTraverse(tree,PrintElement);
		break;
	case 3:
		tree->PostOrderTraverse(tree,PrintElement);
		break;
	case 4:
	
		return 4;
	default:
		break;
	}
	
}
}

int TreeMenu(int selt,int order)
{
	ThrBiTree* tree=NULL;
	ThrBiTree* thrBiTree=NULL;
	cout<<"\n          **********************二叉树**********************\n";
	cout<<"\n1.遍历二叉树\n2.二叉排序树\n0.退出\n请输入选项：";cin>>selt;
	switch(selt)
	{
	case 1:
		cout<<"建立二叉树!#表示空结点\n";
		tree->CreateBiTree(tree);
		Traverse(tree,order);
		cout<<endl;
		break;
	case 2:
		BST();
		break;
	default:
		break;
	}
	return selt;
}

void main()
{
	int order=1,selt=1,temp;
	while (temp!=0)
		temp=TreeMenu(selt,order);
	
}