“We have seen binary trees and specific use cases of binary trees!!.. But trees doesn’t need to be always binary!!.. one root can have multiple children.. there can be cycles.. When these cycles are created, they are known as graphs!!.. The structures are all application based!!.. But how would you traverse it is not!!.. There are specific ways to visit the nodes in a tree.”
Introduction
As we already studied about heap in the previous article, you should have noted two ways of moving inside the tree: up-heap and down-heap. In up-heap, we move from down to top and down-heap, top to bottom. This is a form of traversal which is application specific, specific to heap. Moreover, insertion happens in left-to-right, that is, fill all the above nodes before filling the next level which is kind of Level order or breadth first. Similarly there are many ways a tree can be traversed.
Concept
Tree must be understood as a type of graph from now on. In a graph, the main applications are derived around the traversal which we will see soon. Similar to that, even in a tree, there are many applications linked with a tree traversal. The types of traversal’s possible in a tree are,
- Normal graph traversals – Breadth First (also known as level-order in a binary tree), Depth First
- Normal tree traversals – In-order, Pre-order, Post-order
You can do all the above traversals in a tree depending upon the application.
Diagrams for each of the Tree traversals, along with level-order,
Courtesy: http://www.macs.hw.ac.uk/flex/BScCS/ds1/activity10.html
Code
#define PARENT(i) i-1/2#define LEFT(i) 2*i+1#define RIGHT(i) 2*i+2#define ARRAYSIZE(a) sizeof(a)/sizeof(a[0])
int A[14] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};/*The tree looks like this, 1 2 3 4 5 6 7 8 9 10 11 12 13 14preorder: root=>left=>right1. is(root) => left => is(root), until root = NULL2. visited(root) => right => is(root) => left => is(root), until root=NULL 1 2 4 8 9 5 10 11 3 6 12 13 7 14postorder: left=>right=>root8 9 4 10 11 5 2 12 13 6 14 7 3 1*/void preorder_stack(int idx)
{ Stack<int> obj; int j= idx; while(j < ARRAYSIZE(A)) { int i = j; // move to root till left // note, this runs for all the root // even the right root!! while(i < ARRAYSIZE(A)) { std::cout<<A[i]<<" ";obj.push(i);
i=LEFT(i);
}
// move to the right int val;obj.pop(val);
j=RIGHT(val);
// remove leaf less nodes while(j > ARRAYSIZE(A)) {obj.pop(val);
j=RIGHT(val);
}
}
}
void preorder(int idx)
{ if ( idx < ARRAYSIZE(A)){ std::cout<<A[idx]<<" ";preorder(LEFT(idx));
preorder(RIGHT(idx));
}
}
void postorder(int idx)
{ if(idx < ARRAYSIZE(A)) {postorder(LEFT(idx));
postorder(RIGHT(idx));
std::cout<<A[idx]<<" ";}
}
void inorder(int idx)
{ if(idx < ARRAYSIZE(A)) {inorder(LEFT(idx));
std::cout<<A[idx]<<" ";inorder(RIGHT(idx));
}
}
void main(){preorder_stack(0);
std::cout<<endl;
preorder(0);
std::cout<<endl;
postorder(0);
std::cout<<endl;
}
Important points
- This algorithm uses array which is not usual. Mostly you would see linked list based implementation
- We will see more of linked list in coming chapters before jumping into trees using linked list
- Preorder – we need to visit all the roots at the left and then right, but whenever we see root, we need to make sure that root is visited first!! then left and then right
- Post order – visit all left and right nodes, before visiting the root
- Inorder – visit left node and then the root and the right node.
- Only for preorder, i have written an implementation using Stack, iterative way. It can be reused for all others and very useful when you need to do traversal using iterations.
No comments:
Post a Comment