Earlier we have learned about Linked List and one of its types Doubly Linked List. Also, we have gone through how binary trees are represented using arrays. If you aren’t aware, you can check them out from the links provided in the “References and Recommendations” section.
So, here we shall discuss how to represent binary trees using a linked list and a queue to implement it.
Structure:
The above picture depicts the structure of the node of a binary tree.
Left: It points to the left child of the node.
Right: It points to the right child of the node.
Data: It contains the information of the node.
Representation:
The given binary tree is represented in the form of a linked list. The left of A points to its left child B and right points to its right child C. The left and right pointers of the leaf nodes (D, E, and F here) always remain null. How do we implement it in a programming language? We shall now see.
Prerequisites:
The order of visiting a tree to display its nodes and data is called a traversal. There are three types of traversals. Namely,
- Inorder: LDR
- Preorder: DLR
- Postorder: LRD
L → Left node; R → Right node; D → Data
The order mentioned across the types is the order used by them to traverse the binary tree.
For sample,
Inorder: LDR
The left-most child is visited first followed by the data or root of the child and finally, the right-most child is visited. This will be more clear once we take an example.
Let’s take from the root which is ‘A’. The left child is B but we shouldn’t take it. The left child of B is D and it is the leaf node. D is considered as left-most and first visited in Inorder traversal. It is followed by its root B and then sibling E which is right-most. DBE is the initial traversal. Then left part of root A is completed and then data has to be printed which is the root A.
While traversing through the right sub-tree, there is a left child to the root C. Then we will apply inorder rule here. The left-most child is visited first and then the root. The order of traversal is FC.
Final Inorder traversal: DBEAFC
Similarly,
Preorder Traversal: ABDECF
Postorder Traversal: DEBFCA
These are the prerequisites we should be aware of to display the elements of the tree. We shall now go through the implementation in the Python programming language.
IMPLEMENTATION IN PYTHON
#IMPLEMENTATION OF BINARY TREE USING LINKED LIST IN PYTHON
#INCLUDES INORDER, PREORDER AND POSTORDER TRAVERSALS.
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
#Represent the root of binary tree
self.root = None
#Function to add new node to the binary tree
def insertNode(self, data):
#Create a new node
newNode = Node(data)
#Check whether tree is empty
if(self.root == None):
self.root = newNode
return;
else:
queue = []
#Add root to the queue if root is not empty
queue.append(self.root)
while(True):
#the first elements of the queue are popped
#as they will be respective left and right children
node = queue.pop(0)
#If node has both left and right child, add both the child to queue
if(node.left != None and node.right != None):
queue.append(node.left)
queue.append(node.right)
else:
#If node has no left child, make newNode as left child
if(node.left == None):
node.left = newNode
queue.append(node.left)
else:
#If node has left child but no right child, make newNode as right child
node.right = newNode
queue.append(node.right)
break;
#inorder() will perform inorder traversal on binary search tree
def inorderTraversal(self, node):
#Check if tree is empty
if(self.root == None):
print("Tree is empty")
return
else:
if(node.left != None):
self.inorderTraversal(node.left)
print(node.data,end=" ")
if(node.right!= None):
self.inorderTraversal(node.right)
bt = BinaryTree()
#Adding nodes to the binary tree
bt.insertNode('A')
#A will become root node of the tree
print("Binary tree after insertion: ")
#Binary after inserting nodes
bt.inorderTraversal(bt.root)
bt.insertNode('B')
bt.insertNode('C')
#B will become left child and C will become right child of root node A
print("\nBinary tree after insertion: ")
#Binary after inserting nodes
bt.inorderTraversal(bt.root)
bt.insertNode('D')
bt.insertNode('E')
#D will become left child and E will become right child of node B
print("\nBinary tree after insertion: ")
#Binary after inserting nodes
bt.inorderTraversal(bt.root)
bt.insertNode('F')
#F will become the left child
print("\nBinary tree after insertion: ")
#Binary after inserting nodes
bt.inorderTraversal(bt.root)
PREORDER TRAVERSAL
#preorder() will perform preorder traversal on binary search tree
def preorderTraversal(self, node):
#Check whether tree is empty
if(self.root == None):
print("Tree is empty")
return
else:
print(node.data)
if(node.left != None):
self.inorderTraversal(node.left)
if(node.right!= None):
self.inorderTraversal(node.right)
POSTORDER TRAVERSAL
#postorder() will perform inorder traversal on binary search tree
def postorderTraversal(self, node):
#Check whether tree is empty
if(self.root == None):
print("Tree is empty")
return
else:
if(node.left != None):
self.inorderTraversal(node.left)
if(node.right!= None):
self.inorderTraversal(node.right)
print(node.data)
DOWNLOAD CODE FROM HERE
Techprodezza 