Need an algorithm for creating an complete binary tree.

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

  1. C-man

    C-man Guest

    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
    #1
    1. Advertising

  2. C-man

    Mike Wahler Guest

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

    "C-man" <> wrote in message
    news:pgv1c.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:
    http://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q="binary tree" alg
    orithm+%22C%2B%2B%22&btnG=Google+Search
    (that'll probably wrap, just paste it back together)

    Over 7,000 hits.

    You might want to try asking about this in an algorithms group
    or mailing list.

    -Mike
     
    Mike Wahler, Mar 4, 2004
    #2
    1. Advertising

  3. "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
    will get logarithmic access to all operations. And the corresponding
    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
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Max
    Replies:
    4
    Views:
    560
  2. binaya

    complete binary tree

    binaya, Oct 22, 2003, in forum: C Programming
    Replies:
    2
    Views:
    1,010
    Thomas Matthews
    Oct 22, 2003
  3. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,175
  4. Ravi
    Replies:
    6
    Views:
    1,638
    Richard Tobin
    Aug 22, 2005
  5. Aris

    Binary tree Algorithm

    Aris, Dec 3, 2005, in forum: C++
    Replies:
    10
    Views:
    763
    red floyd
    Dec 8, 2005
Loading...

Share This Page