Fsharp F#中递归遍历二叉树的三种方式

Question

我一直在读这本很棒的书Functional Programming Using F#我刚读到关于有限树的章节，我注意到有三种遍历树的方法，但是我不明白为什么以及如何不同。这是代码。

type BinaryTree<'a> =
    |Leaf 
    |Node of BinaryTree<'a> * 'a * BinaryTree<'a>


let rec preorder (tr:BinaryTree<'a>) : 'a list =
    match tr with
    |Leaf            -> []
    |Node(trr,x,trl) -> x:: (preorder trr) @ (preorder trl) 


let rec inorder (tree:BinaryTree<'a>) : 'a list =
    match tree with
    |Leaf -> []
    |Node(tr,x,tl) -> (inorder tr) @ [x] @ (inorder tl)

let rec postorder (tree:BinaryTree<'a>) : 'a list =
    match tree with
    |Leaf -> []
    |Node(tr,x,tl) -> (postorder tr) @ (postorder tl) @ [x]

let someTree = Node(Leaf,20,Node(Leaf,40,Node(Node(Leaf,-2,Leaf),2,Node(Leaf,0,Leaf))))

preorder someTree
inorder someTree
postorder someTree

欢迎任何帮助！ :)

Answer 1

如果您运行自己的代码，您会看到结果的不同：

> preorder someTree;;
val it : int list = [20; 40; 2; -2; 0]
> inorder someTree;;
val it : int list = [20; 40; -2; 2; 0]
> postorder someTree;;
val it : int list = [-2; 0; 2; 40; 20]

因此，区别在于列表元素的顺序。

Answer 2

查看不同遍历方式中的拼接顺序：

前：x :: (preorder tl) @ (preorder tr)

x : 当前值
preorder tl : 访问左树
preorder tr : 访问右树

在：(inorder tl) @ [x] @ (inorder tr)

inorder tl : 访问左树
x : 当前值
inorder tr : 访问右树

Post: (postorder tl) @ (postorder tr) @ [x]

postorder tl : 访问左树
postorder tr : 访问右树
x : 当前值

如果您从树的顶部（根上方）开始追踪树 anti-clockwise：

Pre-order遍历returns元素按照先遇到每个节点left-hand边的顺序
In-order遍历returns元素按照先遇到每个节点底部的顺序
Post-order遍历returns元素按照先遇到每个节点right-hand边的顺序

作为简要概述，pre-order 遍历对于复制整棵树很有用，in-order 遍历对于二进制搜索很有用，post-order 遍历对于删除整棵树很有用。

可以在此处找到更多详细信息：https://en.wikipedia.org/wiki/Tree_traversal

Fsharp F#中递归遍历二叉树的三种方式

Three ways of traversing a binary tree recursively in Fsharp F#

tree

f#

types