-1

我找到了一个从 preorder 构建的示例，如何从 post order 构建二叉树？

我编辑如下，是否正确

type BinaryTree = 
    | Nil 
    | Node of NodeType * BinaryTree * BinaryTree

let rec buildBSTfromPostOrder (l:NodeType list) = 
match l with
| [] -> Nil
| [a] -> Node(a, Nil, Nil)
| h::t -> 
    let b = Node(h, buildBSTfromPostOrder(t), buildBSTfromPostOrder(t))
    let smaller = 
               t 
               |> Seq.takeWhile (fun n -> n < h) 
               |> Seq.toList
    let bigger = 
               t 
               |> Seq.skipWhile (fun n -> n < h) 
               |> Seq.toList
    b


let input = [10; 1; 2; 2; 1; 50]
4

1 回答 1

1

你不能，如果你想从流（列表）中重建一些二叉树，必须至少使用两个。

有一个 Haskell 版本（非常接近 F#）

post [] _ = [] 
post (x:xs) ys = post (take q xs) (take q ys) ++         -- left
                 post (drop q xs) (drop (q + 1) ys) ++   -- right
                 [x]                                     -- node
    where (Just q) = elemIndex x ys

该函数从 pre 和 in order 重建 post order。可以适应其他版本。（键也应该是唯一的）

如果您的树是有序的（BST），那么只需用键填充树。

要填充您的 BST，您可以编写

let rec insert tree n =
    match tree with
    | Nil -> Node(n, Nil, Nil)
    | Node(x, left, right) -> if n < x then Node(x, insert left n, right)
                                       else Node(x, left, insert right n)

let populate xs = Seq.fold insert Nil xs

例子

let rec show tree =
    match tree with
    | Nil -> printf ""
    | Node(x, left, right) -> do printf "[%d;" x
                                 show left
                                 printf ";"
                                 show right
                                 printf "]"

do show <| populate [|1;6;4;8;2;|]
于 2013-07-10T09:44:59.003 回答