二叉树的实现.cpp

二叉树的虚拟实现 c语言版

#include<iostream.h>
#define MAXSIZE 100

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode;


/*****由前序遍历序列和中序遍历序列构造二叉树*****/


BiTNode *CreateBiTree(char *pre,char *mid,int n)
{
	
	BiTNode *T;
	char *search;
	int k;

	T=new(BiTNode);
	T->data=*pre;
	
	for(search=mid;search<mid+n;search++)//在中序序列中找到根
		if(*search==*pre)
			break;
    
    k=search-mid;//左子树的结点个数
	
	T->lchild=CreateBiTree(pre+1,mid,k);//递归构造左子树
	T->rchild=CreateBiTree(pre+k+1,search+1,n-k-1);//递归构造右子树

	return T;
}


/*****层次遍历二叉树*****/


void LevelFirstTraverse(BiTNode *T)
{
	struct Queue
	{
		BiTNode *base[MAXSIZE];
		int front,rear;
	};
    struct Queue Q;

	Q.front=0;
	Q.rear=0;

	if(T!=NULL)
	{
		cout<<T->data;
		Q.base[Q.rear]=T;
		Q.rear++;

		while(Q.front!=Q.rear)
		{
			T=Q.base[Q.front];
			Q.front++;

			if(T->lchild!=NULL)
			{
				cout<<T->lchild->data;
				Q.base[Q.rear]=T->lchild;
				Q.rear++;
			}

			if(T->rchild!=NULL)
			{
				cout<<T->rchild->data;
				Q.base[Q.rear]=T->rchild;
				Q.rear++;
			}
		}
	}
}


/*****求二叉树的深度*****/

int BiTreeDepth(BiTNode *T)
{
	int ldep,rdep;

	if(T==NULL)
		return 0;
	else
	{
		ldep=BiTreeDepth(T->lchild);
        rdep=BiTreeDepth(T->rchild);

		if(ldep>rdep)
			return(ldep+1);
		else
			return(rdep+1);
	}
}


/*****求二叉树的叶子数*****/


int Leavesnum(BiTNode *T)
{
	int Lleaves,Rleaves;

	if(T==NULL)
		return 0;
	else if(T->lchild==NULL&&T->rchild==NULL)
		return 1;
	else
	{
		Lleaves=Leavesnum(T->lchild);
        Rleaves=Leavesnum(T->rchild);
		return(Lleaves+Rleaves);
	}
}


void main()
{
	BiTNode *T;
	char pre[]="abcdef",mid[]="bcaedf";
	int leavesnum,depth,num;

	cout<<"请输入二叉树的结点个数：";
	cin>>num;

	T=CreateBiTree(pre,mid,num);
	LevelFirstTraverse(T);
	depth=BiTreeDepth(T);
	leavesnum=Leavesnum(T);

	cout<<"二叉树的深度为："<<depth<<endl;
	cout<<"二叉树的叶子数为："<<leavesnum<<endl;
}