給定一個N元樹,找出它是否對稱於通過樹的根節點繪製的線。在二叉樹的情況下很容易做到這一點。然而,對於N-ary樹,它似乎很難N元樹 - 它是否對稱
回答
這並不困難。我打算用這個問題打高爾夫球。我得到7 ...任何人都變好了?思考這個問題
data Tree = Tree [Tree]
symmetrical (Tree ts) =
(even n || symmetrical (ts !! m)) &&
all mirror (zip (take m ts) (reverse $ drop (n - m) ts))
where { n = length ts; m = n `div` 2 }
mirror (Tree xs, Tree ys) =
length xs == length ys && all mirror (zip xs (reverse ys))
一種方法是發現樹是對稱的,如果它是它自己的倒影,其中一棵樹的反射是遞歸定義:
- 空的反射樹本身。
- 具有根r和子c1,c2,...,cn的樹的反射是具有根r並且子反射(cn),...,reflect(c2),reflect(c1)的樹。
然後,您可以通過計算樹的反射並檢查它是否等於原始樹來解決此問題。這又可以遞歸地完成:
- 空的樹只等於它自己。
- 具有根r和子元素c1,c2,...,cn的樹等於另一棵樹T,如果另一棵樹非空,具有根r,具有n個子元素,並且子元素等於c1,...。 ..,cn按此順序。
當然,這樣做效率有點低,因爲它在進行比較之前完全複製了樹。內存使用量爲O(n + d),其中n是樹中保存副本的節點數量,d是樹的高度(在遞歸tom檢查中是否保持相等)。由於d = O(n),所以使用O(n)存儲器。然而,它運行在O(n)時間,因爲每個階段只訪問一次節點。
這樣做是使用下面的遞歸形式的更節省空間的方法:
1. The empty tree is symmetric.
2. A tree with n children is symmetric if the first and last children are mirrors, the second and penultimate children are mirrors, etc.
然後,您可以定義兩棵樹是鏡子如下:
- 空樹只是其本身的一面鏡子。
- 具有根r和子c1,c2,...,cn的樹是具有根t和子d1,d2,...,dn的樹的鏡像iff r = t,c1是dn的鏡像,c2是dn-1的鏡像等等。
這種方法也運行在線性時間,但是並不構成樹的完整副本。因此,內存使用量只有O(d),其中d是樹的深度。這是最壞的O(n),但很可能要好得多。
堆棧 現在每次開始遍歷根節點時, 現在遞歸地調用一個函數,並在特定級別上逐個推送左子樹的元素。 維護一個全局變量並在每次將一個左子樹推入堆棧時更新它的值。現在遞歸地調用(在遞歸調用左子樹之後)右子並彈出每個正確匹配。這將確保它是以對稱方式進行檢查。
最後,如果堆棧爲空,所有的元素都被處理了,堆棧的每個元素都被彈出來了......你已經完成了!
我只是在左邊的子樹上按順序遍歷樹(節點向左)並將它保存到列表中。然後在右邊的子樹上再次按順序遍歷樹(node right left)並將其保存到列表中。然後,你可以比較兩個列表。他們應該是一樣的。
您的回覆以某種方式假定對稱是指數據而不是結構。爲了更容易的視覺化:如果滿足以下條件,則BST是對稱的:布爾hasStructuralSymmetry(節點a,節點b)如果(null == a && null == b) 返回true;如果(null == a || null == b) return false; return hasStructuralSymmetry(a.left,b.right) && areIdentical(a.right,b.left);}從http://geekviewpoint.com/BST_code_in_Java/複製 – kasavbere 2012-03-11 23:05:22
- 1. N元樹等於
- 2. 尋找n元樹
- 3. Python中的N元樹
- 4. Haskell n元樹遍歷
- 5. n元樹搜索功能
- 6. C中的N元樹C
- 7. 替換n元樹中的元素
- 8. 設計緩存優化的N元樹
- 9. 反向樹掃描,它是否可行?
- 10. 如何在C中摺疊n元樹#
- 11. 從CSV文件實例化N元樹
- 12. 檢查元素是否在樹中
- 13. 析構函數的n元樹結構
- 14. n元樹中的最小節點
- 15. Python的 - 壓扁它有N個兒童(N叉樹)
- 16. 紅寶石 - 遞歸對於每個n元樹
- 17. git是否有「相對」的樹狀?
- 18. 將N元表達式樹轉換爲二叉樹
- 19. N元樹插入和搜索的複雜性是什麼?
- 20. Deserilizing N叉樹
- 21. Perl中是否有一個n-tree樹實現?
- 22. 檢查兩個n-ary樹在Haskell中是否相等
- 23. Mips:驗證矩陣是否是對稱的
- 24. Python - 將n元樹轉換爲二叉樹
- 25. 從N元素的元組到N/2對的元組
- 26. 是否有按名稱選擇元素?
- 27. 是否有XSLT名稱元素?
- 28. 混疊規則是否對稱?
- 29. 是否可以通過不同的名稱多次關聯記錄N-N?
- 30. 用於遞歸下降解析的C++ n元樹實現
你認爲在分析一個N-ary樹時增加了很大的難度?我能看到的唯一困難的部分基本上是一個任意決定的問題:假定根節點可以有N個後代,那麼您究竟如何決定在「該行」的左側和右側考慮哪些? – 2010-02-23 04:49:41