二叉樹廣度優先搜索

我正在使用OCaml。我有型：二叉樹廣度優先搜索

type 'a bt = Empty | Node of 'a * 'a bt * 'a bt;;

我也有例如BST：

let tree = Node(1,Node(2,Node(4,Empty,Empty),Empty),Node(3,Node(5,Empty,Node(6,Empty,Empty)),Empty));

我需要寫功能：breadthBT : 'a bt -> 'a list這將是廣度優先搜索遍歷。對於上面的示例樹，它應該返回[1; 2; 3; 4; 5; 6]

如何編寫該函數？我只能寫以下其使用DST功能：

let rec breadthBT tree = 
if tree=Empty then [] 
else let Node(w,l,r)=tree in (w::breadthBT l)@breadthBT r;;

以上函數返回（例如樹）[1; 2; 4; 3; 5; 6]。但我不能編寫使用BFS的功能。你可以幫幫我嗎？

來源

2012-10-19 Paul

我同意上一次ocaml問題的評論：「我認爲通常的家庭作業規則是你應該顯示一些你已經嘗試過的代碼，沒有什麼可以評論的，如果不解決問題就很難提供幫助「。 – jrouquie

這不是一個可編譯的解決方案。只是一個小費。您應該從頂級根節點迭代到深層節點。讓我們的函數接收累加器的答案和節點列表（您的'a bt值）作爲第二個參數。您可以通過獲取三元組的第一個元素來映射此列表，並且您可以收到答案的下一部分。你也需要評估下一層樹。對於每個節點，最多有兩個後代。您可以映射您的列表並應用_a_function_接收後代列表。它將成爲你樹的下一層。而不是---遞歸。

A不會指定這個_a_function_。嘗試研究谷歌中的concatMap。

快樂黑客！

來源

2012-10-19 22:27:08 Kakadu

謝謝，明天我會檢查 – Paul

想象一下，你把你的鼻子插在樹上。沒有在記事本中添加書籤位置，是否有可能以廣度優先的方式遍歷樹？不，因爲訂單可以讓你從一個分支跳到另一個不相關的分支。所以你需要一個記事本和「剩餘位置訪問」。你從記事本中選擇下一個剩餘的位置並盲目地跳到它。由於您從記事本中刪除了訪問位置，因此您尚未訪問過的節點。既然你不能在沒有訪問中間節點的情況下起牀樹，你還沒有訪問你上面的兩個節點。但你抵制本能直接攀登分支 - 哎，這是寬度第一順序。你不想忘記這兩個未訪問的節點，所以你想把它們放到筆記本中。你把它們放在筆記本前面或背面？當然，否則你會立即選擇其中一個，這就是我們想要避免的。 Et瞧：你的記事本是一個FIFO隊列的節點，你保持（即通過）作爲一個累加器，但也消耗挑選一個子樹訪問。

來源

2012-10-20 09:56:07 lukstafi

二叉樹廣度優先搜索

回答

相關問題