How to Implement a Tree in Python

How to Implement a Tree in Python : In this new article we will see how to build a python tree.

Overview

In computer science, a tree is a data structure.This type of tree is used, for example, in decision trees. By default, this structure is not implemented natively in the python language. We will therefore see how to create a tree in python using classes to model it.

Binary Tree Data Structure

A tree is composed of several nodes that are linked together by links called edges. A tree has 3 main properties which are the following:

• The main node is named as the root node.
• Each node other than the root is associated with a parent node.
• Each node can have a child node arbitrary number.

The top of our tree is called the root node. Nodes that have no child nodes (with a reference to null for these children) are called leaves.

To illustrate these definitions nothing beats an explanatory diagram:

Create Root Node

So we are going to start to create our Tree class, which is based on the principles we mentioned earlier:

class Tree:

    def __init__(self, value=None, left=None, right=None):

        self.left = left
        self.right = right
        self.value = value

    def PrintTree(self):
        print(self.value)
 
 

The Tree class takes 3 parameters optionnals:

• The first parameter “value” corresponds to the value of the instanciated node (equal to None by default).
• The second parameter “left” corresponds to the left child node of the instanciated node (equal to None by default).
• The second parameter “right” corresponds to the right child node of the instanciated node (equal to None by default).

To test the class, simply call the class as follows:

root = Tree(8)
root.PrintTree()

Output:

10

Building Binary Tree

We have seen how to define our root node, now we have to define our child nodes. To do this we need to call the Tree class recursively to create new nodes:

class Tree:

    def __init__(self, value, left=None, right=None):

        self.left = left
        self.right = right
        self.value = value

    def PrintTree(self):
        print(self.value)
        if self.left:
            self.left.PrintTree()
        if self.right:
            self.right.PrintTree()


# 1st method

root = Tree(8, Tree(3), Tree(10))
root.PrintTree()

# 2nd method
root = Tree(8)
root.left = Tree(3)
root.right = Tree(10)
root.PrintTree()
 

In the first method we instanciated two Tree objects during the creation of our root node whereas in the second method we first create our root node with the left and right nodes to None then we assign them as value a new Tree object.

To reproduce the tree used in our diagram just do this:

class Tree:

    def __init__(self, value, left=None, right=None):

        self.left = left
        self.right = right
        self.value = value

    def PrintTree(self):
        print(self.value)
        if self.left:
            self.left.PrintTree()
        if self.right:
            self.right.PrintTree()


root = Tree(8)
root.left = Tree(3)
root.right = Tree(10)
root.left.left = Tree(1)
root.left.right = Tree(6)
root.right.right = Tree(14)

root.PrintTree()

 

Output:

8
3
1
6
10
14

It is quite possible to put any type of data in our tree (and not only numbers):

class Tree:

    def __init__(self, value, left=None, right=None):

        self.left = left
        self.right = right
        self.value = value

    def PrintTree(self):
        print(self.value)
        if self.left:
            self.left.PrintTree()
        if self.right:
            self.right.PrintTree()


root = Tree("WEBSITE AMIRADATA")
root.left = Tree("News")
root.right = Tree("Learning")
root.left.left = Tree("Hardware")
root.left.right = Tree("Technology")
root.right.right = Tree("Python")

root.PrintTree()

 

Output:

WEBSITE AMIRADATA
News
Hardware
Technology
Learning
Python

Back to the Python Menu