From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,LOTS_OF_MONEY autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,24d1392c628fdfb6 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-04-12 12:04:18 PST Path: supernews.google.com!sn-xit-02!supernews.com!news.gv.tsc.tdk.com!newsfeed.berkeley.edu!ucberkeley!freenix!grolier!dispose.news.demon.net!demon!diablo.theplanet.net!news.theplanet.net!newspost.theplanet.net!not-for-mail From: "Des Walker" Newsgroups: comp.lang.ada Subject: Re: array Date: Thu, 12 Apr 2001 19:59:41 +0100 Message-ID: <9b4tb6$cha$1@news5.svr.pol.co.uk> References: <5s2B6.32267$ii5.3236241@afrodite.telenet-ops.be> NNTP-Posting-Host: modem-56.brown-sailfin-tang.dialup.pol.co.uk X-Trace: news5.svr.pol.co.uk 987101350 12842 62.136.243.56 (12 Apr 2001 18:49:10 GMT) NNTP-Posting-Date: 12 Apr 2001 18:49:10 GMT X-Complaints-To: abuse@theplanet.net X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.00.2615.200 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2615.200 Xref: supernews.google.com comp.lang.ada:6835 Date: 2001-04-12T18:49:10+00:00 List-Id: Ted Dennison wrote in message news:DpjB6.4297$FY5.303408@www.newsranger.com... > In article <5s2B6.32267$ii5.3236241@afrodite.telenet-ops.be>, Pieter Thysebaert > says... > >Now I was looking for a function that would allow me to convert the contents > >of a tree into an array (and vice versa) > >I've found something like arrays with variable range (I mean not fixed at > >compile-time) > >Well I think that's what I found - does that thing exist ? > > > >And if it does, how would one manipulate it (add/remove elements) > > Back in the olden days, binary trees were ususally implmented as arrays. I > believe the algorithms for doing so are avilable in "The Art of Computer > Programming, Volume 3" http://www-cs-faculty.stanford.edu/~knuth/taocp.html ). > Go find, or preferably purchase yourself, a copy. > > > > > >Or are there data structures like C++ STL stuff (vector etc) available ? > The Ada implementation of the Booch Components should have something for > size-limited trees, which I would imagine would be implemented using arrays (but > I haven't examined the code). > > --- > T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html > home email - mailto:dennison@telepath.com Hi, I think the underlying implementation for some of the 'bounded' items in the Booch Components use arrays, but the array would not be directly accessible to the user. The BC does provide some useful binary tree implementations for dynamically changing binary trees, I've used the AVL tree to good effect. One method of representing a binary tree in an array is put each node at the index which corresponds to the order you would obtain it in a breadth order traversal. i.e. If you number your binary tree nodes starting at the root node -------1 ---2-------3 4----5--6----7 The numbers correspond to the array index for the element for an element at index I, the left child will be at index (I*2) the right child will be at index (I*2+1) the parent will be at index (I/2) If your binary tree has holes in it, you'll need some way of describing an empty array element, to maintain the correct position of a node in an array. In this way you'll know a node doesn't have a child if the index for the child is greater than the maximum size of the array, or the value at that index is the empty element. Sorry I can't be more helpful, I've never used an array implementation for a binary tree. Binary Trees I have used have been ones which are dynamically changing and need continuous rebalancing, for which the AVL tree has been satisfactory. Des Walker