f# - 排序二叉树 F#

Question

嗨，我一直在寻找一些关于如何在 F# 中制作排序二叉树数据类型的好信息，但我找不到任何可以理解的内容。我已经检查了 msdn-page 上的示例，但我不明白。

Answer 1

如果您正在寻找现有的实现，那么FSharpX 库有相当多的数据结构（包括一些树）可用。虽然我不认为它有一个排序二叉树的简单实现。您还可以从 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，则要根据键的值向左或向右插入。