tree.cpp

二叉树的实现

//        程序名：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<<")";
	}
}