Showing posts with label Binary Tree. Show all posts
Showing posts with label Binary Tree. Show all posts

Monday, 24 December 2012

Tree Traversal(Binary Tree)


Tree Traversal or Traversing a binary tree is a method that refers as "to visit each node of tree in a specified order(exactly one times per node)".

Ways to traverse the tree:-


1)In-order Traversal:-

Procedure:-1)Traverse the left sub-tree.

2)Visits Root node.
3)Post Order traversal.

In simple words....Left-->Root-->Right or L(e)-->R-->R(i)


2)Post Order Traversal:-


Procedure:-1)Traverse Right Sub Tree.

2)Traverse Left Sub Tree.
3)Visits Root node.

In simple words....Right-->Left-->Root R(i)-->L(e)-->R 

3)Preorder Traversal:-


Procedure:-1)Visits Root node.

2)Traverse Left Sub Tree.
3)Traverse Right Sub Tree.

In simple words....Root-->Left-->Right or R-->L(e)-->R(i)


Let us take an examples:-


Example 1:-






In Order:-E,B,D,G,K,J,I,H,F,A,C,N,M.


Post order:-E,K,J,I,H,G,F,D,B,N,M,C,A.


Preorder:-A,B,E,D,F,G,H,I,J,K,C,M,N.


Example 2:-






In Order:-K,G,L,H,M,D,B,A,E,O,Q,R,S,T,P,N,C.

Post Order:-K,L,M,H,G,D,B,T,S,R,Q,P,O,N,E,C,A.


Preorder:-A,B,D,G,K,L,H,M,C,E,N,O,P,Q,R,S,T.


Example 3:-(a*b)+(c/d)-e+(f^g)




In order:-a*b+c/d-e+f^g.

Post Order:-ab*cd/+efg^+-.

Preorder:--+*ab/cd+e^fg.

Example:- 4:-a*(b+c)-d/e+(f%g)^h.




In Order:-a*b+c-d/e+f%g^h.

Post Order:-abc+*de/-fg%h^+.

Preorder:-+-*a+bc/de^%fgh.



If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.

What is Binary Tree?


Binary Tree in data structure are defined as those tree who's node have 0,1,2 children(s).As we know that general trees are made up of node,root etc.So binary tree also contains root,node,left pointer and the right pointer.In binary tree,tree consist node are called as root node,left and right node are called as Sub-tree.In this tree the degree of each  node is less than 2(<2).This tree deals in C ++,Java code etc.




Types of binary tree:-

1)Complete binary Tree:-Complete binary tree are those tree whose degree of every node is 2 or o.

No. of leaf node=2^level nodes.

Example:-




2)Almost complete Binary Tree:-In complete binary tree all the leaf are at the same level but in this type of binary tree all the leaf are in the bottom level.




3)Strictly binary tree:-Strictly binary tree are those tree whose degree of every node is 0 or 2.

Total no. of node=(2n-1).
where n=no. of leaf node.






If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.