CODEWITHSUNDEEP
python-3.xbinary-tree
Anurag Tripathi
Anurag Tripathi

Reputation: 1094

How to represent Binary tree into an array using python?

I want to convert Binary Tree into Array using Python and i don't know how to give index to tree-node?

I have done this using the formula left_son=(2*p)+1; and right_son=(2*p)+2; in java But i'm stuck in python. Is there any Function to give index to tree-node in python ?

Upvotes: 0

Views: 13926

Answers (2)

Mark
Mark

Reputation: 92461

You can represent a binary tree in python as a one-dimensional list the exact same way.

For example if you have at tree represented as:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15]

0 is the root
1 & 2 are the next level
the children of 1 & 2 are [3, 4] and [5, 6]

This corresponds to your formula. For a given node at index i the children of that node are (2*i)+1 (2*i)+2. This is a common way to model a heap. You can read more about how Python uses this in its [heapq library].(https://docs.python.org/3.0/library/heapq.html)

You can use this to traverse the tree in depths with something like:

a =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15]

def childNodes(i):
     return (2*i)+1, (2*i)+2

def traversed(a, i=0, d = 0):
    if i >= len(a):
        return 
    l, r =  childNodes(i)
    traversed(a, r, d = d+1)
    print("   "*d + str(a[i]))
    traversed(a, l, d = d+1)

traversed(a)

This Prints

         15
      6
         14
   2
         13
      5
         11
0
         10
      4
         9
   1
         8
      3
         7

Upvotes: 8

taurus05
taurus05

Reputation: 2546

Incase of a binary tree, you'll have to perform a level order traversal. And as you keep traversing, you'll have to store the values in the array in the order they appear during the traversal. This will help you in restoring the properties of a binary tree and will also maintain the order of elements. Here is the code to perform level order traversal.

class Node: 

    # A utility function to create a new node 
    def __init__(self, key): 
        self.data = key  
        self.left = None
        self.right = None


# Function to  print level order traversal of tree 
def printLevelOrder(root): 
    h = height(root) 
    for i in range(1, h+1): 
        printGivenLevel(root, i) 


# Print nodes at a given level 
def printGivenLevel(root , level): 
    if root is None: 
        return
    if level == 1: 
        print "%d" %(root.data), 
    elif level > 1 : 
        printGivenLevel(root.left , level-1) 
        printGivenLevel(root.right , level-1) 


""" Compute the height of a tree--the number of nodes 
    along the longest path from the root node down to 
    the farthest leaf node 
"""
def height(node): 
    if node is None: 
        return 0 
    else : 
        # Compute the height of each subtree  
        lheight = height(node.left) 
        rheight = height(node.right) 

        #Use the larger one 
        if lheight > rheight : 
            return lheight+1
        else: 
            return rheight+1

# Driver program to test above function 
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 

print "Level order traversal of binary tree is -"
printLevelOrder(root)

Upvotes: 1

Related Questions