Как построить двоичное дерево из почтового заказа

-1

Я нахожу пример сборки из preorder, как насчет того, как построить двоичное дерево из сообщения ?Как построить двоичное дерево из почтового заказа

я редактировать следующим образом, это правильно

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]

источник

2013-07-10 ControlPoly

Ваш код подразумевает есть еще одна деталь, которая не упоминается в этом вопросе. Кажется, это пост-порядок двоичного * поиска * дерева - это значит, что вы знаете, что уже происходит в обходном порядке. Это действительно так? – amit

@amit, я думаю, что BST в 'buildBSTfromPostOrder' подразумевает, что это двоичное дерево поиска :) – MisterMetaphor

Вы не используете' small' и 'large', знаете ли вы, куда они должны идти? –

Вы не можете, если вы хотите восстановить некоторые бинарное дерево из потоков (списков) должны использовать по крайней мере два.

Существует версия 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

Эта функция восстановить пост заказ от заранее и в порядке. Может быть адаптирован к другим версиям. (Ключи также должны быть уникальными)

Если ваше дерево заказано (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-10 09:44:59 josejuan

Как построить двоичное дерево из почтового заказа

ответ

Смежные вопросы