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 函数,对指定的二元搜寻树求平均走访次数。提示:你须要取出树的全部节点,并分别使用每个节点走访这株树;将每个走访次数加总求平均。