如何建立从职务序列二叉树 [英] how to build binary tree from post order

问题描述

我找到一个例子构建preorder，如何如何建立从后二叉树 订购？

我的编辑如下，它是正确的。

 键入二叉树=
    |零
    |节点类型是节点*二叉树*二叉树

让拍摄buildBSTfromPostOrder（L的NodeType名单）=
比赛l当
| []  - ＆GT;零
|并[a]  - ＆GT;点（A，无，无）
| ^ h ::笔 - ＆GT;
    令b =节点（h时，buildBSTfromPostOrder（吨），buildBSTfromPostOrder（t））的
    让小=
               Ť
               |＆GT; Seq.takeWhile（有趣N  - ＆GT; N＆LT; H）
               |＆GT; Seq.toList
    让大=
               Ť
               |＆GT; Seq.skipWhile（有趣N  - ＆GT; N＆LT; H）
               |＆GT; Seq.toList
    b


让输入= 10; 1; 2; 2; 1; 50]
 

解决方案

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

有一个Haskell的版本（非常封闭的F＃）

 发布[] _ = []
帖子（X：XS）YS =后（取q XS）（坐q YS）+  - 左
                 后期（下降q XS）（下降（Q + 1）YS）+  - 右
                 [X]  - 节点
    其中，（只是Q）= elemIndex x伊苏
 

这是pre和为了使功能重构职务序列。可以适于其他版本。 （钥匙应该是独有太）

如果你的树是有序（BST），那么，只需填充树的钥匙。

要填充您的BST，你可以写

 让REC插入树N =
    匹配树
    |无 - ＆GT;节点（N，无，无）
    |节点（X，左，右） - ＆GT;如果n＆LT; x然后节点（X，插入左N，右）
                                       其他节点（X，左，右插N）

让填充XS = Seq.fold插入无XS
 

例如

 让REC秀树=
    匹配树
    |无 - ＆GT; printf上
    |节点（X，左，右） - ＆GT;这样做的printf[％D; x
                                 显示左
                                 printf的;
                                 显示正确的
                                 printf的]

做节目＆LT; |填充[| 1; 6; 4; 8; 2; |]
 

I find an example build from preorder, how about how to build binary tree from post order ?

i edit as following, is it correct

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]

解决方案

You can't, if you want reconstruct some binary tree from streams (lists) must use at least two.

There is a Haskell version (very closed to 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 

That function reconstruct post order from pre and in order. Can be adapted to other versions. (The keys should be uniques too)

If your tree is ordered (BST) then, simply populate tree with keys.

To populate your BST, you can write

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

example

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;|]

这篇关于如何建立从职务序列二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！