Binary Tree Implementation in Python

1. Introduction

A Binary Tree is a hierarchical data structure in which each node has at most two children, commonly referred to as the left and right child. It's a fundamental concept that's used in more specialized types of trees like Binary Search Trees, Heaps, and AVL trees.

2. Implementation Steps

1. Define a Node class that contains data, a left child, and a right child.

2. Implement the BinaryTree class that initiates the root node.

3. Provide methods to insert, search, and display the tree using inorder traversal.

3. Implementation in Python

class Node:
    def __init__(self, data):
        self.data = data        # Holds the data for the node
        self.left = None        # Pointer to the left child node
        self.right = None       # Pointer to the right child node
class BinaryTree:
    def __init__(self):
        self.root = None        # Initialize the root of the tree as None
    def insert(self, data):
        # Insert data into the tree
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert_recursive(self.root, data)
    def _insert_recursive(self, node, data):
        # A private helper function to insert data recursively
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert_recursive(node.left, data)
        elif data > node.data:
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert_recursive(node.right, data)
    def search(self, data):
        # Search for data in the tree
        return self._search_recursive(self.root, data)
    def _search_recursive(self, node, data):
        # A private helper function to search for data recursively
        if node is None:
            return False
        if node.data == data:
            return True
        if data < node.data:
            return self._search_recursive(node.left, data)
        return self._search_recursive(node.right, data)
    def inorder(self):
        # Display tree using inorder traversal
        return self._inorder_recursive(self.root)
    def _inorder_recursive(self, node):
        # A private helper function for inorder traversal
        result = []
        if node:
            result += self._inorder_recursive(node.left)
            result.append(node.data)
            result += self._inorder_recursive(node.right)
        return result
# Test the BinaryTree class
bt = BinaryTree()
bt.insert(5)
bt.insert(3)
bt.insert(7)
bt.insert(1)
bt.insert(4)
print("Inorder traversal:", bt.inorder())
print("Search for 4:", bt.search(4))
print("Search for 8:", bt.search(8))

Output:

Inorder traversal: [1, 3, 4, 5, 7]
Search for 4: True
Search for 8: False

Explanation:

1. We start with the Node class, which is designed to hold its data, a left child, and a right child.

2. The BinaryTree class has a root which is the starting node of the tree.

3. The insert method allows adding data to the tree. If the tree is empty, the root node is created. Otherwise, a recursive method (_insert_recursive) is used to find the correct location for the new node.

4. The search method checks if a data value exists in the tree. It uses a helper method (_search_recursive) to perform the search operation.

5. The inorder method is used to display the tree using the inorder traversal technique, which gives a sorted sequence for binary search trees.

6. In the test section, we create a binary tree, insert some values, and then perform a search and display operations.

Related Data Structures in Python


Comments

Post a Comment