F#二叉树与树遍历

Question

因此，为了在操练主义上进行附带练习，我实现了一个BinarySearchTree。我对实现二叉树的创建很有信心。但我对这棵树的穿越不太确定。所以我想出了两种遍历算法的实现--哪一种是“更好”的解决方案？

我正在学习F#，因为我想学习函数式编程。这是代码审查-所以任何批评都欢迎！

module BinarySearchTree 

type Node<'a> =
    { Left: Node<'a> option
      Right: Node<'a> option
      Data: 'a }

let left (node: Node<'a>)  = node.Left

let right (node: Node<'a>) = node.Right

let data (node: Node<'a>) : 'a = node.Data

let rec insertNode (root: Node<'a> option) (nextValue: 'a) : Node<'a> =
    match root with
    | Some root -> if nextValue <= root.Data then { root with Left = Some(insertNode root.Left nextValue) }
                   elif nextValue > root.Data then { root with Right = Some(insertNode root.Right nextValue) }
                   else root
    | None -> { Left=None; Right=None; Data=nextValue }

let create (items: 'a list) : Node<'a> =
     items
     |> List.fold (fun (acc: Option<Node<'a>>) (item: 'a) -> Some(insertNode acc item)) None
     |> function
        | None -> failwith "Failed to construct binary tree. You must pass a valid item list."
        | Some root -> root  

let sortedData (node: Node<'a>) : ('a list) =
    let rec traverse (acc: 'a list) (node: Node<'a>)  =     
        match (node.Left, node.Right) with
        | Some left, Some right -> seq {
                                   yield! node.Data::acc
                                   yield! (traverse [] left)
                                   yield! (traverse [] right)}
                                   |> Seq.toList
        | Some left, None -> traverse (node.Data::acc) left
        | None, Some right -> traverse (node.Data::acc) right
        | None, None -> node.Data::acc

    List.sort (traverse [] node)

以及sortedData的替代实现：

let sortedData (node: Node) : (int list) =



 let rec traverse (acc: int list) (node: Node)  =     
        match (node.Left, node.Right) with
        | Some left, Some right -> (node.Data::acc)@(traverse [] left)@(traverse [] right) 
        | Some left, None -> traverse (node.Data::acc) left
        | None, Some right -> traverse (node.Data::acc) right
        | None, None -> node.Data::acc

    List.sort (traverse [] node)

Answer 1

通常，在F#中，我们尽量减少对函数参数使用显式类型声明：

let left (node: Node<'a>) = node.Left

变成了

let left node = node.Left

等。

函数insertNode违反了单一责任原则，如果root = None，则创建一个新的树/根节点，而不是实际插入值。

我个人不允许root成为Option/None

相反，我将提供一个名为newTree的函数，它以一个'a值作为参数并返回一个Node<'a>

let rec insertNode (root: Node<'a> option) (nextValue: 'a) : Node<'a> = ...

通常，您应该将模块的对象作为函数的最后一个参数，以便使用管道操作符：

let rec insertNode value root =...

root |> BinarySearchTree.insertNode value

sortedData看起来过于复杂了--也许是因为List.sort的使用。原则上，它只是深度优先搜索(dfs)，您可以为每个节点连接左子节点中的值，并将节点本身的值与右子节点中的值连接起来：

关于清单，可以是：

let toList root =
    let rec dfs optNode =
        match optNode with
        | Some node -> (dfs (left node))@(data node::dfs (right node))
        | None -> []

    dfs (Some root)

或者如果您喜欢一个序列(我喜欢)：

let toSeq root =
    let rec dfs optNode =
        match optNode with
        | Some node -> seq {
            yield! dfs (left node)
            yield data node
            yield! dfs (right node)
            }
        | None -> Seq.empty

    dfs (Some root)

我将函数称为toList和toSeq。也许toOrderedList/Seq是更好的名字。

您可以考虑使用List-module而不是create items函数来扩展toBinaryTree items。这样就可以写：

let data = [ 5; 8; 1; 5; 1; 2; 2; 4; 6; 3 ]
let root = data |> List.toBinaryTree

这可能更直观

在create items函数中，您应该考虑对项进行排序，并执行二进制插入，以创建平衡树，因为如果您提供了一个已排序的项列表，那么您的函数只会使用一个子节点而不是一个树生成一个单一链接的节点列表。

您应该考虑提供一个能够平衡现有树的函数。

作为作为记录类型的Node<'a>类型的替代，可以考虑使用以下定义将其定义为受歧视的联合类型：

type Node<'a> =
    | Empty
    | Node of Data:'a * Left:Node<'a> * Right:Node<'a>

这更符合F#的功能风格，您的函数变得更加简单和直观：

module BinaryTree =

let data = function Empty -> failwith "Empty Tree" | Node (d, _, _) -> d
let left = function Empty -> Empty | Node (_, l, _) -> l
let right = function Empty -> Empty | Node (_, _, r) -> r

let first root = 
    let rec goLeft node =
        match node with
        | Empty -> None
        | Node (d, ln, _) ->
            match ln with
            | Empty -> Some d
            | Node _ -> goLeft ln

    goLeft root

let last root = 
    let rec goRight node =
        match node with
        | Empty -> None
        | Node (d, _, rn) ->
            match rn with
            | Empty -> Some d
            | Node _ -> goRight rn

    goRight root

let rec insert data root =
    match root with
    | Empty -> Node(data, Empty, Empty)
    | Node (d, l, r) ->
        match data <= d with
        | true -> Node (d, l |> insert data, r)
        | false -> Node (d, l, r |> insert data)

let toOrderedSeq root =
    let rec dfs node =
        match node with
        | Empty -> Seq.empty
        | Node (d, ln, rn) -> seq {
                yield! dfs ln
                yield d
                yield! dfs rn
            }

    dfs root


module List =
    let toBinaryTree data = data |> List.fold (fun n x -> n |> BinaryTree.insert x) Empty

正如所见，使用option是不必要的，而且insert函数是一致的，因为Empty节点作为root也是Node<'a>/Tree --只是没有任何元素。