如果我们把二叉树看成一个图，，父子节点间的连线看成是双向的，我们姑且定义“距离”为两节点之间边的个数。
写一个程序，求一颗二叉树中相距最远的两个节点之间的距离。
例如：
二叉树为：
1
/ \
2 3
\
4
/
5
则两点间最大的距离为5
实现如下：
#include<iostream>using namespace std;struct BSTree{BSTree(int _v = 0):value(_v),left(NULL),right(NULL) {}int value;BSTree *left;BSTree *right;};int findMaxEd_num(BSTree *bst, int& max_depth, int &maxed_num){if(bst == NULL){max_depth = 0;maxed_num = 0;return 0;}int left_maxdepth = 0;int right_maxdepth = 0;int left_maxednum = 0;int right_maxednum = 0;if(bst->left != NULL)findMaxEd_num(bst->left, left_maxdepth, left_maxednum);if(bst->right != NULL)findMaxEd_num(bst->right, right_maxdepth, right_maxednum);max_depth = left_maxdepth>right_maxdepth?left_maxdepth:right_maxdepth;max_depth += 1;maxed_num = left_maxdepth + right_maxdepth + 1;if(maxed_num < left_maxednum)maxed_num = left_maxednum;if(maxed_num < right_maxednum)maxed_num = right_maxednum;return maxed_num;}int main(){BSTree *root = new BSTree(1);root->left = new BSTree(2);root->right = new BSTree(3);root->left->right = new BSTree(4);root->left->right->left = new BSTree(5);int max_num = 0;int max_depth = 0;cout << "BSTree’s max distance is " << findMaxEd_num(root, max_num, max_depth) << endl;return 0;}
输出结果为：
BSTree’s max distance is 5
版权声明：本文为博主原创文章，未经博主允许不得转载。
再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。
