生活随笔
收集整理的這篇文章主要介紹了
二叉树分析(两点最大距离)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
轉載自：http://blog.csdn.net/lalor/article/details/7626678 ? ? ? ? ??http://blog.csdn.net/lalor/article/details/7618120
把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，我們姑且定義"距離"為兩節點之間邊的個數。寫一個程序求一棵二叉樹中相距最遠的兩個節點之間的距離。
書上的解法
書中對這個問題的分析是很清楚的，我嘗試用自己的方式簡短覆述。
計算一個二叉樹的最大距離有兩個情況:
情況A: 路徑經過左子樹的最深節點，通過根節點，再到右子樹的最深節點。 情況B: 路徑不穿過根節點，而是左子樹或右子樹的最大距離路徑，取其大者。 只需要計算這兩個情況的路徑距離，并取其大者，就是該二叉樹的最大距離。
代碼參考編程之美，或者http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html
這段代碼有幾個缺點:
算法加入了侵入式(intrusive)的資料nMaxLeft, nMaxRight 使用了全局變量 nMaxLen。每次使用要額外初始化。而且就算是不同的獨立資料，也不能在多個線程使用這個函數 邏輯比較復雜，也有許多 NULL 相關的條件測試。
我的思路：
在看到這題的時候，我沒有馬上看答案，而是自己思考了一會，得出如下思路，最后跟http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html的思路基本一樣，只是實現上略有不同。
這個問題的核心是，情況A?及 B 需要不同的信息: A 需要子樹的最大深度，B 需要子樹的最大距離。只要函數能在一個節點同時計算及傳回這兩個信息，我是通過一個整形指針保存樹中的局部最大距離。然后通過返回值，分別樹的最大深度，如果左右子樹的最大深度相加大于當前樹的最大距離，則更新最大距離，最后返回左右子樹中較大的深度，這樣可以輕易求得它們父親的最大深度。（關于建樹部分，可以參考http://blog.csdn.net/lalor/article/details/7618120）
代碼核心：
int DistanceCore(BinaryTreeNode *root, int *max)
完整代碼如下：
#include?<iostream> ??#include?<stdlib.h> ??using ?namespace ?std;???? struct ?BinaryTreeNode???{?? ????int ?m_nValue;?? ????struct ?BinaryTreeNode?*m_pLeft;?? ????struct ?BinaryTreeNode?*m_pRight;?? };?? ?? int ?maxDistance(BinaryTreeNode?*root,?int ?*max);??int ?DistanceCore(BinaryTreeNode?*root,int ?*max);???? void ?Traverse(?BinaryTreeNode?*?root);??BinaryTreeNode*?Construct(int ?*preorder,?int ?*inorder,?int ?lenght);?? BinaryTreeNode*?ConstructCore(int ?*startPreorder,?int ?*endPreorder,?int ?*startInorder,?int ?*endInorder);?? int ?InsertNodeAtMostRight(BinaryTreeNode?*?root,?BinaryTreeNode?*?node);???? ?? int ?main(int ?argc,?char *?argv[])??{?? ?? ????int ?preOrder[]?=?{5,?4,?8,?9,?6,?3,?18,?19,?2};?? ????int ?inOrder[]?=?{9,?8,?6,?3,?4,?5,?19,?18,?2};?? ?? ????int ?max;?? ?? ?????? ????BinaryTreeNode?*parent?=?Construct(preOrder,?inOrder,?sizeof (inOrder)?/?sizeof (inOrder[0]));?? ?? ????cout?<<?"A樹的后序遍歷的結果：" ?<<?endl;?? ????Traverse(parent);?? ????cout?<<?endl;?? ?? ????BinaryTreeNode?*node1?=?(BinaryTreeNode?*)malloc(sizeof (BinaryTreeNode));?? ????BinaryTreeNode?*node2?=?(BinaryTreeNode?*)malloc(sizeof (BinaryTreeNode));?? ?? ????node1->m_nValue?=?0;?? ????node1->m_pLeft?=?NULL;?? ????node1->m_pRight?=?NULL;?? ?? ????node2->m_nValue?=?0;?? ????node2->m_pLeft?=?NULL;?? ????node2->m_pRight?=?NULL;?? ?? ????maxDistance(parent,?&max);?? ????cout?<<"max?distance?of?tree's?nodes?:?" ?<<?max?<<?endl;?? ?? ????InsertNodeAtMostRight(parent,?node1);?? ????maxDistance(parent,?&max);?? ????cout?<<"max?distance?of?tree's?nodes?after?insert?node1:?" ?<<?max?<<?endl;?? ?? ????InsertNodeAtMostRight(parent,?node2);?? ????maxDistance(parent,?&max);?? ????cout?<<"max?distance?of?tree's?nodes?after?insert?node2:?" ?<<?max?<<?endl;?? ?? ?????? ????maxDistance(node2,?&max);?? ????cout?<<"just?one?node?" ?<<?max?<<?endl;?? ?? ?????? ????maxDistance(node1,?&max);?? ????cout?<<"just?two?node?" ?<<?max?<<?endl;?? ????return ?0;?? }?? ?? BinaryTreeNode*?Construct(int ?*preorder,?int ?*inorder,?int ?lenght)?? {?? ????if ?(preorder?==?NULL?||?inorder?==?NULL?||?lenght?<=?0)??? ????{?? ????????return ?NULL;?? ????}?? ????return ?ConstructCore(preorder,?preorder?+?lenght?-?1,?inorder,?inorder?+?lenght?-?1);?? }?? ?? BinaryTreeNode*?ConstructCore(int ?*startPreorder,?int ?*endPreorder,?int ?*startInorder,?int ?*endInorder)?? {?? ????int ?rootValue?=?startPreorder[0];?? ????BinaryTreeNode?*root?=?new ?BinaryTreeNode();?? ????root->m_nValue?=?rootValue;?? ????root->m_pLeft?=?root->m_pRight?=?NULL;?? ?? ????if ?(startPreorder?==?endPreorder)??? ????{?? ????????if ?(startInorder?==?endInorder?&&?*startPreorder?==?*startInorder)??? ????????{?? ????????????return ?root;?? ????????}?? ????????else ?? ????????{?? ????????????cout?<<?"Invalid?input" ?<<?endl;?? ????????????exit(-1);?? ????????}?? ????}?? ?? ????int ?*rootInorder?=?startInorder;?? ????while ?(rootInorder?<=?endInorder?&&?*rootInorder?!=?rootValue)??? ????{?? ????????++rootInorder;?? ????}?? ????if ?(rootInorder?<=?endInorder?&&?*rootInorder?!=?rootValue)??? ????{?? ????????cout?<<?"Invalid?input" ?<<?endl;?? ????????exit(-1);?? ????}?? ?? ????int ?leftLength?=?rootInorder?-?startInorder;?? ????int ?*leftPreorderEnd?=?startPreorder?+?leftLength;?? ?? ????if ?(leftLength?>?0)??? ????{?? ????????root->m_pLeft?=?ConstructCore(startPreorder?+?1,?leftPreorderEnd,?startInorder,?rootInorder?-?1);?? ????}?? ????if ?(leftLength?<?endPreorder?-?startPreorder)??? ????{?? ????????root->m_pRight?=?ConstructCore(leftPreorderEnd?+?1,?endPreorder,?rootInorder?+?1,?endInorder);?? ????}?? ?? ????return ?root;?????? }?? ?? void ?Traverse(?BinaryTreeNode?*?root)??{?? ????if ?(root?==?NULL)??? ????{?? ????????return ;?? ????}?? ????else ?? ????{?? ????????Traverse(root->m_pLeft);?? ????????Traverse(root->m_pRight);?? ????????cout?<<?root->m_nValue?<<?"??" ;?? ????}?? }?? int ?maxDistance(BinaryTreeNode?*root,?int ?*max)??{?? ?????? ????if ?(root?==?NULL?||?max?==?NULL)??? ????{?? ????????return ?-1;?? ????}?? ????*max?=?0;?? ????return ?DistanceCore(root,?max);?? }?? ?? int ?DistanceCore(BinaryTreeNode?*root,?int ?*max)??{?? ?????? ????if ?(root->m_pLeft?==?NULL?&&?root->m_pRight?==?NULL)??? ????{?? ????????return ?0;?? ????}?? ?? ?????? ????int ?lDistance?=?0;?? ????int ?rDistance?=?0;?? ?? ?????? ????if ?(root->m_pLeft?!=?NULL)??? ????{?? ????????lDistance?=?1?+?DistanceCore(root->m_pLeft,?max);?? ????}?? ?? ????if ?(root->m_pRight?!=?NULL)??? ????{?? ????????rDistance?=?1?+?DistanceCore(root->m_pRight,?max);?? ????}?? ?? ?????? ????if ?(lDistance?+?rDistance?>?*max)??? ????{?? ?????????? ????????*max?=?lDistance?+?rDistance;?? ????}?? ?????? ????return ?lDistance?>?rDistance???lDistance?:?rDistance;?? }?? ?? ?? ?? int ?InsertNodeAtMostRight(BinaryTreeNode?*?root,?BinaryTreeNode?*?node)??{?? ????if ?(root?==?NULL?||?node?==?NULL)??? ????{?? ????????return ?-1;?? ????}?? ?? ????while ?(root->m_pRight?!=?NULL)??? ????{?? ????????root?=?root->m_pRight;?? ????}?? ?? ????root->m_pRight?=?node;?? ????return ?0;?? }?
總結
以上是生活随笔 為你收集整理的二叉树分析(两点最大距离) 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
