030300726_2.cpp

求二叉树深度与节点数的集合

#include <iostream>
#include <fstream>
using namespace std;


int m=1;
typedef struct BiTNode
{
	int data;
	int sign;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//
void find(BiTree &t,int r,BiTree &p)
{
	if(t->data==r){p=t;m=0; return ;}

	if(m==1&&t->sign==1&&t->lchild!=NULL){	find(t->lchild,r,p);}
	if(m==1&&t->sign==1&&t->rchild!=NULL){	find(t->rchild,r,p);}
    m=1;
    return;
}
//
void Create(BiTree &t,int root,int ldata,int rdata)
{
	
	BiTree	p=NULL;
	if(t==NULL){t=(BiTNode *)malloc(sizeof(BiTNode)); p=t ;}
	else 
	{
		p=t;
		find(t,root,p);
	}
	if(p!=NULL)	{ 
	p->data=root; 
	if(ldata==0)p->lchild=NULL;
    else{
			p->lchild=(BiTNode *)malloc(sizeof(BiTNode));
			p->lchild->data=ldata; 
		}
	if(rdata==0)p->rchild=NULL;
	else{
			p->rchild=(BiTNode *)malloc(sizeof(BiTNode));
			p->rchild->data=rdata; 
		}
	}
	p->sign=1;
}
//
void PreOrder(BiTree t,int a[],int NUMBER)
{
	for(int i=0;i<NUMBER&&a[i]!=0;++i);
	a[i]=t->data;
	if(t->lchild!=NULL)	PreOrder(t->lchild,a,NUMBER);
	if(t->rchild!=NULL)	PreOrder(t->rchild,a,NUMBER);
	return;
}
//


void InOrder(BiTree t,int a[],int NUMBER)
{
	if(t->lchild!=NULL)	InOrder(t->lchild,a,NUMBER);
	for(int i=0;i<NUMBER&&a[i]!=0;++i);
	a[i]=t->data;
	if(t->rchild!=NULL)	InOrder(t->rchild,a,NUMBER);
	return;
}

void postOrder(BiTree t,int a[],int NUMBER)
{
	if(t->lchild!=NULL)	postOrder(t->lchild,a,NUMBER);
	
	
	if(t->rchild!=NULL)	postOrder(t->rchild,a,NUMBER);
     for(int i=0;i<NUMBER&&a[i]!=0;++i);
     a[i]=t->data;
	return;
}

int depth(BiTree t){
	int dep1,dep2;
  //若T为空树，则深度为0，否则其深度等于左子树或右子树的最大深度加1
     if (t==NULL) return 0;
     else {dep1=depth(t->lchild);
           dep2=depth(t->rchild);
           return dep1>dep2?dep1+1:dep2+1;
  }
       }
//
void main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		cerr<<"the input is not exist!"<<endl;
		return  ;
	}
	ofstream out("output.txt");
	int num1;
	BiTree t1=NULL;
	in>>num1; 
	int root1,ldata1,rdata1;
	for(int i=0;i<num1;i++)
	{
		in>>root1>>ldata1>>rdata1;
	 	Create(t1,root1,ldata1,rdata1);		
	}

	
	int *a=new int[3*num1];
    	int *b=new int[3*num1];
      	int *c=new int[3*num1];

for(i=0;i<3*num1;i++)
		a[i]=b[i]=c[i]=0;

	int y=depth(t1);
	out<<y<<endl;

	PreOrder(t1,a,3*num1);
	for( i=0;i<num1;i++)
		out<<a[i]<<" ";
	out<<endl;
 	
		InOrder(t1,b,3*num1);//中序遍历
    for( i=0;i<num1;i++)
		out<<b[i]<<" ";
    out<<endl;
    postOrder(t1,c,3*num1);
        
for( i=0;i<num1;i++)
		out<<c[i]<<" ";
	

}