Preorder Traversal
Tree traversal is a type of graph traversal and refers to visiting every node in the tree. There are various methods for traversing the tree. One of the popular traversal methods is preorder traversal which follows the rule of visiting the root of the tree (first), left side of the tree and then the right side of the tree. Preorder traversals can be used to make prefix notations or polish notation from expression trees.
Binary Tree
A binary tree is a non-linear data structure in which every node has at a most maximum of two children. So, in terms of binary tree construction, we should have a node with three-pointers one to hold data and two for left and right nodes.
class Tree {
public class Node {
int data;
Node right;
Node left;
Node(int data) {
this.data = data;
left = right = null;
}
}
In this above tree class with inner node class has one instance member data and two objects of Node class left and right. For every new node, we use Node(int data ) constructor to assign data to that node and set left and right as null.
Tree.Node t = new Tree().new Node(1);
t.left = new Tree().new Node(2);
t.left.left = new Tree().new Node(4);
t.left.right = new Tree().new Node(5);
t.right = new Tree().new Node(3);
Algorithm :
- Visit the root vertex
- Traverse the left subtree
- Traverse the right subtree
Preorder traversal for the tree is: 1 2 4 5 3
Program for iterative preorder traversal:
public void preOrder(Node root) {
Stack<Node> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
Node e = s.pop();
System.out.print(e.data + " ");
if (e.right != null) {
s.push(e.right);
}
if (e.left != null) {
s.push(e.left);
}
}
}
In the above program, a stack is used in order to hold the elements of each node,
At first, the root is pushed into the stack and while loop runs till the stack is empty and
prints the top element of the stack in every iteration.
I hope you guys liked this article, here are some other articles you may like:
){kind=link}
0 Comments