排序二叉树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时，则要根据键的值向左或向右插入。