编程之美--求二叉树中节点的最大距离

求二叉树节点的最大距离

如果把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两个节点之间的个数。

写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

推荐阅读： http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html

以下个人代码：

#include <iostream>
#include "vld.h"
using namespace std;

struct Node
{
	char val;
	int max_right;
	int max_left;
	Node *right;
	Node *left;
	Node(int ch)
	{
		val = ch;
		max_left = 0;
		max_right = 0;
		right = NULL;
		left = NULL;
	}
};
void bulid(Node **root);
void print_node(Node *root);
void delete_tree(Node *root);
void find_max_distance(Node *root,int &max_distance);
int main()
{
	Node *root = NULL;
	bulid(&root);
	if(root == NULL) cout<<"NULL！"<<endl;
	cout<<"先序遍历！"<<endl;
	print_node(root);
	cout<<"节点最大距离！"<<endl;
	int max_dis = 0;
	find_max_distance(root,max_dis);
	cout<<endl<<max_dis<<endl;

	delete_tree(root);
	return 0;
}

void bulid(Node **root)
{
	 char ch;
	 cin>>ch;
	 if (ch == '0')
	 {
		root = NULL;
	 }
	 else
	 {
		*root = new Node(ch);
		bulid(&((*root)->left));
		bulid(&((*root)->right));
	 }
}

void print_node(Node *root)
{ 
	 if(root == NULL) return ;

	cout<<root->val<<" ";
	print_node(root->left);
	print_node(root->right);
 
}


void delete_tree(Node *root)
{
	if(root == NULL) return ;

	delete_tree(root->left);
	delete_tree(root->right);
	delete root;

}

void find_max_distance(Node *root,int &max_distance)
{
	if (root == NULL)
	{
		return ;
	}
	
	if (root->left == NULL)
	{
		root->max_left = 0;
	}
	if (root->right == NULL)
	{
		root->max_right = 0;
	}

	if (root->left != NULL)
	{
		find_max_distance(root->left,max_distance);	

		if (root->left->max_left > root->left->max_right)
		{
			root->max_left = root->left->max_left + 1; 
		}
		else
		{
			root->max_left = root->left->max_right + 1;
		}
	}

	if (root->right != NULL)
	{
		find_max_distance(root->right,max_distance);

		if (root->right->max_left > root->right->max_right)
		{
			root->max_right = root->right->max_left + 1; 
		}
		else
		{
			root->max_right = root->right->max_right + 1;
		}
	}
	 
	if (max_distance < root->max_left + root->max_right)
	{
		max_distance = root->max_left + root->max_right;
	}

}