Python Program to Construct a Tree and Perform Tree Operations

In the following example of a Python program that constructs a binary tree and performs some common tree operations :

Program :

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

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)

    def search(self, value):
        return self._search(value, self.root)

    def _search(self, value, node):
        if node is None:
            return False
        elif value == node.value:
            return True
        elif value < node.value:
            return self._search(value, node.left)
        else:
            return self._search(value, node.right)

    def traverse_inorder(self):
        nodes = []
        if self.root is not None:
            self._traverse_inorder(self.root, nodes)
        return nodes

    def _traverse_inorder(self, node, nodes):
        if node.left is not None:
            self._traverse_inorder(node.left, nodes)
        nodes.append(node.value)
        if node.right is not None:
            self._traverse_inorder(node.right, nodes)

# Example usage
tree = BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)
tree.insert(6)
tree.insert(8)

print(f"Tree contains 5? {tree.search(5)}")
print(f"Tree contains 2? {tree.search(2)}")

print("Inorder traversal:", tree.traverse_inorder())

Output :

Tree contains 5? True
Tree contains 2? False
Inorder traversal: [1, 3, 4, 5, 6, 7, 8]

In this example, the `Node` class represents a node in the binary tree, with a value and pointers to its left and right children. The `BinaryTree` class represents the entire binary tree, with a pointer to the root node.

The `insert()` method inserts a new node with the specified value into the tree, maintaining the binary search tree property. The `search()` method searches for a node with the specified value in the tree, returning `True` if found and `False` otherwise. The `_insert()` and `_search()` methods are helper methods that perform the actual recursion through the tree.

The `traverse_inorder()` method performs an inorder traversal of the tree, returning a list of the node values in ascending order. The `_traverse_inorder()` method is a helper method that performs the actual recursion through the tree.

The example usage at the bottom of the program constructs a binary search tree with some example values, and then performs a search for the values 5 and 2. It also performs an inorder traversal of the tree and prints the resulting list of node values.