Wednesday, April 14, 2010

Binary Trees in Erlang

More Erlang goodness, today binary trees!

The record which describes a node

-record(node, {left=nil, load, right=nil}).


Insertion and preorder

-module(binary_tree).
-export([newnode/1, insert/2, preorder/1]).
-import(lists).
-include("binary_tree.hrl").

newnode(Load) ->
#node{load=Load}.

newleaf(Load) ->
{leaf, Load}.

isnil(Node) ->
Node == nil.

insert({leaf, LeafLoad}, Load) ->
if
LeafLoad > Load ->
#node{left=newleaf(Load), load=LeafLoad};
LeafLoad =< Load ->
#node{load=LeafLoad, right=newleaf(Load)}
end;
insert(#node{left=LeftNode,
load=CurrentLoad,
right=RightNode} = Node,
Load) ->
if
CurrentLoad > Load ->
case isnil(LeftNode) of
true ->
Node#node{left=newleaf(Load)};
false ->
Node#node{left=insert(LeftNode, Load)}
end;
CurrentLoad =< Load ->
case isnil(RightNode) of
true ->
Node#node{right=newleaf(Load)};
false ->
Node#node{right=insert(RightNode, Load)}
end
end.

preorder([], ValueList) ->
ValueList;
preorder([Tree|TreeList], ValueList) ->
case Tree of
#node{left=Left, load=Load, right=Right} ->
NewValueList = [Load|ValueList],
NewTreeList = [Left|[Right|TreeList]],
preorder(NewTreeList, NewValueList);
{leaf, LeafLoad} ->
NewValueList = [LeafLoad|ValueList],
preorder(TreeList, NewValueList);
nil ->
preorder(TreeList, ValueList)
end.

preorder(Tree) ->
case Tree of
#node{left=_Left, load=_Load, right=_Right} ->
lists:reverse(preorder([Tree], []));
nil ->
[]
end.


Weeee....

No comments:

Post a Comment