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:
20
30
40
50
60
70
80
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.