二叉树类.cpp

数据结构：二叉树

//二叉树类的实现文件“二叉树类.cpp”
#include<iostream.h>
#include<stdlib.h>

#include"二叉树类.h"
//按任意一种递归遍历次序输出二叉树中的所有结点
void BinaryTree::TraverseBTree(int mark)
{
	if(mark==1)::PreOrder(root);
	else if(mark==2)::InOrder(root);
	else if(mark==3)::PostOrder(root);
	else if(mark==4)::LevelOrder(root);
	else cout<<"mark参数值有误！"<<endl;
}

//根据存于字符数组a的二叉树广义表建立对应的二叉树存储结构
void CreateBTree(BTreeNode* & BT,char* a)
{
	//s数组作为存储二叉树中根结点指针的栈
	const MaxSize=10;  //栈数组长度要大于等于二叉树的深度减1
	BTreeNode* s[MaxSize];
	//用top作为s栈的栈顶指针并初始化
	int top=-1;
	//给树根指针置空
	BT=NULL;
	//定义p为指向二叉树结点的指针
	BTreeNode* p;
	//用k作为处理左子树和右子树的标记，k=1处理左子树，k=2处理右子树
	int k;
	//用i扫描数组a中存放的二叉树广义表字符串
	int i=0;
	//每循环一次处理一个字符，直到扫描到字符串结束符'\0'为止
	while(a[i]) {
		switch(a[i])
		{
		case ' '://对空格不作任何操作
			break;
		case '(':
			if(top==MaxSize-1) {
				cout<<"栈空间太小，请增加MaxSize的值！"<<endl;
				exit(1);
			}
			top++;  s[top]=p; k=1;
			break;
		case ')':
			if(top==-1) {
				cout<<"二叉树广义表字符串错！"<<endl; exit(1);
			}
			top--; break;
		case ',':
			k=2; break;
		default :   //扫描到的字符必为字母，即结点值
			p=new BTreeNode;
			p->data=a[i]; p->left=p->right=NULL;
			if(BT==NULL) BT=p;
			else {
				if(k==1) s[top]->left=p;
				else s[top]->right=p;
			}
		}
		i++;   //为扫描下一个字符修改i值
	}
}
	

//前序遍历算法
void PreOrder(BTreeNode* BT)
{
	if(BT!=NULL){
		cout<<BT->data<<' ';  //访问根结点
		PreOrder(BT->left);   //前序递归遍历左子树
		PreOrder(BT->right);  //前序递归遍历右子树
	}
}

//中序遍历算法
void InOrder(BTreeNode* BT)
{
	if(BT!=NULL) {
		InOrder(BT->left);  //中序递归遍历左子树
		cout<<BT->data<<' '; //访问根结点
		InOrder(BT->right); //中序递归遍历右子树
	}
}

//后序遍历算法 
void PostOrder(BTreeNode* BT)
{
	if(BT!=NULL) {
		PostOrder(BT->left);  //后序递归遍历左子树
		PostOrder(BT->right);  //后序递归遍历右子树
		cout<<BT->data<<' ';   //访问根结点
	}
}

//按层遍历算法
void LevelOrder(BTreeNode* BT)
{
	//定义存储二叉树结点指针的数组空间作为队列使用
	const MaxSize=30;  //为防止溢出，数组长度要不小于任何相邻两层的结点数之和
	BTreeNode* Q[MaxSize];
	//定义队首指针和队尾指针，初始均置0表示空队
	int front=0, rear=0;
	//定义结点指针类型的变量p
	BTreeNode* p;
	//树根结点指针进队
	if(BT!=NULL) {
		rear=(rear+1)%MaxSize;
		Q[rear]=BT;
	}
	//当队列非空时执行循环
	while(front!=rear) {
		front=(front+1)%MaxSize;  //后移队首指针
		p=Q[front];               //删除队首结点
		cout<<p->data<<' ';       //输出队首结点的值
		if(p->left!=NULL) {//若结点存在左孩子，则左孩子结点指针进队
			rear=(rear+1)%MaxSize;
			Q[rear]=p->left;
		}
		if(p->right!=NULL) {//若结点存在右孩子，则右孩子结点指针进队
			rear=(rear+1)%MaxSize;
			Q[rear]=p->right;
		}
	}
}

//从二叉树中查找值为x的结点，若存在则由x带回完整值并返回真，否则返回假
bool FindBTree(BTreeNode* BT, ElemType& x)
{
	if(BT==NULL) return false;  //树为空返回假
	else {
		if(BT->data==x) { //树根结点的值等于x，则由x带回并返回真
			x=BT->data;  
			return true;
		}
		else {
			//向左子树查找，若成功则继续返回真
			if(FindBTree(BT->left,x)) return true;
			//向右子树查找，若成功则继续返回真
			if(FindBTree(BT->right,x)) return true;
			//左右子树查找均失败则返回假
			return false;
		}
	}
}

//按照二叉树的一种表示方法输出整个二叉树
void PrintBTree(BTreeNode* BT)
      //按照二叉树广义表的形式输出二叉树
{
	if(BT==NULL) return;  //树为空时返回
	else {
		cout<<BT->data;  //输出根结点的值
		if(BT->left!=NULL || BT->right!=NULL) {
			cout<<'(';
			PrintBTree(BT->left);   //输出左子树
			if(BT->right!=NULL)
				cout<<',';
			PrintBTree(BT->right);   //输出右子树
			cout<<')';
		}
	}
}

//清除二叉树，使之成为一棵空树
void ClearBTree(BTreeNode* BT)
{
	if(BT!=NULL) {
		ClearBTree(BT->left);   //删除左子树
		ClearBTree(BT->right);  //删除右子树
		delete BT;              //释放根结点
		BT=NULL;                //置根指针为空
	}
}

//求二叉树的深度
int BTreeDepth(BTreeNode* BT)
{
	if(BT==NULL) return 0;
	else {
		int dep1=BTreeDepth(BT->left);   //计算左子树的深度
		int dep2=BTreeDepth(BT->right);   //计算右子树的深度
		//返回树的深度
		if(dep1>dep2) return dep1+1;
		else return dep2+1;
	}
}

//求二叉树中所有结点数
int BTreeCount(BTreeNode* BT)
{
	if(BT==NULL) return 0;
	else return BTreeCount(BT->left)+BTreeCount(BT->right)+1;
}

//求二叉树中所有叶子结点数
int BTreeLeafCount(BTreeNode* BT)
{
	if(BT==NULL) return 0;
	else if(BT->left==NULL && BT->right==NULL) return 1;
	else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);
}

//返回x结点所处的层号，若不存在值为x的结点则返回0
int NodeLevel(BTreeNode* BT,ElemType x)
{
	//空树层号为０
	if(BT==NULL) return 0;
	else if(BT->data==x) return 1;   //根结点的层号为１
	//向子树中查找x结点
	else {
		//求出x在左子树中的层号，返回该层号加１
		int c1=NodeLevel(BT->left,x);
		if(c1>=1) return c1+1;
		//求出x在右子树中的层号，返回该层号加１
		int c2=NodeLevel(BT->right,x);
		if(c2>=1) return c2+1;
		//在左、右子树中都不存在x结点，则返回０
		else return 0;
	}
}