pythonpython-3.4

print binary tree level by level in python


I want to print my binary tree in the following manner:

                   10

               6        12

             5   7    11  13 

I have written code for insertion of nodes but can't able to write for printing the tree. so please help on this . My code is :

class Node:
    def __init__(self,data):
       self.data=data
       self.left=None
       self.right=None
       self.parent=None

class binarytree:
   def __init__(self):
     self.root=None
     self.size=0

   def insert(self,data):
     if self.root==None:
        self.root=Node(data)

    else:
        current=self.root
        while 1:
            if data < current.data:
                if current.left:
                    current=current.left
                else:
                    new=Node(data)
                    current.left=new
                    break;
            elif data > current.data:
                if current.right:
                    current=current.right
                else:
                    new=Node(data)
                    current.right=new
                    break;
            else:
                break



 b=binarytree()  

Solution

  • What you're looking for is breadth-first traversal, which lets you traverse a tree level by level. Basically, you use a queue to keep track of the nodes you need to visit, adding children to the back of the queue as you go (as opposed to adding them to the front of a stack). Get that working first.

    After you do that, then you can figure out how many levels the tree has (log2(node_count) + 1) and use that to estimate whitespace. If you want to get the whitespace exactly right, you can use other data structures to keep track of how many spaces you need per level. A smart estimation using number of nodes and levels should be enough, though.