排序二叉樹F＃

Question

您好我一直在尋找一些關於如何在F＃中創建一個排序的二叉樹數據類型的好消息，但是我無法找到任何可以理解的東西。我檢查了msdn頁面上的例子，但我沒有得到它。

Answer 1

如果你正在尋找一個現有的實現，那麼the FSharpX library有很多數據結構（包括一些樹）可用。雖然我不認爲它有一個簡單的排序二叉樹實現。你也可以訪問所有來自F＃的.NET集合，但我不認爲.NET也有二叉樹。它有sorted list，這可能對你來說很好，這取決於你想要做什麼。

如果你想實現自己的，那麼你需要通過定義的數據類型開始代表樹：

type SortedTree<'T when 'T : comparison> = 
    | Node of SortedTree<'T> * 'T * SortedTree<'T> 
    | Leaf of 'T 

的Node元素意味着左邊的所有值都大於存儲的值越小在節點中，所有更大（或相等）的值都在右邊。我添加了一個約束條件'T : comparison，這意味着您只能創建可比較元素的樹（這在實現中需要對樹進行排序）。

實現所有常見的樹操作將是相當多的工作，但是在插入一個簡單的嘗試（不保持任何形式營養均衡的樹）看起來是這樣的：

let rec insert element tree = 
    match tree with 
    | Leaf v when element < v -> Node(Leaf element, v, Leaf v) 
    | Leaf v -> Node(Leaf v, element, Leaf element) 
    | Node(left, key, right) when element < key -> Node(insert element left, key, right) 
    | Node(left, key, right) -> Node(left, key, insert element right) 

的模式匹配處理4個有趣的案例：當樹是Leaf時，您需要使用左側或右側的新元素構建新節點。當樹是Node時，則要根據鍵的值向左或向右插入。