求二叉樹中節點的最大距離，程式設計之美3.8

//　求二叉樹中節點的最大距離，程式設計之美3.8

#inlcude <iostream>

using namespace std;

struct Node

{

Node *lchild;

Node *rchild;

//data

};

//因為最大距離，一定是已樹中某點為根　的左右子樹高度之和

int get_max_distance(tree* root,int& maxlen)

{

if(root==null) return 0;//空結點傳回0

int Lhight = get_max_distance(root->lchild, maxlen);

int Rhight = get_max_distance(root->rchild, maxlen) ;

if( Lhight+Rhight > maxlen) maxlen = Lhight+Rhight ;

return max(Lhight,Rhight)+1; //樹的高度＝max(左子樹高度，右子樹高度)+1

}

01 // 資料結構定義

02 struct NODE

03 {

04 NODE* pLeft; // 左子樹

05 NODE* pRight; // 右子樹

06 int nMaxLeft; // 左子樹中的最長距離

07 int nMaxRight; // 右子樹中的最長距離

08 char chValue; // 該節點的值

09 };

10

11 int nMaxLen = 0;

12

13 // 尋找樹中最長的兩段距離

14 void FindMaxLen(NODE* pRoot)

15 {

16 // 周遊到葉子節點，傳回

17 if(pRoot == NULL)

18 {

19 return;

20 }

21

22 // 如果左子樹為空，那麼該節點的左邊最長距離為0

23 if(pRoot -> pLeft == NULL)

24 {

25 pRoot -> nMaxLeft = 0;

26 }

27

28 // 如果右子樹為空，那麼該節點的右邊最長距離為0

29 if(pRoot -> pRight == NULL)

30 {

31 pRoot -> nMaxRight = 0;

32 }

33

34 // 如果左子樹不為空，遞歸尋找左子樹最長距離

35 if(pRoot -> pLeft != NULL)

36 {

37 FindMaxLen(pRoot -> pLeft);

38 }

39

40 // 如果右子樹不為空，遞歸尋找右子樹最長距離

41 if(pRoot -> pRight != NULL)

42 {

43 FindMaxLen(pRoot -> pRight);

44 }

45

46 // 計算左子樹最長節點距離

47 if(pRoot -> pLeft != NULL)

48 {

49 int nTempMax = 0;

50 if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)

51 {

52 nTempMax = pRoot -> pLeft -> nMaxLeft;

53 }

54 else

55 {

56 nTempMax = pRoot -> pLeft -> nMaxRight;

57 }

58 pRoot -> nMaxLeft = nTempMax + 1;

59 }

60

61 // 計算右子樹最長節點距離

62 if(pRoot -> pRight != NULL)

63 {

64 int nTempMax = 0;

65 if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)

66 {

67 nTempMax = pRoot -> pRight -> nMaxLeft;

68 }

69 else

70 {

71 nTempMax = pRoot -> pRight -> nMaxRight;

72 }

73 pRoot -> nMaxRight = nTempMax + 1;

74 }

75

76 // 更新最長距離

77 if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)

78 {

79 nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;

80 }

81 }