-1

プレオーダーからのビルド例を見つけましたが、ポスト オーダーからバイナリ ツリーをビルドするにはどうすればよいですか?

私は次のように編集します、それは正しいですか

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

ストリーム（リスト）からバイナリツリーを再構築したい場合は、少なくとも2つを使用する必要があります。

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 から post オーダーを順番に再構築します。他のバージョンに適応することができます。(キーも一意である必要があります)

ツリーが順序付けられている (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 に答える