After a long time I took a look in algorithms and data structure and what I wrote first in Binary Tree and its different traversal in C++. I have never written them in python so I tried to write one. And yes writing them down in python is lot more easier. So lets me first introduce you to the basic concepts of Binary tree then we will code Binary Tree and its traversal using python.
Binary Tree and its traversal using python.
Binary tree are the tree where one node can have only two child and cannot have more than two. Traversal means visiting all the nodes of the Binary tree. There are three types of traversal.
Lets take the below tree for example.
In order traversal means visiting first left, then root and then right.
So the traversal of above tree would be 4 2 5 1 3
Pre Order Traversal
In this traversal we first visit root, then left, then right
It will be something like this 1 2 4 5 3
Post Order traversal
Here we first visit left, then right and then root.
It will be something like this 4 5 2 3 1
If you want to learn data structures in python you can read the below books.
These were the traversal now lets code it in python
class Node: def __init__(self,data): self.left = None self.right = None self.data = data def inOrder(root): if root: inOrder(root.left) print (root.data) inOrder(root.right) def preOrder(root): if root: print (root.data) preOrder(root.left) preOrder(root.right) def postOrder(root): if root: postOrder(root.left) postOrder(root.right) print (root.data) #making the tree root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print inOrder(root) #4 2 5 1 3 print preOrder(root) #1 2 4 5 3 print postOrder(root) #4 5 2 3 1
So this is how you write the binary tree in Python.
Lets have a look at the script.
We made a class Node which represent the node of Binary tree. We initialize the node with data and left and right child as None.
When we add new child we simple use root.left or root.left.left to add a new child.
Now lets have a look at the traversal functions.
In all these functions we took advantage of recursion and passed the subtrees in the functions again to print in proper order. In Inorder function, we first pass the left subtree to Inorder then print the node and then pass the right subtree. Thus made left, root and right. Similarly we did for the other two.
Here we took a look into how to code binary Tree and its traversal using python.
Read about Graphs and its implementation in python here.