Erlang程式設計與問題解決/樹
樹結構是將幾個節點連通，使每一個節點對其他每一個節點的連通路徑各只有一條。樹符合下列性質。
- 空集合是樹。
- 以一個節點做為樹根，其下擁有若干子樹，這樣也是樹。
以下由一個二元樹的定義開始，介紹 Erlang 如何實作樹及演算法。
二元樹
[編輯]樹的基本構成，有兩種情況：
nil % 空集合
{Root, Left, Right} % 有樹根、左子樹和右子樹
先有一個最簡單的樹生產式 create/1 ，產生 N 個節點並且大致平衡的樹。用 x 標示節點位置。
-module(binary_tree).
-compile(export_all).
create(0) ->
nil;
create(N) ->
Half = (N-1) div 2,
{x, create(Half), create(N-1-Half)}.
> binary_tree:create(6).
{x,{x,nil,{x,nil,nil}},{x,{x,nil,nil},{x,nil,nil}}}
上述程式提供了雛型，讓我們可以由簡單的結果檢查程式是否運作良好。我們可以轉抄上述程式的框架，寫成資料妥善分配的版本。
create([]) ->
nil;
create([X|Xs]) ->
Half = (length(Xs)-1) div 2,
{Left, Right} = split_at(Half, Xs),
{ X, create(Left), create(Right) }.
split_at(0, Xs) ->
{[], Xs};
split_at(N, [X|Xs]) ->
{Ys, Zs} = split_at(N-1, Xs),
{[X|Ys], Zs}.
程式執行結果為：
> binary_tree:create([a,b,c,d]).
{a,{b,nil,nil},{c,nil,{d,nil,nil}}}
接着還可以寫一些函數檢查樹的一些屬性：例如， height/1 檢查樹高度， node_count/1 檢查節點數目， node_count_at/2 檢查某一層的節點數目。
height(nil) ->
0;
height({_,L,R}) ->
1 + erlang:max(height(L), height(R)).
node_count(nil) ->
0;
node_count({_,L,R}) ->
1 + node_count(L) + node_count(R).
node_count_at(_, nil) ->
0;
node_count_at(1, {_,_,_}) ->
1;
node_count_at(Level, {_,L,R}) ->
node_count_at(Level-1, L) + node_count_at(Level-1, R).
接着，接到一個列表，產生全部可能的樹，程式如下：
all_trees([]) ->
[nil];
all_trees([X|Xs]) ->
[ {X, L, R}
|| {Ls, Rs} <- [ split_at(Half,Xs)
|| Half <- lists:seq(0,length(Xs))],
L <- all_trees(Ls),
R <- all_trees(Rs) ].
稍做修改，可以求全部可能的樹的高度：
all_trees_height([]) ->
[0];
all_trees_height([_|Xs]) ->
[ 1 + erlang:max(Ln,Rn)
|| {Ls, Rs} <- [ split_at(Half,Xs)
|| Half <- lists:seq(0,length(Xs))],
Ln <- all_trees_height(Ls),
Rn <- all_trees_height(Rs) ].
平衡樹
[編輯]平衡樹，又叫做自我平衡樹，有好幾種類別。其中一種稱為 AVL tree ，是指在樹的左子樹與右子樹的高度，最多不相差超過 1 。
AVL 樹
[編輯]現在，要做的問題是，給一個列表，產生可能構成的 AVL 樹。我們已經有一個 all_tree/1 可以產生一個列表全部可能有的樹。對每一株樹，我們可以有 is_avl_tree/1 判斷是否為 AVL 樹。
is_avl_tree(nil) ->
true;
is_avl_tree({_,L,R}) ->
case height(L) - height(R) of
0 ->
is_avl_tree(L) and is_avl_tree(R);
1 ->
is_avl_tree(L) and is_avl_tree(R);
-1 ->
is_avl_tree(L) and is_avl_tree(R);
_ ->
false
end.
於是，使用 lists 模組的 filter 函數，可以根據指定的準則，將符合的結果找出。我們可以找出全部的 AVL tree 。
avl_trees(Xs) ->
lists:filter(
fun(T) -> test:is_avl_tree(T) end,
all_trees(Xs)
).
> binary_tree:avl_trees([a,b,c,d]).
[{a,{b,nil,nil},{c,nil,{d,nil,nil}}},
{a,{b,nil,nil},{c,{d,nil,nil},nil}},
{a,{b,nil,{c,nil,nil}},{d,nil,nil}},
{a,{b,{c,nil,nil},nil},{d,nil,nil}}]
完整樹
[編輯]接下來討論另一種平衡樹：完整樹 ( complete tree ) 。完整樹是在它最高高度以下的任何一層中，能夠補滿節點的位置都補滿了。而在樹的最高一層，所有的節點全部向左靠齊，留下右邊全都是 nil 。或者，最高的一層也全部補滿。
從上述建構樹的程式的思路走來，我們發現，上述的樹建構都思考子樹本身的局部情況。然而，來處理完整樹時，你必須思考自己子樹和其他子樹的一些節點的情況。所以，在此要寫一些新的函數。
level_at/2 是從樹中取出指定層次的一列節點；要注意的是，把一層裏沒有節點的位置填上 nil ：
level_at(1, nil) ->
[nil];
level_at(1, {Rt,_,_}) ->
[Rt];
level_at(N, nil) when N > 1 ->
level_at(N-1, nil) ++ level_at(N-1, nil);
level_at(N, {_,L,R}) when N > 1 ->
level_at(N-1, L) ++ level_at(N-1, R).
對最高高度以下的任何一層，用 check_level_full/1 檢查列表中全部填滿節點，也就是沒有 nil ：
check_level_full([]) ->
true;
check_level_full([nil|_]) ->
false;
check_level_full([_|Ns]) ->
check_level_full(Ns).
對最高高度一層，用 check_level_complete/1 檢查列表中的節點全部向左靠齊：
check_level_complete([]) ->
true;
check_level_complete([_]) ->
true;
check_level_complete([nil,Node|_]) when Node /= nil ->
false;
check_level_complete([_|Ns]) ->
check_level_complete(Ns).
於是，檢查一株樹是不是完整樹，作法是先取樹高，接着求低於樹高的每一層都是填滿節點，最後求最高層節點都向左靠齊：
check_complete_tree(nil) ->
true;
check_complete_tree(T) ->
Height = height(T),
check_full_level_at([ level_at(H,T) || H <- lists:seq(1,Height-1) ])
andalso check_complete_level_at(Height, T).
check_complete_level_at(H, T) ->
check_level_complete(level_at(H, T)).
check_full_level_at([]) ->
true;
check_full_level_at([Level|Ls]) ->
check_level_full(Level) andalso check_full_level_at(Ls).
使用下列主程式，先產生全部可能的樹，然後對每一株樹檢查並篩選出完整樹：
complete_trees(Xs) ->
lists:filter(
fun check_complete_tree/1,
all_trees(Xs)
).
% lists:filter/2 使用指定的檢查函數 fun check_complete_tree/1
% 判斷一個列表 all_trees(Xs) 中有哪些樹是完整樹。如果是，就篩選出來
執行情況為：
> binary_tree:complete_trees([a,b,c,d,e,f,g]).
[{a,{b,{c,nil,nil},{d,nil,nil}},{e,{f,nil,nil},nil}}]
> binary_tree:complete_trees([a,b,c,d,e,f,g,h]).
[{a,{b,{c,nil,nil},{d,nil,nil}},
{e,{f,nil,nil},{g,nil,nil}}}]
> binary_tree:complete_trees([a,b,c,d,e,f,g,h,i]).
[{a,{b,{c,{d,nil,nil},nil},{e,nil,nil}},
{f,{g,nil,nil},{h,nil,nil}}}]
> binary_tree:complete_trees([a,b,c,d,e,f,g,h,i]).
[{a,{b,{c,{d,nil,nil},{e,nil,nil}},{f,nil,nil}},
{g,{h,nil,nil},{i,nil,nil}}}]
- 練習題
- 最大堆積樹 ( max heap ) 有若干性質為： (1) 是樹，擁有樹的各種性質 (2) 任一子樹的左、右子樹每一節點都不大於樹根節點。請仿照本節的程式手法──產生並過濾──撰寫 max_heap:create/1 ，輸入一個數值列表，產生出各種可能的最大堆積樹。
二元搜尋樹
[編輯]二元搜尋樹是有序的樹結構，可以在其中以二元搜尋法尋找資料。首先，可以用最簡單的二部份來建構二元搜尋樹：關於列表的處理和節點的插入。
-module(bstree).
-compile(export_all).
create([]) ->
nil;
create([X|Xs]) ->
insert(X, create(Xs)).
insert(X, nil) ->
{X, nil, nil};
insert(X, {X, L, R}) ->
{X, insert(X, L), R};
insert(X, {Y, L, R}) when X > Y ->
{Y, L, insert(X, R)};
insert(X, {Y, L, R}) ->
{Y, insert(X, L), R}.
基本上已經可以將任何列表轉換為二元搜尋樹了。樹的結構由列表資料決定：例如，以下案例產生最糟情況的二元搜尋樹，看起來就像是鏈接串列。
> bstree:create([1,2,3,4,5,6,7,8]).
{8,
{7,{6,{5,{4,{3,{2,{1,nil,nil},nil},nil},nil},nil},nil},nil},
nil}
可想而知，須調整樹的平衡程度。
樹的平衡
[編輯]樹的調整步驟可分為樹左移和樹右移。以樹左移來說，是從樹的右子樹取最左端點當做新的樹根，同時將舊樹根插入左子樹，就得到左移一步的新樹。樹右移的步驟與樹左移對稱。
為了做到樹左右移，我們需要幾個函數： node_count/1 求子數的節點總數、 take_leftest/1 取出子樹最左端點並留下餘樹、 take_rightest/1 取出子樹最右端點並留下餘樹。
node_count(nil) ->
0;
node_count({_,L,R}) ->
1 + node_count(L) + node_count(R).
take_leftest(nil) ->
{nil, nil};
take_leftest({Rt,nil,R}) ->
{Rt, R};
take_leftest({Rt,L,R}) ->
{Node, Rest} = take_leftest(L),
{Node, {Rt, Rest, R}}.
take_rightest(nil) ->
{nil, nil};
take_rightest({Rt,L,nil}) ->
{Rt, L};
take_rightest({Rt,L,R}) ->
{Node, Rest} = take_rightest(R),
{Node, {Rt, L, Rest}}.
已知樹左移與樹右移如下列程式：
shl(nil) ->
nil;
shl({Rt,L,R}) ->
{Node, Rest} = take_leftest(R),
{Node, insert(Rt, L), Rest}.
shr(nil) ->
nil;
shr({Rt,L,R}) ->
{Node, Rest} = take_rightest(L),
{Node, Rest, insert(Rt, R)}.
則樹平衡為函數 balance/1 ：求左右子樹節點數目，當二子樹節點數目相差超過一個，就要做樹左移或樹右移；並且，二子樹也要做樹平衡。
balance(nil) ->
nil;
balance({Rt,L,R}) ->
Nl = node_count(L),
Nr = node_count(R),
if
Nl - Nr > 1 ->
balance(shr({Rt,L,R}));
Nr - Nl > 1 ->
balance(shl({Rt,L,R}));
true ->
{Rt, balance(L), balance(R)}
end.
二元搜尋樹的平衡情況如下例：
> bstree:balance(bstree:create([1,2,3,4,5,6,7,8])).
{5,
{3,{2,{1,nil,nil},nil},{4,nil,nil}},
{7,{6,nil,nil},{8,nil,nil}}}
- 練習一
- 以上述二元搜尋樹為例，撰寫 search/2 函數，在樹中尋找指定資料。當資料找到時，傳回 {Data, Traversal} ， Traversal 為走訪次數。 (由任一樹根走往左子樹樹根算走訪一次，同理，走往右子樹樹根也算走訪一次。) 如果找不到資料，傳回 {nil, Traversal} 。
- 練習二
- 撰寫 avg_traversal/1 函數，對指定的二元搜尋樹求平均走訪次數。提示：你須要取出樹的全部節點，並分別使用每個節點走訪這株樹；將每個走訪次數加總求平均。