樹中兩個(gè)結(jié)點(diǎn)的最低公共祖先

【補(bǔ)充條件】：

      樹是普通的樹，而且樹中的結(jié)點(diǎn)沒有指向父節(jié)點(diǎn)的指針。

針對(duì)上述的題目和條件，書中給出了如下解決方案。

【原方案】：

      使用兩個(gè)鏈表，對(duì)樹進(jìn)行兩次遍歷以查找兩個(gè)樹結(jié)點(diǎn)，并保持路徑到兩個(gè)鏈表中，從而將問題轉(zhuǎn)化為求兩個(gè)鏈表的最后一個(gè)公共結(jié)點(diǎn)。

從該方案中，觀察到兩次樹結(jié)點(diǎn)查找的遍歷中，其中一個(gè)結(jié)點(diǎn)的遍歷過的樹結(jié)點(diǎn)序列將完全覆蓋查找另一結(jié)點(diǎn)時(shí)所遍歷的樹結(jié)點(diǎn)序列。由此入手，本文提出了如下的改進(jìn)解決方案。

【改進(jìn)方案】：

    深度優(yōu)先遍歷樹，并記錄路徑，當(dāng)找到第一個(gè)結(jié)點(diǎn)后，在當(dāng)前基礎(chǔ)上繼續(xù)遍歷搜索第二個(gè)結(jié)點(diǎn)，并記錄第一個(gè)結(jié)點(diǎn)路徑的變化程度，直到找到第二個(gè)結(jié)點(diǎn)。最后，根據(jù)棧信息和記錄的結(jié)點(diǎn)路徑變化程度得到最低公共祖先。如圖1，假設(shè)輸入的兩個(gè)樹結(jié)點(diǎn)為D和K，樹的根節(jié)點(diǎn)為R，則求D和K的最低公共結(jié)點(diǎn)的過程如下表： 

步驟	棧	第一個(gè)結(jié)點(diǎn)	第二個(gè)結(jié)點(diǎn)	路徑變化程度
1	R	—	—	—
2	R，A	—	—	—
3	R，A，F	—	—	—
4	R，A，F，J	—	—	—
5	R，A，F，G	—	—	—
6	R，A，F，K	K	—	0（或K）
7	R，A，C	K	—	1（或A）
8	R，A，C，E	K	—	2（或A）
9	R，A，C，I	K	—	2（或A）
10	R，A，D	K	D	1（或A）
è 得出結(jié)果，最低公共祖先結(jié)點(diǎn)為A

從中，可以看到，改進(jìn)后的方案，只需對(duì)樹執(zhí)行一次遍歷。而在輔助空間的需求上， 只需使用一個(gè)棧（外加少量結(jié)點(diǎn)指針變量和1個(gè)表示路徑變化程度的整型變量）。而且，如果采用遞歸的方式實(shí)現(xiàn)，該棧所需保存的信息，還可以通過遞歸時(shí)的函數(shù)調(diào)用棧得以保存。

【附注】：

1. 此處，有如下一個(gè)問題：
   假設(shè)待查找公共祖先的兩樹結(jié)點(diǎn)，其中一結(jié)點(diǎn)在以另一結(jié)點(diǎn)為根的子樹上（包括兩結(jié)點(diǎn)相同）時(shí)，公共祖先的確定規(guī)則——
   “作為子樹根結(jié)點(diǎn)的那個(gè)結(jié)點(diǎn)”還是“子樹根結(jié)點(diǎn)的父節(jié)點(diǎn)”？
   例如：對(duì)上面圖1中的那棵樹，如果待查結(jié)點(diǎn)為根結(jié)點(diǎn)R和結(jié)點(diǎn)F，那么最終的查找結(jié)果是為R呢，還是因?yàn)?/span>R是根結(jié)點(diǎn)無父結(jié)點(diǎn)而得出NULL？
   此問題在書中未提及，但查看書中代碼，確認(rèn)是選擇了后者；而在本人的樣例代碼中則采用了前面的觀點(diǎn)。
2. 在樣例代碼中，對(duì)樹結(jié)點(diǎn)在棧中的存儲(chǔ)方式略有改動(dòng)。
3. 樣例代碼工程所使用的環(huán)境為 Visual C++ 2010；
   其中：tree.h/cpp為功能代碼文件，TestLowestCommonAncestor.h/cpp為相應(yīng)的UT代碼文件；
   UT采用gtest所編寫，編譯鏈接請(qǐng)根據(jù)gtest在自己本機(jī)的路徑狀況修改gtest_link.props文件中相應(yīng)的鏈接項(xiàng)。

posted on 2012-04-05 23:45 青碧竹 閱讀(3099) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法相關(guān)