The traversal of a binary tree is to visit each node in the tree exactly once. Binary tree traversal is useful in many applications. The order in which nodes of a linear list are visited is clearly from first to last. However, there is no such natural linear order for the nodes of a tree. The methods differ primarily in the order in which they visit the nodes. There are three popular methods of binary tree traversal. These methods are known as inorder traversal, preorder traversal and postorder traversal. In each of these methods nothing need be done to traverse an empty binary tree. The functions used to traverse a tree using these methods can be kept quite short if we understand the recursive nature of the binary tree. Recall that a binary tree is recursive in that each subtree is really a binary tree itself. Thus traversing a binary tree involves visiting the root node and traversing its left and right subtrees. The only difference among the methods is the order in which these three operations are performed. To traverse a nonempty binary tree in preorder , we perform the following three operations:
To traverse a nonempty binary tree in inorder (or symmetric order):
To traverse a nonempty binary tree in postorder :
Many algorithms that use binary trees proceed in two phases. The first phase builds a binary tree, and the second traverses the tree. As an example of such an algorithm, consider the following sorting method. Given a list of numbers in an input file, we wish to print them in ascending order. As we read the numbers, they can be inserted into a binary tree such as the one of Figure 6. When a number is compared with the contents of a node in the tree, a left branch is taken if the number is smaller than the contents of the node and a right branch if it is greater or equal to the contents of the node. Thus if the input list is 20 17 6 8 10 20 7 18 13 12 5 6 The binary tree of Figure 6 is produced.
Figure 6 Such a binary tree has the property that all elements in the left subtree of a node n are less than the contents of n, and all elements in the right subtree of n are greater than or equal to the contents of n. A binary tree that has this property is called a Binary Search tree. If a binary search tree is traversed in inorder (left, root, right) and the contents of each node are printed as the node is visited, the numbers are printed in ascending order. Convince yourself that this is the case for the binary search tree of Figure 6. The program to implement this algorithm is given below /* Program to implement a binary tree */ #include"alloc.h" struct btreenode { struct btreenode *leftchild ; int data ; struct btreenode *rightchild ; } ; main( ) { struct btreenode *bt ; int req, i = 1, num ; bt = NULL ; /* empty tree */ clrscr( ) ; printf ( "Specify the number of data items to be inserted: " ) ; scanf ( "%d", &req ) ; while ( i++ <= req ) { printf ( "Enter the data :" ) ; scanf ( "%d", &num ) ; insert (&bt, num ) ; } clrscr( ) ; printf ( "\nInorder Traversal:" ) ; inorder ( bt ) ; printf ( "\nPreorder Traversal:" ) ; preorder ( bt ) ; printf ( "\nPostorder Traversal: " ) ; postorder ( bt ) ; } /* inserts a new node in a binary search tree */ insert ( struct btreenode **sr, int num ) { if ( *sr == NULL ) { *sr = malloc ( sizeof ( struct btreenode ) ) ; ( *sr ) -> leftchild = NULL ; ( *sr ) -> data =num ; ( *sr ) -> rightchild = NULL ; return ; } else /* search the node to which new node will be attached */ { /* if new data is less, traverse to left */ if ( num < ( *sr ) -> data ) insert ( &( ( *sr ) -> leftchild ), num ) ; else /* else traverse to right */ insert (&( ( *sr ) -> rightchild ), num ) ; } return ; } /*traverse a binary search tree in a LDR (Left-Data-Right) fashion */ inorder ( struct btreenode *sr ) { if ( sr != NULL ) { inorder ( sr -> leftchild ) ; /* print the data of the node whose leftchild is NULL or the path has already been traversed */ printf ( "%d ", sr-> data ) ; inorder ( sr -> rightchild ) ; } else return ; } /* traverse a binary search tree in a DLR (Data-Left-right) fashion */ preorder ( struct btreenode *sr ) { if ( sr != NULL ) { /* print the data of a node */ printf ( "%d ", sr -> data ) ; /* traverse till leftchild is not NULL */ preorder ( sr -> leftchild ) ; /* traverse till rightchild is not NULL */ preorder ( sr -> rightchild ) ; } else return ; } /* traverse a binary search tree in LRD (Left-Right-Data) fashion */ postorder ( struct btreenode *sr ) { if ( sr != NULL ) { postorder ( sr -> leftchild ) ; postorder ( sr -> rightchild ) ; printf ( "%d ", sr -> data ) ; } else return ; } | Interview Puzzles Click here to enter your page's footer (optional).
|
Click here to enter your page's footer (optional).