二叉树0.cpp

这是用c++编写的关于二叉树的实验

#include <iostream.h>
#include <stdlib.h>
//using namespace std;
int m=0;
#define MAX_TREE_SIZE 100   //定义二叉树的最大存储值
typedef struct BiTNode     //定义二叉树结构体
{
     char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BTree;
void InitBTree(BTree &T)
{
	T=new BiTNode;
	T->data=NULL;
	T->lchild=NULL;
	T->rchild=NULL;
}
void CreateBTree(BTree &T)
{
	//BiTNode *p;
	char ch;
	cin>>ch;
	if(ch=='!') T=NULL;  //退出条件
	else
	{
		T=new BiTNode; //开辟新结点
		T->data=ch;
		CreateBTree(T->lchild);  //创建左孩子
		CreateBTree(T->rchild);  //创建右孩子
	}

}
void PreOrder(BTree T)  //先序遍历输出结点
{
	if(T!=NULL)
	{
		//if(T->lchild==NULL&&T->rchild)
		cout<<T->data<<' ';     //输出结点
		PreOrder(T->lchild);    //先序遍历左孩子
		PreOrder(T->rchild);    //先序遍历右孩子
	}
}
void InOrder(BTree T)  //中序遍历输出结点
{
	if(T!=NULL)
	{
		//if(T->lchild==NULL&&T->rchild)
			
		InOrder(T->lchild);  //中序遍历左孩子
		cout<<T->data<<' ';  //输出结点
		InOrder(T->rchild);  //中序遍历右孩子
	}
}
void PostOrder(BTree T)   //后序遍历输出结点
{
	if(T!=NULL)
	{
		//if(T->lchild==NULL&&T->rchild)
			
		PostOrder(T->lchild);  //后序遍历左孩子
		PostOrder(T->rchild);  //后序遍历右孩子
		cout<<T->data<<' ';    //输出结点
	}
}
void LevelOrder(BTree T)    //层次遍历输出结点
{
	const MaxLength=30;   //定义一个最大长度常量为30
		BiTNode* Q[MaxLength];  //定义一个队列指针数组
		int front=0,rear=0;  //将队列置为空
		BiTNode* BT;  //定义指针结点
		if(T!=NULL){
			rear=(rear+1)%MaxLength;  //队尾结点后移
			Q[rear]=T;  //将指针赋给队尾元素
		}
		while(front!=rear)   //队列不为空
		{
			front=(front+1)%MaxLength;  //对头元素后移
			BT=Q[front];  //将对头元素赋给指针
			cout<<BT->data<<' ';  //输出结点
			if(BT->lchild!=NULL)
			{
				rear=(rear+1)%MaxLength;
				Q[rear]=BT->lchild;  //遍历左孩子
			}
			if(BT->rchild!=NULL)
			{
				rear=(rear+1)%MaxLength;
				Q[rear]=BT->rchild;  //遍历右孩子
			}
		}
}
void Traverse(BTree T)  //定义遍历函数
{
    //BiTNode* BiT;
	char j;
	cin>>j;
	switch(j)
	{
	case 'A':PreOrder(T);break;
	case 'B':InOrder(T);break;
    case 'C':PostOrder(T);break;
	case 'D':LevelOrder(T);break;
	default :cout<<"错误"<<endl;break;
	}
}


int BTreeDepth(BTree T)  //求树的深度
{
	if(T=NULL)return 0;
	else
	{
		int depl=BTreeDepth(T->lchild);   //遍历左子树的深度
		int depr=BTreeDepth(T->rchild);  //遍历右子树的深度
		if(depl>depr)
		return depl+1;
		else return depr+1;
	}

}
int BTreeCount(BTree T)
{
	
	if(T=NULL) return 0;
	else
	{
		m++;     //计数器
	    BTreeCount(T->lchild);  //遍历左孩子
	    BTreeCount(T->rchild);  //遍历右孩子
	}

	/*int m;