Erlang程式设计与问题解决/树

计算机科学 > 编程 > Erlang程式设计与问题解决

树结构是将几个节点连通，使每一个节点对其他每一个节点的连通路径各只有一条。树符合下列性质。

1. 空集合是树。
2. 以一个节点做为树根，其下拥有若干子树，这样也是树。

以下由一个二元树的定义开始，介绍 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 函数，对指定的二元搜寻树求平均走访次数。提示：你须要取出树的全部节点，并分别使用每个节点走访这株树；将每个走访次数加总求平均。