Menu
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() 
973
To insert into a tree we use the same node class created above and add a insert class to it. The insert class compares the value of the node to the parent node and decides to add it as a left node or a right node. Finally the PrintTree class is used to print the tree.
This search is referred to as level order traversal or Breadth–first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth. A simple solution is to print all nodes of level 1 first, followed by level 2, until level h , where h is the tree's height.
Algorithm to print nodes at given levelIf level of current node is equal to L then we will print it on screen else continue pre order traversal. If node is equal to NULL, return. If level of node is equal to L, then print node and return. Recursively traverse left and right sub trees at level L + 1.
Each level in a binary tree is the number of nodes between that node and the root node, and each node consists of a left and right reference and stored data element. The top node for the binary tree is called the root node.
Step 1: To get a better intuition of the algorithm, visualize the binary tree and mark the levels as mentioned in the image given above. Step 2: Create a queue data structure and enqueue the elements from each level, hence we add 11 to the queue and initialize an empty array to store the result after completing the level order traversal, ie.
To traverse the tree in level order, we will first print the value in the root node, then we will print the value of children of the root node and we will move on to the next level after completing the current level until nodes from each level are printed.
METHOD 1 (Use function to print a given level) Algorithm: There are basically two functions in this method. One is to print all nodes at a given level (printGivenLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printGivenLevel to print nodes at all levels one by one starting from root.
Here's my attempt, using recursion, and keeping track of the size of each node and the size of children.
class BstNode: def __init__(self, key): self.key = key self.right = None self.left = None def insert(self, key): if self.key == key: return elif self.key < key: if self.right is None: self.right = BstNode(key) else: self.right.insert(key) else: # self.key > key if self.left is None: self.left = BstNode(key) else: self.left.insert(key) def display(self): lines, *_ = self._display_aux() for line in lines: print(line) def _display_aux(self): """Returns list of strings, width, height, and horizontal coordinate of the root.""" # No child. if self.right is None and self.left is None: line = '%s' % self.key width = len(line) height = 1 middle = width // 2 return [line], width, height, middle # Only left child. if self.right is None: lines, n, p, x = self.left._display_aux() s = '%s' % self.key u = len(s) first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s second_line = x * ' ' + '/' + (n - x - 1 + u) * ' ' shifted_lines = [line + u * ' ' for line in lines] return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2 # Only right child. if self.left is None: lines, n, p, x = self.right._display_aux() s = '%s' % self.key u = len(s) first_line = s + x * '_' + (n - x) * ' ' second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' ' shifted_lines = [u * ' ' + line for line in lines] return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2 # Two children. left, n, p, x = self.left._display_aux() right, m, q, y = self.right._display_aux() s = '%s' % self.key u = len(s) first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' ' second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' ' if p < q: left += [n * ' '] * (q - p) elif q < p: right += [m * ' '] * (p - q) zipped_lines = zip(left, right) lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines] return lines, n + m + u, max(p, q) + 2, n + u // 2 import random b = BstNode(50) for _ in range(50): b.insert(random.randint(0, 100)) b.display() Example output:
__50_________________________________________ / \ ________________________43_ ________________________99 / \ / _9_ 48 ____________67_____________________ / \ / \ 3 11_________ 54___ ______96_ / \ \ \ / \ 0 8 ____26___________ 61___ ________88___ 97 / \ / \ / \ 14_ __42 56 64_ 75_____ 92_ / \ / / \ / \ / \ 13 16_ 33_ 63 65_ 72 81_ 90 94 \ / \ \ / \ 25 __31 41 66 80 87 / / 28_ 76 \ 29 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.
44
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
