Python program to implement binary tree data structure

Binary trees are a fundamental data structure often used in computer science. They are a type of tree data structure in which each node has at most two children, referred to as the left child and the right child.

The following code is an example of a Python program that implements a binary tree data structure:

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

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.val)
        inorder_traversal(node.right)

def insert_node(node, key):
    if node is None:
        return Node(key)
    else:
        if node.val < key:
            node.right = insert_node(node.right, key)
        else:
            node.left = insert_node(node.left, key)
    return node

root = None
root = insert_node(root, 50)
insert_node(root, 30)
insert_node(root, 20)
insert_node(root, 40)
insert_node(root, 70)
insert_node(root, 60)
insert_node(root, 80)

inorder_traversal(root)

Let’s break down this code and explain what each line does.

First, we define a Node class that represents a single node in the binary tree. Each node has a left and right child as well as a val attribute that holds the node’s value.

Next, we define a function called inorder_traversal which performs an inorder traversal of the binary tree, printing out the values of each node in ascending order.

Finally, we define a function called insert_node which inserts a new node into the binary tree. If the binary tree is empty, the function creates a new node with the provided key value. Otherwise, the function recursively traverses the binary tree to find the correct location for the new node, inserting it as the left or right child of a leaf node as necessary.

To create a new binary tree, we first create a root node and insert the other nodes by calling the insert_node function with the root node as the first argument.

When we run this code, it should output the following:

This output indicates that our binary tree has been correctly constructed and traversed in order.

Conclusion

In conclusion, the binary tree is a useful data structure for organizing hierarchical data. With this Python program, you can easily implement a binary tree data structure and perform operations such as inserting nodes and traversing the tree. This kind of program will be useful when working with large sets of data that need to be organized in a hierarchical manner.

Python program to implement binary tree data structure

Python program to implement binary tree data structure

Conclusion

Related

Top