Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

How do I create a binary tree ?

by punitpawar (Sexton)
on Dec 06, 2015 at 16:35 UTC ( #1149515=perlquestion: print w/replies, xml ) Need Help??

punitpawar has asked for the wisdom of the Perl Monks concerning the following question:

Hello
I need your help. I am trying to write a program that will create a binary tree for any 10 random numbers that are generated. I did try to search online , but I am not able to get a simplified approach of doing this.
Please can any of you help me with this ?

I was reading this link : the Perl Cookbook

But for some reason the node insertion after the second node is added does not make sense to me. I am confused with the way they are using references here.
Any help will be appreciated.

Replies are listed 'Best First'.
Re: How do I create a binary tree ?
by Laurent_R (Canon) on Dec 06, 2015 at 17:14 UTC
    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?

      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.

      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....
        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,
        ( 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
        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
        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.
Re: How do I create a binary tree ?
by QuillMeantTen (Friar) on Dec 06, 2015 at 16:42 UTC

    Welcome to perlmonks,
    As usually stated in those case, this is not an online code writing service.

    What have you tried? If you post a bit of code or at least your ideas on how you would go about it (what perl built in structure you might use) you might get help!

    So before you hit google with "binary tree implementation" you might as well have a look at this if you feel in an array using mood
    You might also implement your tree as a serie of hash data structures with references to each other
    Update:
    as explained in the link above, after the second node has been added you just recursively use the same action to add new nodes:

    Is that value bigger than the first node?
    then recurse right
    else recurse left
    and so on.
    When updating the tree you add references to the new values that way they are not lost, that means that once you have found a place for the new value in your tree you update the new node's father with a reference to his child (here in left or right field)

    Update 2
    Just to be clear, when I say recurse I mean, call the function inside itself, using recursion that is. If you understand the concept that kind of data structure becomes much easier to handle

Re: How do I create a binary tree?
by Athanasius (Archbishop) on Dec 07, 2015 at 03:11 UTC

    Hello punitpawar,

    I am trying to write a program that will create a binary tree for any 10 random numbers that are generated.

    From your later posts, it appears that you actually want a sorted binary tree. CPAN has various modules you can use for this. Here is one example:

    #! perl use strict; use warnings; use Tree::Binary::Search; use Tree::Binary::Visitor::InOrderTraversal; for (1 .. 20) { my $btree = Tree::Binary::Search->new; $btree->useNumericComparison; for (1 .. 10) { my $num = int rand 100; redo if $btree->exists($num); $btree->insert($num => 1); } my $visitor = Tree::Binary::Visitor::InOrderTraversal->new; $visitor->setNodeFilter(sub { $_[0]->getNodeKey }); $btree->accept($visitor); print join(' ', map { sprintf '%2d', $_ } $visitor->getResults), " +\n"; $btree->DESTROY; }

    Output:

    13:09 >perl 1475_SoPW.pl 0 9 14 33 37 55 60 77 89 99 15 26 28 51 59 75 78 79 94 99 18 31 33 38 44 47 70 73 77 84 4 21 24 28 38 57 65 76 98 99 16 42 50 62 70 71 83 87 92 94 21 29 35 40 49 68 71 79 85 90 2 5 11 16 24 46 50 55 75 99 19 26 28 39 42 51 53 59 66 98 26 35 41 45 53 54 67 81 88 95 19 28 45 51 58 64 65 67 79 82 0 21 27 54 60 63 64 73 78 99 0 5 13 27 31 50 61 74 77 92 11 13 14 29 52 60 71 79 80 86 8 9 29 36 37 50 58 69 81 82 10 14 23 38 46 53 57 67 90 97 7 8 13 14 30 32 34 41 50 76 6 11 21 28 50 53 78 79 96 98 19 24 28 37 60 71 78 85 88 93 14 26 28 31 42 59 71 83 87 94 0 8 13 15 19 51 52 71 78 85 13:09 >

    As you can see, in-order traversal outputs the numbers in sorted (numerical ascending) order, showing that the underlying binary tree is sorted.

    Hope that helps,

    Athanasius <°(((><contra mundum Iustus alius egestas vitae, eros Piratica,

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1149515]
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (6)
As of 2022-06-30 12:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My most frequent journeys are powered by:









    Results (98 votes). Check out past polls.

    Notices?