学步园

/*
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。

把最深的左子树距离加上最深的右子树距离就是二叉树中两个节点的最大距离。
*/ 
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;


struct BTreeNode{
	int data;
	BTreeNode *left,*right;
}; 

//建立二叉树 
BTreeNode * CreateTree(int data[],int pos,int len)
{
	BTreeNode *tree;
	if(pos>=len) 
	{
		return NULL;
	}
	else
	{
		tree=(BTreeNode *)malloc(sizeof(BTreeNode));
		tree->data=data[pos];
		tree->left=CreateTree(data,2*pos+1,len);//数组坐标 
		tree->right=CreateTree(data,2*pos+2,len);
		return tree;
	}
}

//最大深度 
int getMaxDepth(BTreeNode *root)
{
	if(root==NULL)
		return 0;
	if(NULL==root->left&&NULL==root->right)
		return 1;
		
	int nLeftDepth=0,nRightDepth=0;
	if(NULL!=root->left)
		nLeftDepth=getMaxDepth(root->left)+1;
	if(NULL!=root->right)
		nRightDepth=getMaxDepth(root->right)+1;
		
	return nRightDepth>=nLeftDepth?nRightDepth:nLeftDepth;
}

//取得最大距离=左最大深度+右最大深度   
int getMaxDistance(BTreeNode *root)
{
	if(NULL==root) 
		return 0;
		
	int nLeftDepth=getMaxDepth(root->left);
	nLeftDepth+=(root->left!=NULL?1:0);
	
	int nRightDepth=getMaxDepth(root->right);
	nRightDepth+=(root->right!=NULL?1:0);
	
	return nLeftDepth+nRightDepth;
}

int main()
{
	/*
		 5
	   4   8
	 7 12 10 	
	*/
	int data[]={5,4,8,7,12,10};
	int len=sizeof(data)/sizeof(int);
	BTreeNode *tree=CreateTree(data,0,len);
	
	int nMaxDis = getMaxDistance(tree);  
    cout <<"11.求二叉树中节点的最大距离："<<nMaxDis<<endl;  
    //4
    
    
    /*
		 5
	   4   8
	 7 12 10 13
	16	
	*/
	int data2[]={5,4,8,7,12,10,13,16};
	int len2=sizeof(data2)/sizeof(int);
	BTreeNode *tree2=CreateTree(data2,0,len2);
	
	int nMaxDis2 = getMaxDistance(tree2);  
    cout <<"11.求二叉树中节点的最大距离："<<nMaxDis2<<endl;  
    //5
	return 0;
}