binarytree.cpp

数据结构二叉树实验

//////////////////////////////////////////////////////////////////////

#include "BinaryTree.h"
#include <iostream.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////



BinaryTree::BinaryTree()
{ root = 0;

}

BinaryTree::~BinaryTree()
{   

}
 
//*****************************************删除整个二叉树****************************************
void BinaryTree::Delete(BinaryTreeNode *t){

	if(t->LeftChild || t->RightChild)
	{	Delete(t->LeftChild);
	    Delete(t->RightChild);

		delete t;
	}
	delete t;
}


//*****************************************前序遍历输出******************************************
void BinaryTree::PreOrder(BinaryTreeNode *s) const{
    
	if(s!=0){
	    cout<<s->data<<"  ";
		PreOrder(s->LeftChild);
		PreOrder(s->RightChild);
	}

}

//*****************************************中序遍历输出******************************************
void BinaryTree::InOrder(BinaryTreeNode *s) const{
   
	if(s!=0){
		InOrder(s->LeftChild);
		cout<<s->data<<"  ";
		InOrder(s->RightChild);
	}

}
//*****************************************后序遍历输出******************************************
void BinaryTree::PostOrder(BinaryTreeNode *s) const{
    
	if(s!=0){
		PostOrder(s->LeftChild);
		PostOrder(s->RightChild);
		cout<<s->data<<"  ";
	}

}

//****************************************逐层遍历输出*******************************************
void BinaryTree::LevelOrder(BinaryTreeNode *s) const{
    LinkedQueue Q;

	while(s){
	
	    cout<<s->data<<"  ";
		
		if(s->LeftChild!=NULL)  Q.Add(s->LeftChild);  //往队列中添加，加在队列中最后面
	
		if(s->RightChild!=NULL)  Q.Add(s->RightChild);
	
		if(Q.IsEmpty())
			return;
		else {
		    s = Q.Delete();  //从队列中删除第一个节点，并返回其数据域

		}
			
	}

}



//*************************************前序依次输入**********************************************
BinaryTreeNode* BinaryTree::PreOrderInput(){
    int a;
	cout<<"Enter the element of this piont & enter -1 to end"<<endl;
	cin>>a;
    BinaryTreeNode *s;
	if(a!=-1){
	     s = new BinaryTreeNode;
	}else 
		return 0;

	cout<<"Enter the data"<<endl;
	s->data = a;
	
	cout<<"Enetr LeftChild："<<endl;
	s->LeftChild = PreOrderInput();
    
	cout<<"Enetr RightChild："<<endl;
    s->RightChild = PreOrderInput();

	return s;
	

}

//*******************************************高度计算*********************************************
int BinaryTree::Height(BinaryTreeNode *s) const{
    if(s == 0) return 0;

	int hLeftChild = Height(s->LeftChild);  //左子树高度
	int hRightChild = Height(s->RightChild); //右子树高度

	if(hLeftChild > hRightChild) return ++hLeftChild;
	else return ++hRightChild;

}

//****************************************节点数计算************************************************
int BinaryTree::NumberOfNode(BinaryTreeNode *s) const{
	int count = 0;
   if(s==0) return count;
   
   int left = NumberOfNode(s->LeftChild); //递归计算左右子树的节点数
   int right = NumberOfNode(s->RightChild);

   count +=left;
   count += right;
   
   return ++count;

}

//**********************************添加一个元素************************************************
LinkedQueue& LinkedQueue::Add(BinaryTreeNode *t){

	Node *p = new Node;
	p->element = t;
	p->link =0;

	if(front!=0) last->link = p;  //队列不为空
	else {front = p; } //队列为空
	last = p;

	return *this;

}

//***************************删除队列的第一个节点，并保存到t*************************************
BinaryTreeNode* LinkedQueue::Delete(){


	if(IsEmpty())
	{   cout<<"The Queue is empty"<<endl;
		return 0;
	}
	BinaryTreeNode *temp = front->element;
	Node *p = front;
	front = front->link;

	delete p; //从队列中删除

	return temp;

	

}


//****************************输入二叉树的前序序列和中序序列，然后创建二叉树*********************

BinaryTreeNode* BinaryTree::MakeTree( int *pre, int *in,  int length){
   BinaryTreeNode *root = new BinaryTreeNode;

   int numberOfLeft = 0; //代表左树节点个数
   if(length!=0){
          root->data = pre[0];  //根节点赋值
		  if(length!=1){
		       for(numberOfLeft = 0; in[numberOfLeft]!=root->data; numberOfLeft++);  //在中序中寻找前序中确定的根节点

			   if(length>1) root->LeftChild = MakeTree(pre+1, in,numberOfLeft);    //如果length>1说明有左子树，然后创建其左子树，注意参数传递中指针的变化
               if(length>2) root->RightChild = MakeTree(pre+numberOfLeft+1, 
				   in+numberOfLeft+1, length-1-numberOfLeft);  //如果length>2说明有右子树，然后创建右子树
		  }

	   
   }
   return root;
}


void main(){
	
    BinaryTree t1;
	cout<<"*****Enter the tree by PreOrder*****："<<endl;
	t1.root = t1.PreOrderInput();
	cout<<endl;

	cout<<"*****the PreOrderof the tree is*****："<<endl;
    t1.PreOrder(t1.Root());
	cout<<endl;
	cout<<"*****the InOrder the tree is*****："<<endl;
	t1.InOrder(t1.Root());
	cout<<endl;
	cout<<"*****the PostOrder the tree is*****："<<endl;
	t1.PostOrder(t1.Root());
	cout<<endl;
	cout<<"*****the LevelOrder the tree is*****："<<endl;
	t1.LevelOrder(t1.Root());
	cout<<endl;

	cout<<"*****Number Of the Node is *****"<<endl;
	cout<<t1.NumberOfNode(t1.Root())<<endl;

    cout<<"*****Height is*****"<<endl;
	cout<<t1.Height(t1.Root())<<endl;

    
//***********************************前序和中序序列确定树*****************************************

	cout<<"PreOrder and InOrder to make a tree"<<endl;
	int length;
	cout<<"Enter the point number of the tree："<<endl;
	cin>>length;

	int *pre = new int[length];
	int *in  = new int[length];
    int *post = new int[length];

	cout<<"***Enter the tree by PreOrder:"<<endl;
	int count1=1;
	for(int i=1; i<=length; i++){
	   cout<<"***enter tne "<<count1<<"element：   ";
	   cin>>pre[i-1];
	   count1++;
	}

	cout<<"***Enter the tree by PreOrder："<<endl;
	int count2=1;
	for(int j=1; j<=length; j++){
		cout<<"***Enter the "<<count2<<"element：   ";
		cin>>in[j-1];
		count2++;
	}


	BinaryTree t2;
	t2.root = t2.MakeTree(pre,in,length);
	cout<<"***Enter the tree of PreOrder："<<endl;
	t2.PreOrder(t2.Root());
	cout<<endl;
	cout<<"***Enter the tree by InOrder："<<endl;
	t2.InOrder(t2.Root());
	cout<<endl;
	cout<<"***Enter the tree by PostOrder："<<endl;
	t2.PostOrder(t2.Root());
	cout<<endl;

	

}