cpp1.cpp

采用分治的算法来求解二叉树的高度的问题.

#include "iostream.h"
#include "malloc.h"
#define maxsize 100
typedef struct node
{
	int data;
	struct node *lc,*rc;
}Btree;

typedef struct node *bitreptr,*tpointer;

tpointer nar[maxsize];

bitreptr creat(bitreptr root)
{
	int n,i,j,f,x;
	cout<<"输入结点数：";
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cout<<"输入编号：";
		cin>>j;
		cout<<"输入值：";
		cin>>x;
		nar[j]=(bitreptr)malloc(sizeof(Btree));
		nar[j]->data=x;
		nar[j]->lc=0;
		nar[j]->rc=0;
		if(j==1)
			root=nar[j];
		else
		{
			f=j/2;
			if(j%2==0)
				nar[f]->lc=nar[j];
			else if(j%2!=0)
				nar[f]->rc=nar[j];
		}
	}
	return root;
}

int high(bitreptr root)
{
	if(!root)
		return 0;
	else
	{
		if(high(root->lc)>=high(root->rc))
			return (1+(high(root->lc)));
		else
			return (1+(high(root->rc)));
	}
}

void main()
{
	bitreptr t=0;
	t=creat(t);
	cout<<high(t)<<endl;
}