源代码.txt

二叉树的实现

//程序名：main.cpp
//      程序功能：二叉树基本操作的实现
//          作者：黄秋旋
//          日期：2008.11.9
//          版本：1.0
//      修改内容：
//      修改日期：
//      修改作者：
//对应类实现文件: tree.h
//对应主程序文件: tree.cpp

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

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//主函数
//返回值：无

void main()
{
	TREE Tree1;                       //Tree1 object
	int first=1,choice;
    BTreeNode *bt=NULL;
	int finish=0;
	while(!finish)
	{   
		cout<<"********************MENU*******************************";
		cout<<"\n 1:Create a tree";
		cout<<"\n 2:Trave the tree with recursive algorithm of preamble";
        cout<<"\n 3:Trave the tree with nonrecursive algorithm of preamble";
		cout<<"\n 4:Trave the tree whith recursive algorithm of mid-rank method";
        cout<<"\n 5:Trave the tree whith noncursive algorithm of mid-rank method";
        cout<<"\n 6:Trave the tree whith recursive algorithm of surf-order";
        cout<<"\n 7:Trave the tree whith nonrecursive algorithm of surf-order"; 
        cout<<"\n 8:Trave the tree whith layerorder";
	    cout<<"\n 9:The altitude of the tree";
        cout<<"\n 10:The total number of the leaves";
        cout<<"\n 11:Print the tree: ";
		cout<<"\n 12:Exit";
        cout<<"\n Please inout the choice 1 to 12:  ";
		cin>>choice;
		switch(choice)
		{
		case 1:
			Tree1.Create(first);                               //创建二叉树
			cout<<"\n Please input the letters: ";
			first=1;
			cout<<endl;
			break;
		case 2:
			cout<<"The result of preorder: ";                 //调用前序递归遍历
			Tree1.Preorder(bt, first);
           	first=1;
			cout<<endl;
			break;
        case 3: 
        	cout<<"The result of preorder: ";                 //调用前序非递归遍历
            Tree1.Preorderf(bt);
			first=1;
			cout<<endl;
			break;
	   case 4:
	        cout<<"The result of inorder: ";                  //调用中序递归遍历
            Tree1.Inorder(bt, first);
            first=1;
			cout<<endl;
			break;
	   case 5:
            cout<<"The result of inorder: ";                  //调用中序非递归遍历
			Tree1.Inoderf(bt);
			first=1;
			cout<<endl;
			break;
	   case 6:
            cout<<"The result of postorder: ";                //调用后序递归遍历
			Tree1.Postorder(bt, first);
		    first=1;
			cout<<endl;
			break;
       case 7:
            cout<<"The result of postorder: ";                  //调用后序非递归遍历
			Tree1.Postorderf(bt);
            first=1;
			cout<<endl;
			break;
		case 8:
            cout<<"The result of layerorder: ";                  //调用层次遍历
			Tree1.Layerorder(bt);
			first=1;
			cout<<endl;
			break;
        case 9:
			cout<<"The altitude of the tree is: ";               //调用求树高函数
			cout<<Tree1.Altitude(bt, first);
		    cout<<endl;
			break;
		case 10:
			cout<<"The number of the leaves is: ";                //调用求子叶数函数
			cout<<Tree1.Number();
		    cout<<endl;
			break;
        case 11:
			Tree1.Print(bt,first);                                //调用输出二叉树函数
			cout<<endl;
			break;
		case 12:
			finish=1;                                             //结束程序
			break;
		}
	}
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//        程序名：tree.cpp
//      程序功能：二叉树类中成员函数的实现
//          作者：黄秋旋
//          日期：2008.11.9
//          版本：1.0
//      修改内容：
//      修改日期：
//      修改作者：
//  对应类头文件：tree.h
//对应主程序文件: main.cpp

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
#include"tree.h"

///////////////////////////////////////////////////////////////////////////////////////////////////////////
//建立二叉树函数
//函数功能：建立一棵二叉树
//函数参数：
//      first:1: 表示建立树根节点
//            0：表示建立分支节点或子节点
//参数返回值：p: 表示数的成功建立了节点

BTreeNode *TREE::Create(int first)
{
	char ch;
	BTreeNode *p;
	cin>>ch;
	if(ch=='.') p=NULL;
	else{
		p=new BTreeNode;
		p->data=ch;
		if(first)
		{
			head=p;
			first=0;
		}
		p->lchild=Create(first);
		p->rchild=Create(first);
	}
	return p;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//前序递归遍历函数
//函数功能：以根-左子树-右子树的顺序遍历二叉树
//函数参数：
//          bt：表示传入的节点指针
//          first：表示传入的节点是否为根节点
//参数返回值：无

void TREE::Preorder(BTreeNode *bt,int first)
{
	BTreeNode *p;
	if(first)
	{
		p=head;
		first=0;
	}
	else p=bt;
	if(p!=NULL)
	{
		cout<<p->data<<"\t";
		Preorder(p->lchild,first);
		Preorder(p->rchild,first);
	}
}


///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//前序非递归遍历
//函数功能：以根-左子树-右子树的顺序遍历二叉树
//函数参数：
//          bt：表示传入的节点指针         
//参数返回值：无

void TREE::Preorderf(BTreeNode *bt)
{
	BTreeNode *p;
	stack <BTreeNode *> s;
	p=head;
	s.push(p);
	while(!s.empty())
	{
		p=s.top();
		s.pop();
		cout<<p->data<<"\t";
		if(p->rchild!=NULL)
			s.push(p->rchild);
		if(p->lchild!=NULL)
			s.push(p->lchild);
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//中序递归遍历
//函数功能：以左子树-根-右子树的顺序遍历二叉树
//函数参数：
//          bt：表示传入的节点指针
//          first：表示传入的节点是否为根节点
//参数返回值：无

void TREE::Inorder(BTreeNode *bt,int first)
{
	BTreeNode *p;
	if(first)
	{
		p=head;
		first=0;
	}
	else p=bt;
	if(p!=NULL)
	{	
	    Inorder(p->lchild,first);
		cout<<p->data<<"\t";
		Inorder(p->rchild,first);
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//中序非递归遍历
//函数功能：以左子树-根-右子树的顺序遍历二叉树
//函数参数：
//          bt：表示传入的节点指针
//参数返回值：无

void TREE::Inoderf(BTreeNode *bt)
{
	BTreeNode *p;
	stack <BTreeNode *>s;
	p=head;
	while((!s.empty())||(p!=NULL))
	{
		while(p!=NULL)
		{
		s.push(p);
		p=p->lchild;
		}
		if(!s.empty())
		{
		p=s.top();
		s.pop();
		cout<<p->data<<"\t";
		p=p->rchild;
		}
	}
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//后序递归遍历
//函数功能：以左子树-右子树-根的顺序遍历二叉树
//函数参数：
//          bt：表示传入的节点指针
//          first：表示传入的节点是否为根节点
//参数返回值：无

void TREE::Postorder(BTreeNode *bt,int first)
{
	BTreeNode *p;
	if(first)
	{
		p=head;
		first=0;
	}
	else p=bt;
	if(p!=NULL)
	{	
		Postorder(p->lchild,first);
		Postorder(p->rchild,first);
		cout<<p->data<<"\t";
	}
}	
	
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//后序非递归遍历
//函数功能：以左子树-右子树-根的顺序遍历二叉树
//函数参数：
//          bt：表示传入的节点指针    
//参数返回值：无

void TREE::Postorderf(BTreeNode *bt)
{
	BTreeNode *p;
	int i;
	stack <BTreeNode *>s;
	stack <int> v;
	p=head;
	while((!s.empty())||(p!=NULL))
	{
		while((p!=NULL)&&(i!=1))
		{
           s.push(p);
		   v.push(0);
		   p=p->lchild;
		}
		if(!s.empty())
		{
			p=s.top();
			s.pop();
			i=v.top();
			v.pop();
        if(i==1)
		{
			cout<<p->data<<"\t";
		    if(p=head) p=NULL;
			}
		else
		{
			s.push(p);
			v.push(1);
			p=p->rchild;
            
		}
		}
		
}
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//层次遍历
//函数功能：以逐层深入的顺序遍历二叉树
//函数参数：
//          bt：表示传入的节点指针
//参数返回值：无

void TREE::Layerorder(BTreeNode *bt)
{
	queue <BTreeNode *> Q;
    BTreeNode *p;
	p=head;
	Q.push(p);
	while(!Q.empty())
	{
		p=Q.front();
		cout<<p->data<<"\t"; Q.pop();
		if(p->lchild!=NULL)
			Q.push(p->lchild);
		if(p->rchild!=NULL)
			Q.push(p->rchild);
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//求二叉树高函数
//函数功能：求二叉树的层高
//函数参数：
//          bt：表示传入的节点指针
//          first：表示传入的节点是否为根节点
//参数返回值：high: 表示二叉树的层高

int TREE::Altitude(BTreeNode *bt,int first)
{
	int high,lhigh,rhigh;
	BTreeNode *p;
	if(first)
	{
		p=head;
		first=0;
	}
	else p=bt;
	if(p==NULL)
		high=0;
	else
	{
		lhigh=Altitude(p->lchild, first);
		rhigh=Altitude(p->rchild, first);
	    if(lhigh>rhigh)
			high=lhigh+1;
		else
			high=rhigh+1;
	}
	return high;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//求二叉数的子叶数函数
//函数功能：求二叉树子叶的数量
//函数参数：无
//参数返回值：num：表示二叉树中子叶的数目

int TREE::Number()
{
	int num=0;
	BTreeNode *p;
	queue <BTreeNode *>Q;
	p=head;
	Q.push(p);
	while(!Q.empty())
	{
		p=Q.front();
		if((p->lchild==NULL)&&(p->rchild==NULL))
			num++;
		    Q.pop();
		if(p->lchild!=NULL)
			Q.push(p->lchild);
		if(p->rchild)
			Q.push(p->rchild);
	}
	return num;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//输出二叉树函数
//函数功能：输出二叉树的所有节点
//函数参数：
//          bt：表示传入的节点指针
//          first：表示传入的节点是否为根节点
//参数返回值：无

void TREE::Print(BTreeNode *bt, int first)
{
	BTreeNode *p;
	if(first)
	{
		p=head;
		first=0;
	}
	else
		p=bt;
	if(p!=NULL)
		cout<<p->data;
	if(p->lchild!=NULL)
	{
		cout<<"(";
		Print(p->lchild,first);
	}
	if(p->rchild!=NULL)
	{
		cout<<",";
		Print(p->rchild,first);
		cout<<")";
	}
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////程序名：tree.h
//      程序功能：二叉树类的头文件
//          作者：黄秋旋
//          日期：2008.11.9
//          版本：1.0
//      修改内容：
//      修改日期：
//      修改作者：
//对应类实现文件: tree.pp
//对应主程序文件: main.cpp
typedef char Datatype;                          //为本程序定义所使用的具体数据类型


struct BTreeNode                                //定义树的节点结构
{
	Datatype data;                
	BTreeNode *lchild;
	BTreeNode *rchild;
};


class TREE                                           //定义树的类
{
private:
    struct BTreeNode *bt;
	struct BTreeNode *head;
    int first;
public:
	BTreeNode *Create(int first);                    //建树函数
	void Preorder(BTreeNode *bt, int first);                //前序递归遍历
    void Preorderf(BTreeNode *bt);                   //前序非递归遍历
    void Inorder(BTreeNode *bt, int first);                 //中序递归遍历
    void Inoderf(BTreeNode *bt);                     //中序非递归遍历
	void Postorder(BTreeNode *bt, int first);               //后序递归遍历
	void Postorderf(BTreeNode *bt);                  //后序非递归遍历
	void Layerorder(BTreeNode *bt);                  //层次遍历
    int Altitude(BTreeNode *bt, int first);                 //求树高     
    int Number();                                    //求子叶数
    void Print(BTreeNode *bt, int first);                   //输出树
};