Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!wuarchive!decwrl!polyslo!vlsi3b15!vax1.cc.lehigh.edu!netnews.upenn.edu!linc.cis.upenn.edu!dowding
From: dowding@linc.cis.upenn.edu (John Dowding)
Newsgroups: comp.lang.prolog
Subject: Re: prolog tree building question
Keywords: m-way trees
Message-ID: <20315@netnews.upenn.edu>
Date: 13 Feb 90 00:12:18 GMT
References: <8052@cbnewsh.ATT.COM> <110154@ti-csl.csc.ti.com>
Sender: news@netnews.upenn.edu
Reply-To: dowding@linc.cis.upenn.edu (John Dowding)
Organization: University of Pennsylvania
Lines: 41

In article <110154@ti-csl.csc.ti.com> brahme@vlsic2.ti.com (Dan Brahme) writes:
>skumar@cbnewsh.ATT.COM (swaminathan.ravikumar) writes:
>
>
>>I have the following facts asserted in the prolog database:

.
.
.

>Try representing trees by t(Nodename, Listofchildnodes).
>which would give you 
>t(a,[t(b,[t(d,[]),t(e,[]),t(f,[])]), t(c, [])])
>

An alternative to this is the representation used for Restriction Grammars:

tree(Node, Child, Sibling)

where Child is the left-most child of Node, and Sibling is the sibling to
the immediate right of Node (if there is one).

tree(a,
   tree(b,
      tree(d,_,tree(e,_,tree(f,_,_))),
      tree(c,_,_)),
    _)

This structure may be a bit non-intuitive, but has certain advantages 
for some applications, in that it does not build that extra list structure,
and it is cheap to dynamically grow the tree on its fringe.

See the following for more details:

L. Hirschman and K. Puder, "Restriction Grammar: A Prolog Implementation."
in Logic Programming and its Applications, ed. D.H.D. Warren and M.
VanCaneghem, 1985.


John Dowding
dowding@linc.cis.upenn.edu