# Need an algorithm for creating an complete binary tree.

Discussion in 'C++' started by C-man, Mar 4, 2004.

1. ### C-manGuest

Yeah, for some reason I can seem to find an algorithm that will simple but
items into the tree in fashion such that a new leaf can't be added to a new
level till all the leafs at the previous level are used. This would seem
like an easy solution but I couldn't find one and I only could get it
parsley working. Any body of a solution?

Thanks

C-man, Mar 4, 2004

2. ### Mike WahlerGuest

Re: [OT, welcome msg, link] Need an algorithm for creating an complete binary tree.

"C-man" <> wrote in message
newsgv1c.39622\$n17.16894@clgrps13...
> Yeah, for some reason I can seem to find an algorithm that will simple but
> items into the tree in fashion such that a new leaf can't be added to a

new
> level till all the leafs at the previous level are used. This would seem
> like an easy solution but I couldn't find one and I only could get it
> parsley working. Any body of a solution?

Algorithms aren't topical here. Just the ISO standard C++ language.
See: http://www.slack.net/~shiva/welcome.txt

However:
(that'll probably wrap, just paste it back together)

Over 7,000 hits.

or mailing list.

-Mike

Mike Wahler, Mar 4, 2004

3. ### Dietmar KuehlGuest

"C-man" <> wrote:
> Yeah, for some reason I can seem to find an algorithm that will simple but
> items into the tree in fashion such that a new leaf can't be added to a new
> level till all the leafs at the previous level are used. This would seem
> like an easy solution but I couldn't find one and I only could get it
> parsley working. Any body of a solution?

What is your actual goal? Typically, for something like a search tree it is
sufficient that the tree is reasonably balanced. For example, if the
maximum height in each (sub)tree is at most twice the minimum height, you
condition is relatively easy to maintain using AVL- or Red-Black-Trees.

The simplest approach to a fully balanced binary tree is probably using an
array in the first place! You would use 'std::lower_bound()' to locate a
position - be it for insertion or lookup. The container is, in this case,
of course not node bound.
--
<mailto:> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

Dietmar Kuehl, Mar 4, 2004