佈局二叉搜索樹

Question

這是鑑於這樣的二進制搜索和佈局它OCaml 99

問題65：

---

的y軸節點很容易，因爲它只是級別編號，從1開始。

節點的x asix稍微複雜一點，但通過觀察，假設整個樹的高度爲h，那麼節點的x就是左邊的最大大小，就好像它是一棵滿樹， x = 2^(h-y)-1

但是，還有一個特殊情況，其中最左邊的節點的x始終是我們需要處理的。

這裏是我的代碼：

type 'a btree = Empty | Node of 'a * 'a btree * 'a btree 

type 'a pos_binary_tree = 
    | E (* represents the empty tree *) 
    | N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree 

let rec height = function 
    | Empty -> 0 
    | Node (_,l,r) -> 1 + max (height l) (height r) 

let get_fullsize h level = (2. ** (Float.of_int (h+1-level)) |> Int.of_float) - 1 

let layout_btree2_correct t = 
    let h = height t in 
    let rec lay off y = function 
    | Empty -> get_fullsize h y, E 
    | Node (w, Empty, r) when off = 0 -> 
     let wtr, newr = lay 1 (y+1) r in 
     1+wtr, N (w, 1, y+1, E, newr) 
    | Node (w, l, r) -> 
     let wt1, newl = lay off (y+1) l in 
     let wt2, newr = lay (off+wt1+1) (y+1) r in 
     wt1+wt2+1, N (w, off+wt1+1, y, newl, newr) 
    in 
    lay 0 1 t |> snd 

---

我確實是：

1. 得到整個樹的高度
2. 總是返回回全寬，它可能佔用
3. x應該是左節點寬度+ 1
4. 對於最左邊的節點的特殊情況下，返回1個+寬的權利，寬度

在我的方式，我必須先前往樹一次得到的高度。任何人都可以建議更好的實施，例如，只是一次旅行樹？

Answer 1

您是否要求使用不同的算法來搜索樹？或者不同的方式來實現該算法？

樹和樹算法部分可能會對您有所幫助。 http://interactivepython.org/runestone/static/pythonds/index.html