in reply to How do I create a binary tree ?

Please note that the link you're giving on the O'Reilly books is on a site (presumably in Ukraine) which most probably does not have the right to publish these contents on the Internet. In other words, it is most probably illegal, and I would advise you to update your original post and remove the link.

Otherwise, everything important is done in the insert subroutine and it seems to be it is pretty much straight forward: if the value of the current node is larger than the value to be inserted, go down into the left subtree (by calling recursively insert on it); if it is larger, go down into the right subtree (also calling insert recursively); if it is equal, it is a duplicate, just ignore it; if the node is not defined, then create it, you're at the right place.

What is it that you don't understand?

Replies are listed 'Best First'.
Re^2: How do I create a binary tree ?
by mr_mischief (Monsignor) on Dec 07, 2015 at 20:26 UTC

    I'll note that for those severely budget-constrained, the older versions of The Perl CD Bookshelf from O'Reilly are really affordable. $4 shipped plus any applicable tax in the US, for example, is a good deal if you don't need the latest version. This doesn't support the authors and publisher as much as a brand new book, but it's legal and far more ethical than using pirated copies.

    Here's what the second version of the CD Bookshelf included:

    • Programming Perl, third edition
    • Perl for System Administration
    • Perl in a Nutshell
    • Perl Cookbook
    • Advanced Perl Programming

    There are also some good books that are actually gratis for personal use in electronic form. There's a huge GitHub project for free programming book lists at https://github.com/vhf/free-programming-books with various languages including English used for the lists. Of course there's a Perl section among many other languages and programming-language-neutral programming topics.

[reply]
Re^2: How do I create a binary tree ?
by punitpawar (Sexton) on Dec 06, 2015 at 19:20 UTC
    HI Laurent,
    Thanks for the response. The part which I do not understand is , how are the nodes inserted after a second node has been created.
    So say for instance the first node is with value 40. So this node now contains undefined references to the Left and Right node.
    Now say the second value that is generated is 60 , This is inserted to the Right of the tree. So $tree->{right} points a new tree with value 60.

    ( I understand till here) But now say if third value that is generated is 80 . At this point in time $root still points to the orignal tree with value 40.
    Now because $root is already defined it skips to the if else condition , and makes a call that 80 > 40 , hence it should be inserted to the right
    But $tree->{Right} is already defined , and it contains the value 60, so it never executes the actual routine to create a reference to a new tree .....


    So I am confused about the way they are using references to move things around.....

    And what if the third value that is generated is 50 . 50 >40 hence it will be inserted at the right. But 50<60 , so it should be inserted to the left of 60 in its tree.
    How is this determined in the code ?
    Will appreciate any help you can provide to clear my understanding....
[reply]
      But now say if third value that is generated is 80 . At this point in time $root still points to the orignal tree with value 40. Now because $root is already defined it skips to the if else condition , and makes a call that 80 > 40 , hence it should be inserted to the right But $tree->{Right} is already defined , and it contains the value 60, so it never executes the actual routine to create a reference to a new tree
      Yes, $tree->{Right} is already defined, so it recurses again, and inserts 80 as the right son of 60. 
      ($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,

      [download]
[reply]
[d/l]
[select]
      ( I understand till here) But now say if third value that is generated is 80 . At this point in time $root still points to the orignal tree with value 40. Now because $root is already defined it skips to the if else condition , and makes a call that 80 > 40 , hence it should be inserted to the right But $tree->{Right} is already defined , and it contains the value 60, so it never executes the actual routine to create a reference to a new tree .....
      Follow what is happening:

      - and makes a call that 80 > 40 , hence it should be inserted to the right

      Yes. So it calls the insert function on the right tree. When entering this new function call, it finds a node where the value is 60. It compares the values, and since 80 is larger than 60, it sees that it should call the insert function recursively once more on the right side. When it gets to this next level, the node below 60 does not exists yet, so that insert can actually create the node 80 below (and right of) node 60.

      Update ( Dec 06, 2015 at 22:25 UTC):

      This graph may make it clearer: 

                40
         /  \
        /    \
             60
            /  \
                \
                80

      [download]
      Now, if you add another node with a value of 50, it will go right of 40 and then left of 60: 
                40
         /  \
        /    \
             60
            /  \
           /    \
          50    80

      [download]
      Update 2:

      And, since you appear not to have seen my earlier warning, let me repeat that the link you're giving on the O'Reilly books is on a site (presumably in Ukraine) which most probably does not have the right to publish these contents on the Internet.

      In other words, it is most probably illegal, and I would advise again you to update your original post and remove the link.
[reply]
[d/l]
[select]
        Thanks for the response. I see that the link has been removed. Going forward I will keep this in mind.
[reply]

In Section Seekers of Perl Wisdom