Tree modeling

[Ulf Wiger]

On 13 Jul 2000, Mickael Remond wrote:

>
>How would you write an insert function to add child to a tree structure
>represented like that:
>
>{id, name, [child]}
>
>For example: 
>{1, "test1", [
>    {2, "test2", []},
>    {3, "test3", [
>            {4, "test4", []}]},
>    {5, "test5", []]}
>
>I did not figure out how to scan/walk this tree with recursive functions.
>It will be easy if it was a binary tree, but this is not the case...

What are the criteria for insertion? Are there split/merge thresholds?
Why is for example 4 a child of 3?

In any case, I wrote a walk/1 function and an insert/3 function,
assuming that you need to identify the parent node when you insert.
The walk/1 function is really tree_to_list/1.

/Uffe
-- 
Ulf Wiger                                    tfn: +46  8 719 81 95
Network Architecture & Product Strategies    mob: +46 70 519 81 95
Ericsson Telecom AB,              Datacom Networks and IP Services
Varuvägen 9, Älvsjö,                    S-126 25 Stockholm, Sweden
-------------- next part --------------
-module(ltree).

-export([walk/1,
	 insert/3]).


walk({Id, Name, Children}) ->
    lists:reverse(walk(Children, [{Id, Name}])).

walk([{Id, Name, Children}|T], Acc) ->
    NewAcc = walk(Children, [{Id, Name}|Acc]),
    walk(T, NewAcc);
walk([], Acc) ->
    Acc.


insert(Obj, ParentId, Tree) ->
    walk_insert(ParentId, Tree, Obj).

walk_insert(PId, {PId, PName, Children}, Obj) ->
    {PId, PName, sort_insert(Obj, Children)};
walk_insert(PId, {Id, Name, Children}, Obj) ->
    case walk_insert1(Children, PId, Obj, []) of
	false ->
	    false;
	NewChildren ->
	    {Id, Name, NewChildren}
    end.

walk_insert1([Node|T], PId, Obj, Acc) ->
    case insert(Obj, PId, Node) of
	false ->
	    walk_insert1(T, PId, Obj, [Node|Acc]);
	NewNode ->
	    lists:reverse(Acc) ++ [NewNode|T]
    end;
walk_insert1([], PId, Obj, Acc) ->
    false.


sort_insert(Obj = {Id, _, _}, [H = {Id1, _, _}|T]) when Id > Id1 ->
    [H, sort_insert(Obj, T)];
sort_insert(Obj = {Id, _, _}, [H = {Id1, _, _}|T]) when Id < Id1 ->
    [Obj, H | T];
sort_insert(Obj, []) ->
    [Obj].