Tree node in python

Python Tree Data Structure | Tree in Python

Learn tree in Python- data structure, programs with code examples. Know more about Python tree, how to create it and traverse using pre and post order.

What is a tree in Python?

Trees are non-linear data structures representing nodes connected by edges. Each tree consists of a root or main node known as the Parent node and the left node and right node as Child nodes. It is used for searching and data organization.

Does Python have Tree?

No, Python does not have any trees built-in. On the other hand, you can easily construct by subclassing a Node type from list and writing the traversal methods. We will discuss this later in the article.

Introduction to Python Tree

A binary tree node contains the following components- Data, Left Child, Right Child. The important terms related to a binary tree are:

1. Node – The simplest unit of a binary tree.
2. Root – It is the topmost element. There is mostly one root in a binary tree.
3. Parent – It is the node that is one level upward of the node.
4. Child – They are the nodes that are one level downward of the node.
5. Leaf – Leaves of a binary tree are the nodes that have no children.
6. Level – It is the generation of the node.

For example, a root has level 0, the children of the root node is at level 1 and the grandchildren of the root node is at level 2.

How Tree is implemented in Python? Tree program in Python

To implement and create a tree in Python, we first create a Node class that will represent a single node. The node class will have 3 variables- the left child, the second variable data containing the value for that node and the right child.

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

root = Node(10) root.left = Node(34) root.right = Node(89) root.right.left = Node(45) root.right.right = Node(50)

As a result, the output tree looks like this:

If you create an object of class Node, the __init__ constructor is called, and all the variables inside that constructor will get initialized. The root holds the root node of the tree has a value of 10. We insert the left child with the value 34 and the right child with the value 89. As it is a binary tree, every node can contain a maximum of two nodes. Further, we insert two more nodes to the tree as in 45 and 50. They are the children for node 89.

Note: We can insert any number of nodes we want inside a tree, depending upon the type of tree being created.

How to print tree elements | Traverse a Tree in Python

Since we have created a tree, so we need to traverse the tree to print the tree elements. Traversing means visiting every node in a tree. Every node in a tree is visited three times. There are three types of traversals in a binary tree: in-order traversal, pre-order traversal, and post-order traversal.

In-order Traversal

In this case, we first visit the left child and perform recursion, then we visit the same node for the second time to print that node. It is further followed by the parent node, then followed by recursion on the right child.
The given tree is:

 10 / \ 34 89 / \ / \ 20 45 56 54

def inorder(node): if node: inorder(node.left) print(node.data) inorder(node.right)

As a result, the output is:
20 34 45 10 56 89 54

Pre-order Traversal

In this case, while traversing a python tree, we see the root node for the first time and print it. It is then followed by recursion on the left and the right child.
The given tree is:

 10 / \ 34 89 / \ / \ 20 45 56 54

def preorder(node): if node: print(node.data) preorder(node.left) preorder(node.right)

As a result, the output is:
10 34 20 45 89 56 54

Post-order Traversal

In this case, while traversing a tree, we do recursion on the left node and the right node. Then we come to the root node to print it.
The given tree is:

 10 / \ 34 89 / \ / \ 20 45 56 54

def postorder(node): if node: postorder(node.left) postorder(node.right) print(node.data)

As a result, the output is:
20 45 34 56 54 89 10

Using the Insert Method

To use the insert method in the same node class, we add an insert class to it. This 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. Further, the PrintTree class prints the tree.
Example:

class Node: def __init__(self, data): self.left = None self.right = None self.data = data def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() root = Node(30) root.insert(15) root.insert(40) root.insert(35) root.insert(12) root.insert(20) root.PrintTree()

As a result, the output is:
12 15 20 30 35 40

Conclusion & Practical Application

Using trees in Python can be fun, as we saw in the above examples. These are widely used in different software and applications. A strong grip on this topic can be very beneficial for interview purposes and give you an extra edge. After understanding the principles of a tree, practice some problem sets to test your knowledge of trees in python.

Like this article? Follow us on Facebook and LinkedIn.

Источник

Python — Binary Tree

We create a tree data structure in python by using the concept os node discussed earlier. We designate one node as root node and then add more nodes as child nodes. Below is program to create the root node.

Create Root

We just create a Node class and add assign a value to the node. This becomes tree with only a root node.

Example

class Node: def __init__(self, data): self.left = None self.right = None self.data = data def PrintTree(self): print(self.data) root = Node(10) root.PrintTree()

Output

When the above code is executed, it produces the following result −

Inserting into a Tree

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.

Example

class Node: def __init__(self, data): self.left = None self.right = None self.data = data def insert(self, data): # Compare the new value with the parent node if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Use the insert method to add nodes root = Node(12) root.insert(6) root.insert(14) root.insert(3) root.PrintTree()

Output

When the above code is executed, it produces the following result −

Traversing a Tree

The tree can be traversed by deciding on a sequence to visit each node. As we can clearly see we can start at a node then visit the left sub-tree first and right sub-tree next. Or we can also visit the right sub-tree first and left sub-tree next. Accordingly there are different names for these tree traversal methods.

Tree Traversal Algorithms

Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree.

In-order Traversal

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.

In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the In-order traversal logic is implemented by creating an empty list and adding the left node first followed by the root or parent node.

At last the left node is added to complete the In-order traversal. Please note that this process is repeated for each sub-tree until all the nodes are traversed.

Example

class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Inorder traversal # Left -> Root -> Right def inorderTraversal(self, root): res = [] if root: res = self.inorderTraversal(root.left) res.append(root.data) res = res + self.inorderTraversal(root.right) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.inorderTraversal(root))

Output

When the above code is executed, it produces the following result −

Pre-order Traversal

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the Pre-order traversal logic is implemented by creating an empty list and adding the root node first followed by the left node.

At last, the right node is added to complete the Pre-order traversal. Please note that, this process is repeated for each sub-tree until all the nodes are traversed.

Example

class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Preorder traversal # Root -> Left ->Right def PreorderTraversal(self, root): res = [] if root: res.append(root.data) res = res + self.PreorderTraversal(root.left) res = res + self.PreorderTraversal(root.right) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.PreorderTraversal(root))

Output

When the above code is executed, it produces the following result −

Post-order Traversal

In this traversal method, the root node is visited last, hence the name. First, we traverse the left subtree, then the right subtree and finally the root node.

In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the Post-order traversal logic is implemented by creating an empty list and adding the left node first followed by the right node.

At last the root or parent node is added to complete the Post-order traversal. Please note that, this process is repeated for each sub-tree until all the nodes are traversed.

Example

class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else if data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Postorder traversal # Left ->Right -> Root def PostorderTraversal(self, root): res = [] if root: res = self.PostorderTraversal(root.left) res = res + self.PostorderTraversal(root.right) res.append(root.data) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.PostorderTraversal(root))

Output

When the above code is executed, it produces the following result −

Источник