Thread: compleate mess of trying to write a binary tree cobeling together bits of code

  1. #16
    Registered User
    Join Date
    May 2019
    Posts
    214


    There is one thing you might enjoy having as you move to the balance code. You may enjoy visualizing the resulting tree.

    Here's a link (there are so many) you might be able to interpret. The node is exactly like your Bin_Node, but the code is C++. It is, however, barely C++. You should be able to re-interpret this to visualize the tree on a text display.

    Print Binary Tree Structure with its contents in C++ - Techie Delight

  2. #17
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    AVL tree - Wikipedia

    For those not in the know about AVL Tree; I forgot all about them. Did remember a little about red–black trees.

    cooper1200: I am playing around with your code to remind myself about binary trees; it has been decades since I wrote a binary tree and I forgot a lot.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #18
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    am i right in thinking that the new key word in c++ is the equiverlant of malloc in c ie it assigns a chunk of memory

  4. #19
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    what im scratching my head about is the four cases...
    left left = right rotation
    left right = right then left rotation
    right right = left rotation
    right left = left right rotation.

    i get that its just a rule one has to remember what i don't understand is how one decides which node should be come the parent node. and how one visualises what it looks like

  5. #20
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Quote Originally Posted by cooper1200 View Post
    am i right in thinking that the new key word in c++ is the equiverlant of malloc in c ie it assigns a chunk of memory
    Yes, you need to replace the new with malloc and the delete with free.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #21
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    am i right in thinking that the new key word in c++ is the equiverlant of malloc in c ie it assigns a chunk of memory
    This is a tricky one to answer for you, because you are intending to develop code on the Arduino...

    The Arduino does not fully implement the C++ standard, so "new" is litterally this...
    ArduinoCore-samd/new.cpp at master * arduino/ArduinoCore-samd * GitHub



    However, when using "new" in C++ world it runs something called a "constructor" as well as allocating memory.
    Fact - Beethoven wrote his first symphony in C

  7. #22
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    945
    Quote Originally Posted by Click_here View Post
    This is a tricky one to answer for you, because you are intending to develop code on the Arduino...

    The Arduino does not fully implement the C++ standard, so "new" is litterally this...
    ArduinoCore-samd/new.cpp at master * arduino/ArduinoCore-samd * GitHub



    However, when using "new" in C++ world it runs something called a "constructor" as well as allocating memory.
    Are you sure Arduino's "new" operator doesn't call the class's constructor? It's my understanding that "operator new" is responsible only for allocating memory, and the compiler will generate the code needed to call the constructor after calling "operator new".

  8. #23
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    It used to be a problem, but my info might be out dated...

    You might need to fact check that one!

  9. #24
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    The `operator new` function and the `new` operator are different beasts.

    If the compiler behaves properly (I have no idea as I don't recall.) with respect to the `new` operator, the implementation of the `operator new` function is basically irrelevant as the `new` operator is responsible for calling constructors and associated destructor in the event of an exception.

    Soma
    “Salem Was Wrong!” -- Pedant Necromancer
    “Four isn't random!” -- Gibbering Mouther

  10. #25
    Registered User
    Join Date
    May 2019
    Posts
    214
    Quote Originally Posted by cooper1200 View Post
    am i right in thinking that the new key word in c++ is the equiverlant of malloc in c ie it assigns a chunk of memory
    They are similar, yes, in that they both allocate memory that must be released by the matching keyword (delete for new, free for malloc).

    As for calling the constructor, that's part of what new does - but you can override 'new' in a class for customized allocation and construction, or use something called "in place new", which constructs an object in an existing location without allocation.

  11. #26
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    im sorry to be think but if new allocates memory as well as the "constructor" surely the main in this example Print Binary Tree Structure with its contents in C++ - Techie Delight is completely wrong as far as following the rules of a binary tree

  12. #27
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    What makes you think that it "is completely wrong as far as following the rules of a binary tree"?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #28
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    well from what i understand keeping in mind i don't know c++ we start with a root node (in this case 1) then anything smaller than it should go on the left and anything bigger than it should go on the right so in the example they have the 2 going to the left of 1 ok they might of decided to flip the "rule" so the 2 would go to the left. but next line they but the three on the right of the 1.

  14. #29
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    You're thinking of a binary search tree. That example is of a binary tree.

    It's like saying that inserting into an array by appending is wrong because you must insert to maintain sorted order. Of course not: that's for a sorted array, not an array in general.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #30
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    so i have been studying binary search trees not binary trees....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please review my code for a binary tree
    By 2013Starter in forum C Programming
    Replies: 1
    Last Post: 01-15-2014, 02:26 PM
  2. Write/Read tree nodes into a binary file
    By frank1 in forum C Programming
    Replies: 2
    Last Post: 10-21-2013, 12:37 AM
  3. Problem for Binary Tree code , Help
    By cuihu52 in forum C++ Programming
    Replies: 5
    Last Post: 01-03-2013, 11:14 PM
  4. where can I find source code for a binary tree?
    By binary_man in forum C++ Programming
    Replies: 5
    Last Post: 01-10-2003, 09:53 AM
  5. copy some bits into a 8 bits binary number
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 05-29-2002, 10:54 AM

Tags for this Thread