版权声明：欢迎查看本博客。希望对你有有所帮助 https://blog.csdn.net/cqs_2012/article/details/24880735

the longest distance of a binary tree

个人信息：就读于燕大本科软件project专业 眼下大三;

本人博客：google搜索“cqs_2012”就可以;

个人爱好：酷爱数据结构和算法，希望将来从事算法工作为人民作出自己的贡献;

博客内容：the longest distance of a binary tree;

博客时间：2014-4-26;

编程语言：C++ ;

编程坏境：Windows 7 专业版 x64;

编程工具：vs2008 32位编译器;

制图工具：office 2010 ppt;

硬件信息：7G-3 笔记本;

my words

simple life  is just good.

words for my brother: i miss you 

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY3FzX2V4cGVyaW1lbnQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />

problem

the longest distance of a binary tree(problem from beauty of programming)

eg: the following binary tree

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY3FzX2V4cGVyaW1lbnQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />

the longest distance is 8 

my solution 

recursion solution

int _Longest_distance(node * T,int & deep)

{

    if(T == NULL)

    {

		deep = 0;

		return 0;

    }

    else

    {

		int left  = 0;

		int right = 0;

		int Ldeep = 0;

		int Rdeep = 0;

		left = _Longest_distance(T->left,Ldeep);

		right = _Longest_distance(T->right,Rdeep);

		deep = (Ldeep > Rdeep? Ldeep:Rdeep) + 1;

		int result = left > right?left :right;

		result = result> (Ldeep + Rdeep)? result:(Ldeep+Rdeep);

		return result ;

    }

}

experiment

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY3FzX2V4cGVyaW1lbnQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />

program run out: 7

my code

test.cpp

#include<iostream>

using namespace std;

class node

{

public:

    int data ;

    node * left ;

    node * right ;

    node()

	{

        data = 0 ;

        left = right = NULL ;

    }

};

void _MakeTree(node * &T,int *data,int length);

void _Insert(node * & T,int data);

void _MakeTree(node * &T,int *data,int length)

{

    for(int i=0;i<length;i++)

    {

		_Insert(T,data[i]);

    }

}

void _Insert(node * & T,int data)

{

    if(T == NULL)

    {

		T = new node();

		T -> data = data;

    }

    else

    {

		node * p = T;

		while(p != NULL)

		{

			if(data == p->data )

			break;

			else if(data < p->data )

			{

				if(p->left != NULL)

				{

					p = p ->left;

				}

				else{

					p->left = new node();

					(p->left) ->data = data;

					break;

				}

			}

			else{

				if(p->right != NULL)

					p = p->right;

				else{

					p->right = new node() ;

					(p->right) ->data = data ;

					break ;

				}

			}

		}

    }

}

int _Longest_distance(node * T,int & deep)

{

    if(T == NULL)

    {

		deep = 0;

		return 0;

    }

    else

    {

		int left  = 0;

		int right = 0;

		int Ldeep = 0;

		int Rdeep = 0;

		left = _Longest_distance(T->left,Ldeep);

		right = _Longest_distance(T->right,Rdeep);

		deep = (Ldeep > Rdeep?

Ldeep:Rdeep) + 1;

		int result = left > right?left :right;

		result = result> (Ldeep + Rdeep)? result:(Ldeep+Rdeep);

		return result ;

    }

}

int main()

{

    int data[] = {8,6,3,7,2,1,13,12,15,17};

    node * T = NULL;

    _MakeTree(T,data,10);

    int deep =0;

    cout<<_Longest_distance(T,deep)<<endl;

    system("pause");

    return 0;

}