Ouputting the binary tree in using in-order and pre-order traversal

user_15502141 0
Viewed 201
class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
def inorderTraversal(root):
 
    if root is None:
        return
 
    inorderTraversal(root.left)
    print(root.data, end=' ')
    inorderTraversal(root.right)
 
def preorderTraversal(root):
 
    if root is None:
        return
 
    print(root.data, end=' ')
    preorderTraversal(root.left)
    preorderTraversal(root.right)
 
def construct(start, end, preorder, pIndex, dict):
 
    # base case
    if start > end:
        return None, pIndex
 
    root = Node(preorder[pIndex])
    pIndex = pIndex + 1
 
    index = dict[root.data]
 
    root.left, pIndex = construct(start, index - 1, preorder, pIndex, dict)
 
    root.right, pIndex = construct(index + 1, end, preorder, pIndex, dict)
 
    return root, pIndex     

def constructTree(inorder, preorder):
 
    dict = {}
    for i, e in enumerate(inorder):
        dict[e] = i
 
    pIndex = 0
 
    return construct(0, len(inorder) - 1, preorder, pIndex, dict)[0]
 
 
if __name__ == '__main__':
 
 
    inorder = [4, 2, 1, 7, 5, 8, 3, 6]
    preorder = [1, 2, 4, 3, 5, 7, 8, 6]
 
    root = constructTree(inorder, preorder)
 
    print("The inorder traversal is ", end='')
    inorderTraversal(root)
 
    preorderTraversal(root)

I have this code which construct the binary tree, but in no way it can display the tree in the terminal. It is hard to do! Is there anyone here who could add a method which can display the binary tree in a terminal?

For the above example, it might look like

Binary Tree

enter image description here

preorder inorder binary-tree python
1 Answers

Implemented algorithm for solving your task. For example tested output on same data as your picture has, try on bigger amount of numbers to see more beautiful picture.

In my algorithm both width and height of each sub-tree and length of edges are adaptive.

Those who knows Russian language may read my other post regarding same topic, binary tree construction in console. That other post implements several visualization algorithms in C++. If you don't know Russian at least you may copy C++ code from there.

Try it online!

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        
def print_tree(node):
    def inner(node):
        if node is None:
            return []
        sdat = str(node.data)
        l, r = inner(node.left), inner(node.right)
        cl, cr = len((l or ('',))[0]), len((r or ('',))[0])
        s = max(cl, cr)
        sll, slr = (s - cl + 1) // 2, (s - cl) // 2
        srl, srr = (s - cr) // 2, (s - cr + 1) // 2
        v = [' ' * s + sdat + ' ' * s]
        v.extend([' ' * (s - i - 1) + '/' + ' ' * i + ' ' * len(sdat) +
            ' ' * i + '\\' + ' ' * (s - i - 1) for i in range(s // 2)])
        v.extend([(' ' * sll + l[i] + ' ' * slr if i < len(l) else ' ' * s) +
            ' ' * len(sdat) + (' ' * srl + r[i] + ' ' * srr if i < len(r) else ' ' * s)
            for i in range(max(len(l), len(r)))])
        return v
    print('\n'.join(inner(node)))
        
if __name__ == '__main__':
    root = Node(1, Node(2, Node(4)), Node(3, Node(5, Node(7), Node(8)), Node(6)))
    print_tree(root)

Output:

       1
      / \
     /   \
    /     \
   2       3
  4       / \
         5   6
        7 8

First algorithm above was done using preorder. I'm providing 2nd algorithm using inorder. It has a different simpler output:

Try it online!

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        
def print_tree(node):
    def inner(node, *, upref = '', cpref = '', dpref = ''):
        if node is None:
            return
        inner(node.right, upref = dpref + '  |',
            cpref = dpref + '  /', dpref = dpref + '   ')
        print(cpref + '--' + str(node.data))
        inner(node.left, upref = upref + '   ',
            cpref = upref + '  \\', dpref = upref + '  |')
    inner(node)
        
if __name__ == '__main__':
    root = Node(1, Node(2, Node(4)), Node(3, Node(5, Node(7), Node(8)), Node(6)))
    print_tree(root)

Output:

     /--6
  /--3
  |  |  /--8
  |  \--5
  |     \--7
--1
  \--2
     \--4

Implementing 3rd algorithm that does preorder, but it is much simpler than 1st algorithm:

Try it online!

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        
def print_tree(node):
    def inner(node, *, last = True, pref = ''):
        if node is None:
            return
        print(pref + ('\\-' if last else '|-') + str(node.data))
        inner(node.right, last = False, pref = pref + ('  ' if last else '| '))
        inner(node.left, last = True, pref = pref + ('  ' if last else '| '))
    inner(node)
        
if __name__ == '__main__':
    root = Node(1, Node(2, Node(4)), Node(3, Node(5, Node(7), Node(8)), Node(6)))
    print_tree(root)

Output:

\-1
  |-3
  | |-6
  | \-5
  |   |-8
  |   \-7
  \-2
    \-4
user_9415310
Related