第 11 題（樹）
求二叉樹中節(jié)點的最大距離...
如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，
我們姑且定義"距離"為兩節(jié)點之間邊的個數(shù)。
寫一個程序，
求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點之間的距離。

?

思路：二叉樹結(jié)構(gòu)中只設(shè)了左右子節(jié)點的指針。

設(shè)單個結(jié)點的深度為0。

用后序遍歷，得到每個結(jié)點為根的子樹的最大深度。maxdistance記錄該結(jié)點（左子樹深度+右子樹深度 + 2）是否超過已有的最遠(yuǎn)距離，若超過更新。

關(guān)鍵：空指針的深度設(shè)為-1，這樣避免了復(fù)雜的分類討論。

? ? ? ? ? ? ?樹每個結(jié)點記錄的深度

　　? ? ? ? ? ? （4） ? ?

? ? 　　? ? ? ?/ ??

? ? ? ?　　（3） ? ：舉例計算 子樹中最大的深度是2，當(dāng)前結(jié)點最大深度是2+1 ? ?整棵樹最大距離為 1 + 2 + 2 = 5 比已有的

? ? ? 　　/ ? ? \ ? ? ? ? ? ? ? 整棵樹的最大距離大，更新。

?　　 （1） ? ? （2）

? ? ? ?/ ? ? ? ? / ? ? \

? （0） ? ? （1） ? ? （0）

? ? ? ? ? ? ?/

? ? ? ? ?（0） ：其左右子樹均為空，記其子樹的最大深度為-1 當(dāng)前結(jié)點的深度為 -1 + 1 = 0

?

代碼如下：唯一不滿意的是maxdistance設(shè)為了全局變量，看起來很丑。

/* 第 11 題（樹） 求二叉樹中節(jié)點的最大距離... 如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的， 我們姑且定義"距離"為兩節(jié)點之間邊的個數(shù)。 寫一個程序， 求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點之間的距離。 start time 16:17 end time 17:20 */#include <stdio.h> #include <stdlib.h>typedef struct BiTree {int data;BiTree * p_left, * p_right; }BiTree;void CreateBiTree(BiTree * &T) {int d;printf("please input data number:");scanf("%d", &d);if (d != 0){T = (BiTree *)malloc(sizeof(BiTree));T->data = d;T->p_left = NULL;T->p_right = NULL;CreateBiTree(T->p_left);CreateBiTree(T->p_right);} }//遞歸 int maxdistance = 0; int BiTreeMaxDistance(BiTree * T) //利用后序遍歷 { if (T == NULL){return -1;}else{int l = BiTreeMaxDistance(T->p_left);int r = BiTreeMaxDistance(T->p_right);int distance = l + r + 2;maxdistance = (distance > maxdistance) ? distance : maxdistance;return (l > r) ? l + 1 : r + 1;} }int main() {BiTree * T = NULL;CreateBiTree(T);BiTreeMaxDistance(T);printf("the max distance of the tree is %d.\n", maxdistance);return 0; }

?

網(wǎng)上找答案，發(fā)現(xiàn)居然是《編程之美》里的題。然后，書里的代碼也用了全局變量...感覺書里的方法沒有我的方法簡潔，代碼也比我的看起來復(fù)雜。不過整體思路還是一樣的。

又看了幾個人的博客，發(fā)現(xiàn)有幾個和我的思路是一樣的。真可謂英雄所見略同啊。

總結(jié)

以上是生活随笔為你收集整理的【编程题目】求二叉树中节点的最大距离的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。