help binary tree print in python??

A forum for general discussion of the Python programming language.

help binary tree print in python??

Postby VenugopalaRao » Sat Jun 08, 2013 7:11 am

i am unable to print a binary tree in the following
Code: Select all
                                          20                                                                         
                                 +--------------+                                                                       
                                30              10                                                                     
                 +----------------------+                                                                               
                40                      45                                                                             
     +----------------------+        +--+                                                                               
    50                      90      55                                                                                 
 +------+                +--+                                                                                           
60      70              80                                                                                             
         +--+        +--+                                                                                               
            20      50               

can any one help me please.
input is list of nodes
VenugopalaRao
 
Posts: 16
Joined: Wed May 15, 2013 5:05 pm

Re: help binary tree print in python??

Postby stranac » Sat Jun 08, 2013 7:32 am

Show us this "list of nodes", and also show the code you have tried.
Friendship is magic!

R.I.P. Tracy M. You will be missed.
User avatar
stranac
 
Posts: 1137
Joined: Thu Feb 07, 2013 3:42 pm

Re: help binary tree print in python??

Postby VenugopalaRao » Sat Jun 08, 2013 7:47 am

Code: Select all
def show_tree(tree, total_width=100, fill=' '):
    output = StringIO()
    last_row = -1
    for i, n in enumerate(tree):
        if i:
            row = int(math.floor(math.log(i+1, 2)))
        else:
            row = 0
        if row != last_row:
            output.write('\n')
        columns = 2**row
        col_width = int(math.floor((total_width * 1.0) / columns))
        output.write(str(n).center(col_width, fill))
        last_row = row
    print output.getvalue()
    return

this prints the tree in the following format :
Code: Select all


                                                 20                                                 
                        30                                                10                       
            40                       45                                                             
     50          90          55                                                                 
  60    70    80                                                                               
          20 50     

but i dont require in that way, i need the tree given the first post
can any one help which modifications can i do to get the result
VenugopalaRao
 
Posts: 16
Joined: Wed May 15, 2013 5:05 pm

Re: help binary tree print in python??

Postby stranac » Sat Jun 08, 2013 10:57 am

And what is tree?
I still don't know what you list of nodes looks like.
Friendship is magic!

R.I.P. Tracy M. You will be missed.
User avatar
stranac
 
Posts: 1137
Joined: Thu Feb 07, 2013 3:42 pm

Re: help binary tree print in python??

Postby VenugopalaRao » Sat Jun 08, 2013 11:22 am

Code: Select all
def create_tree(input):
    if input is None:
        return None

    if not isinstance(input, tuple):
        return TreeNode(input)

    assert len(input) == 3, "invalid input"
    root_val, left, right = input
    root = TreeNode(root_val)
    root.left = create_tree(left)
    root.right = create_tree(right)
    return root

Code: Select all
def traverse(rootnode):
  thislevel = rootnode
  level=maxlevel(rootnode)
  level=int(level)+1
  maxnode=2**level-1
  bfslist=[thislevel.value]
  thislevel = [rootnode]
  temp1=thislevel
  flag=0
  cnt=0
  while flag==0:
     try:
      if temp1[cnt]==' ':
        nl=int(math.floor(math.log(int(cnt)+1, 2)))
        if nl<level:
              bfslist.append(' ')
              bfslist.append(' ')
              temp1.append(' ')
              temp1.append(' ')
      else:
        #-- TREE LEFT SIDE
        if temp1[cnt].left==None:
            bfslist.append(' ')
            temp1.append(' ')
        elif temp1[cnt].left:
            bfslist.append(temp1[cnt].left.value)
            temp1.append(temp1[cnt].left)
        #-- TREE RIGHT SIDE
        if temp1[cnt].right==None:
            bfslist.append(' ')
            temp1.append(' ')
        elif temp1[cnt].right:
            bfslist.append(temp1[cnt].right.value)
            temp1.append(temp1[cnt].right)
      cnt=cnt+1
      if cnt>=maxnode:
          flag=1
     except IndexError:
         flag=1
  return bfslist


these are the function i had used
the below provides a sample call program to show_tree function:
Code: Select all
input_tuple_tree = (20, (30, (40, (50, 60, (70,None,20)), (90,(80,50,None),None)), (45,55,None)),10)
z=traverse(input_tuple_tree)
show_tree(z)
VenugopalaRao
 
Posts: 16
Joined: Wed May 15, 2013 5:05 pm

Re: help binary tree print in python??

Postby stranac » Sat Jun 08, 2013 3:25 pm

The maxlevel() function seems to be missing, so I still don' know what z is.
Posting your entire code would make this so much simpler...

Also, from looking at your functions, it seems to me it would be a good idea to create a class to represent your tree.
Friendship is magic!

R.I.P. Tracy M. You will be missed.
User avatar
stranac
 
Posts: 1137
Joined: Thu Feb 07, 2013 3:42 pm


Return to General Discussions

Who is online

Users browsing this forum: Google [Bot] and 2 guests