01.cpp

1、二叉树数据结构表示及基本操作算法实现 2.二叉树递归遍历算法 3.二叉树创建递归算法

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<strstrea.h>

template<class T>class BinaryTree;
template<class T>class BTreeNode
{
	private:
		BTreeNode<T>*left;//左子数指针
		BTreeNode<T>*right;//右子数指针
	public:
		T data;//数据域
		BTreeNode():left(NULL),right(NULL){}
		BTreeNode(T item,BTreeNode<T>*left1=NULL,
			BTreeNode<T>*right1=NULL):data(item),left(left1),right(right1){}
		BTreeNode<T>*&Left(){return left;}
		BTreeNode<T>*Right(){return right;}
		friend class BinaryTree<T>;

};
template<class T>class BinaryTree
{
	private:
		BTreeNode<T>*root;
	public:
		BinaryTree(){root=NULL;}//构造函数，初始画二叉树为空
		void CreateBTree(char *a);//根据字符数组A的二叉树广义表建立对应的二叉数存储结构
		bool BTreeEmpty(){return root==NULL;}//判断二叉数是否为空
		void TraverseBTree(int mark);//按任一种便利次序输出二叉树中的所有接点
		void Traverse(BTreeNode<T>*&BT,int mark);//用与便利的递归函数
		int BTreeDepth();//求二叉数的深度
		int Depth(BTreeNode<T>*&BT);//用与求二叉数深度的递归函数
		int BTreeCount();//求二叉树中所有接点数
		int Count(BTreeNode<T>*&BT);//用与二叉树中的所有接点的递归函数
		int BTreeLeafCount();//求二叉数中所有叶子的接点数
		int LeafCount(BTreeNode<T>*&BT);//用与求二叉树中所有叶子接点的递归函数
		void PrintBTree();//按照二叉树的一种表示方法输出整个二叉树
		void Print(BTreeNode<T>*&BT);//用与输出二叉树的递归函数
		void Clear(BTreeNode<T>*&BT);//用与清楚二叉树的递归函数
		~BinaryTree();//析够函数

};
void main()
{
	int n;
	char b[80]="(a)(b),c(d),e(f),g(h),i(j),k(l),m(n),o@";
	BinaryTree<char> B;
	cout<<"创建的二叉树为"<<endl;
	B.CreateBTree(b);cout<<endl;
	if(B.BTreeEmpty())
		cout<<"do not noting"<<endl;
	else
		cout<<"nothing"<<endl;
	cout<<"先序遍历二叉数"<<endl;
	B.TraverseBTree(1);cout<<endl;
	cout<<"中序遍历二叉数"<<endl;
	B.TraverseBTree(2);cout<<endl;
	cout<<"后序遍历二叉数"<<endl;
	B.TraverseBTree(3);cout<<endl;
	cout<<"按层遍历二叉树"<<endl;
	B.TraverseBTree(4);cout<<endl;
	n=B.BTreeDepth();
		cout<<"二叉树的深度"<<n<<endl;
	n=B.BTreeCount();
	cout<<"二叉树的的所有接点数"<<n<<endl;
	n=B.BTreeLeafCount();
    cout<<"二叉数的所有叶子的结点树"<<n<<endl;
	cout<<"按二叉数的广义表输出"<<endl;
	cout<<'(';
	B.PrintBTree();
	cout<<')'<<endl;
	cin.get();
}
template<class T>
void BinaryTree<T>::CreateBTree(char *a)
{
	BTreeNode<T>*s[80];//S数组做为存储二叉树中跟接点指针的栈
	int top=-1;//TOP做为S栈的栈顶指针
	root=NULL;//给树根指针置空
	BTreeNode<T>*p=NULL;//定义P为指想二叉树接点的指针
	int k;//用K作为处理接点的左子树和又子树的标记
	istrstream ins(a);//把字符窜A定义为输入字符窜流对象ins
	char ch;
	ins>>ch;
	while(ch!='@')
	{
		switch(ch)//每循环一次处理一个读入的字符。直到扫描完为止
		{
		case '(':top++;s[top]=p;k=1;break;
		case')':top--;break;
		case',':top++;k=2;break;
		default:p=new BTreeNode<T>;
			p->data=ch;p->left=p->right=NULL;
			cout<<setw(2)<<p->data;
			if(root==NULL)root=p;
			else{
				if(k==1) s[top]->left=p;
				else s[top]->right=p;
			}
		}
		ins>>ch;
	}
}
template<class T>
void BinaryTree<T>::TraverseBTree(int mark)
{Traverse(root,mark);}
template<class T>
void BinaryTree<T>::Traverse(BTreeNode<T>*&BT,int mark)
{
	if(mark==1)//先序便利
	{
		if(BT!=NULL)
		{
			cout<<BT->data<<' ';
			Traverse(BT->left,mark);
			Traverse(BT->right,mark);
		}
	}
	else
		if(mark==2)//中序便利
		{
			if(BT!=NULL)
			{
				Traverse(BT->left,mark);
				cout<<BT->data<<' ';
				Traverse(BT->right,mark);

			}
		}
		else 
			if(mark==3)//后序便利
		{
			if(BT!=NULL)
			{
				Traverse(BT->left,mark);
				
				Traverse(BT->right,mark);
                cout<<BT->data<<' ';

			}
		}
		else
			if(mark==4)//按层便利
			{
				const MaxLength=80;
				BTreeNode<T>*Q[MaxLength];//定义存储二叉数接点的指针的数组空间做为队列使用
				int front=0,rear=0;//定义对首指针和对尾指针
				BTreeNode<T>*p;
				if(BT!=NULL)
				{
					rear=(rear+1)%MaxLength;//后移对尾指针
					Q[rear]=BT;//将数根接点指针进对
				}
				while(front!=rear)
				{
					front=(front+1)%MaxLength;//后移对首指针
					p=Q[front];//删除对首指针
					cout<<p->data<<' ';//输出对首指针的值
					if(p->left!=NULL)//若接点存在左孩子，则左孩子接点指针进对
					{
						rear=(rear+1)%MaxLength;
						Q[rear]=p->left;
					}
					if(p->right!=NULL)//若接点存在右孩子，则右孩子接点指针进对
					{
						rear=(rear+1)%MaxLength;
						Q[rear]=p->right;
					}
				}
			}
			else
			{
				cout<<"mark fail"<<endl;
				exit(1);
			}
}
template<class T>
int BinaryTree<T>::BTreeDepth()
{return Depth(root);}
template<class T>
int BinaryTree<T>::Depth(BTreeNode<T>*&BT)
{
	if(BT==NULL)return 0;
	else 
	{
		int dep1=Depth(BT->left);//计算左子书的深度
		int dep2=Depth(BT->right);//计算右子书的深度
		if(dep1>dep2)return dep1+1;//返回树的深度
		else return dep2+1;
	}
}
template<class T>//求二叉数的所有接点
int BinaryTree<T>::BTreeCount()
{return Count(root);}
template<class T>
int BinaryTree<T>::Count(BTreeNode<T>*&BT)
{
	if(BT==NULL)return 0;
	else
		return Count(BT->left)+Count(BT->right)+1;
}
template<class T>//求二叉数的叶子接点数
int BinaryTree<T>::BTreeLeafCount()
{return LeafCount(root);}
template<class T>
int BinaryTree<T>::LeafCount(BTreeNode<T>*&BT)
{
	if(BT==NULL)return 0;
	else if(BT->left==NULL&&BT->right==NULL)return 1;
	else return LeafCount(BT->left)+LeafCount(BT->right);
}
template<class T>//按照二叉树的广义表输出
void BinaryTree<T>::PrintBTree()
{Print(root);}
template<class T>
void BinaryTree<T>::Print(BTreeNode<T>*&BT)
{
	if(BT==NULL)return;
	else{
		cout<<BT->data;//输出根接点的植
		if(BT->left!=NULL||BT->right!=NULL)
		{
			if(BT->left!=NULL)
				cout<<'(';//输出左括号
			Print(BT->left);//输出左子书
			if(BT->right!=NULL)//若右子数不为空则输出逗号分阁
				cout<<',';
			Print(BT->right);//输出又子数
			if(BT->left!=NULL&&BT->right!=NULL)
				cout<<')';//输出右括号
		}
	}
}
template<class T>
BinaryTree<T>::~BinaryTree()
{
	Clear(root);
}
template<class T>
void BinaryTree<T>::Clear(BTreeNode<T>*&BT)
{
	if(BT!=NULL)
	{
		Clear(BT->left);//删除左子书
		Clear(BT->right);//删除右子书
		delete BT;//删除跟接点
		BT=NULL;//置跟指针为空
	}
}