如果每個節點的兩個子樹大小相等，則二叉樹是完整的。定義一個函式來決定二叉樹是否完整。
下Leaf a == Node a一段代碼不知道怎么寫，我覺得是，然后輸出一個布林值。
我的 Haskell 代碼如下所示：
data Tree a = Leaf a | Node a [Tree a]
judcomplete :: Tree a -> Tree a -> Bool
judcomplete (Leaf x) (Node y (Leaf z)) = Leaf x == Node y (Leaf z)
uj5u.com熱心網友回復：
基于@Will-Ness 的資料型別和解決方案，我們可以采用類似但可能更有效的方法。
這個想法是為了使一棵樹完整，每個子樹都必須完整。我們可以考慮后序深度優先搜索，我們檢查每個子樹的條件并將其傳遞給它們的父樹。
我們需要檢查的條件是：
- 兩個子樹中的節點數是否相等？
- 子樹的子樹有這種情況嗎？
請注意，我們需要來自每個子樹的兩種型別的資訊，一種是該子樹中的節點數，以便將其與另一棵子樹中的節點數進行比較，另一種是一個 bool 標志，指示如何這個相等的測驗是在那個分支的子樹中。
這導致遞回解決方案，基本情況為Leaf. 葉子有一個直接的答案：根據定義它是完整的并且有 0 個節點。所以，我們可以(True, 0)從所有的Leafs回傳。無Leaf節點做兩件事，比較左右子樹中的節點數以及它們的布林值。如果這 3 個條件都為真，則將標志設定為真，否則為假。它們還添加子樹中的節點數并將它們加一。
這導致了一個O(n)解決方案，其中n是樹中的節點數。我想我們也可以實作它，讓它懶洋洋地擺脫它，一路發現一個錯誤，而不用深入遞回呼叫。
data Tree a = Leaf a | Node a (Tree a) (Tree a)
judComplete :: Tree a -> Bool
judComplete x = fst $ go x where
go (Leaf _) = (True, 0)
go (Node _ left right) = (leftTrue &&
rightTrue &&
leftCount == rightCount,
1 leftCount rightCount) where
(leftTrue, leftCount) = go left
(rightTrue, rightCount) = go right
uj5u.com熱心網友回復：
首先，您的資料型別不正確。它顯示了一個多路樹，而問題是關于二叉樹。
二叉樹的節點有兩個分支。
data Tree a = Leaf a | Node (Tree a) (Tree a)
-- left right
現在，只說你已經知道是真的。
一棵只有葉子的樹是完整的。
complete (Leaf _) = True
一個節點表示的樹只有在它的兩個分支都是完整的并且具有相同的大小/深度時才是完整的：
complete (Node l r) = complete l && complete r
&& sameDepth [l,r]
所以事實證明（當我開始輸入這個答案(*)時我不知道這一點）sameDepth將按級別探索樹！如果當前關卡中的所有樹都是葉子，那么原始樹中所有路徑的深度都相同：
sameDepth level = allLeaves level ||
否則，我們必須在下一次迭代中代替每個節點的兩個分支。這個迭代步驟必須受到關卡中所有樹都是節點的條件的保護（為什么？）：
allNodes level && sameDepth (replaceWithBranches level)
如果關卡中的樹是混合的——有些是葉子，有些是節點，那么原始樹是不完整的：
|| False
sameDepth定義到此結束。
現在所剩下的就是執行allLeaves，allNodes和replaceWithBranches。這應該很容易用串列推導或直接遞回來完成。
以上可能是非常低效的（看看為什么？在哪里？嚴重低效通常來自多次做同樣的事情）。也許你可以在這方面改進它。（提示：您根本不需要添加任何內容，只需洗掉即可）。
還要說服自己這是正確的（或不正確）。
(*)這也是你可以做到的。不要驚慌！不要認為您必須從一開始就知道整個解決方案——這樣您就不會撰寫一行代碼。相反，只需陳述一些必須是真實的明顯事實。代碼以這種方式自行撰寫——我們使用我們希望存在的不存在的函式，這就是我們發現需要撰寫哪些函式的方式。
優化可以稍后來。它甚至可以以完全重寫的形式出現（盡管情況并非如此——只要您洗掉不需要的部分，該演算法就是最佳的）。重要的是不要阻止自己撰寫即使是效率最低的代碼。只要它“顯然”是正確的。稍后將通過等效轉換進行優化。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/316816.html
標籤：哈斯克尔
下一篇：如何原子地修改可變陣列中的值？