题目： 如果把二叉树看成一个图，父子节点之间的连线看成是双下那个的，我们姑且定义距离是两个节点之间边的个数，写1个程序，求1棵二叉树中相距最远的两个节点之间的距离
解： 提示把二叉树看成图，有点误导的意思。 首先，两个节点之间的距离不存在重叠的边，其次，从1个节点到另1个节点的走法，肯定是第1个节点走到拐点，然后开始想第2个节点走，这个拐点一定是第1，2个节点的共同祖先。因此可用递归解决。
给定树T，首先求出树T的左子树的高度left_height，然后求出树T的右子树的高度right_height,那么假如说这个最大距离经过的拐点是T，那么这个最大距离就是left_height+right_height,然后递归求出左孩子的最大距离和右孩子的最大距离，3者之中最大值就是这个二叉树的最大距离
代码:
/* 求最大距离，其实这是1个递归问题。 因为a-b节点的边不能有重叠的，首先求出根结点左孩子最大深度，右孩子最大深度。dis=heightleft+hightright，然后分别 左孩子的dis和右孩子的dis,最大的就是本题要求的节点的最大距离. 若左右孩子是NULL，则返回0 */ #include<iostream> using namespace std; typedef int datatype; typedef struct node { datatype data; struct node* left; struct node* right; }Tree; // 先序建树，NULL节点输入0 Tree* create_tree(void) { Tree* t=NULL; datatype value; cin>>value; if(value==0) return NULL; else { t=new Tree; t->data=value; t->left=create_tree(); t->right=create_tree(); } return t; } //释放树 void free_tree(Tree* t) { if(t) { free_tree(t->left); free_tree(t->right); delete t; t=NULL; } } //求树t的高度 int height(Tree* t) { if(t==NULL) return 0; else { int left_height=height(t->left); int right_height=height(t->right); if(left_height>=right_height) return left_height+1; else return right_height+1; } } //求t的最大距离 int getdis(Tree* t) { if(t) { int leftheight=height(t->left); int rightheight=height(t->right); //高h，则有h-1条边，h1-1+h2-1+1+1=h1+h2 int dis=leftheight+rightheight; int dis_left=getdis(t->left); int dis_right=getdis(t->right); if(dis>=dis_left && dis>=dis_right) return dis; if(dis_left>=dis && dis_left>=dis_right) return dis_left; if(dis_right>=dis && dis_right>=dis_left) return dis_right; } else return 0; } int main(void) { Tree* root=NULL; root=create_tree(); cout<<height(root)<<endl; cout<<getdis(root)<<endl; free_tree(root); return 0; }
试验了几个树，都能输出正确结果。例如输入 1 2 0 3 4 5 6 7 0 0 0 0 0 8 0 9 0 10 0 11 0 0 12 0 0 ，最大距离是8