[ Data Structures with Java ] Section 17.3 : Euler Tour Traversal

Preface :
Up to this point, all of our three traversal algorithms visit each node exactly once. For instance, the inorder traversal visit the node between visiting the left subtree and the right subtree. We need a more general tree traversal algorithm for some applications, one that will visit each node more than once. The Euler tour traversal provides a solution. We assume that the edges and nodes of a tree T are contained in a walkway with walls on both sides. The Euler tour is a walk around T, touching each node as we encounter it, always keeping the wall on our right. The tour visits each node three times :

* On the left, before the Euler tour of the node's left subtree.
* From below, as we finish the tour of the left subtree.
* On the right, after we finish the Euler tour of the right subtree.

If the node is a leaf, all of the visits are combined into a single visit. The walk in below figure traverses an expression tree. The directed edges trace the Euler tour beginning with the root. We encounter nodes in the following order :
Tour visits : + * a * - d - e - * + / b / c / +

The following pseudo-code description of the algorithm summarize the Euler tour. A single visit to a leaf node and multiple visits to a nonleaf node are simply denoted by "visit" althrough, in practice, an implementation does not perform the same action.

- Algorithm eulerTour(TNode t) :

view plaincopy to clipboardprint?

1. if t != null  
2.     if t is a leaf node  
3.         visit t  
4.     else   
5.         visit t  
6.         eulerTour(t.left);  
7.         visit t  
8.         eulerTour(t.right);  
9.         visit t  

The recursive algorithm allows us to pause three times to perform a visit. You should note that the Euler tour generalizes the inorder, postorder and preorder three traversals. For instance, if the visit on the left and the vist on the right do nothing, the Euler tour is equivalent to an inorder traversal.
An expression tree provides a good application of a Euler tour. The traversal includes visits that add parentheses and that access the value of a node. The result is a string that represent an equivalent fully parenthesized expression. The algorithm is straightforward. A visit to a leaf node (operand) inserts the operand in the string. For a nonleaf node (operator), insert a '(' as the visit on the left, insert the operator as the visit from below and insert a ')' as the visit on the right. The static method fullParen() in the BinaryTree class implements the algorithm :

- Method fullParen() implementation :

view plaincopy to clipboardprint?

1. public static String fullParen(TNode t){  
2.     String s = "";  
3.     if(t.left == null && t.right == null) // visit leaf node  
4.         s+=t.nodeValue;  
5.     else {  
6.         s+='(';  
7.         s+=fullParen(t.left);   //Visit on left  
8.         s+=t.nodeValue;         //Visit from below  
9.         s+=fullParen(t.right);  //Visit on right  
10.         s+=')';  
11.     }  
12.     return s;  
13. }  

- Demo on Method fullParen() :

view plaincopy to clipboardprint?

1. public static void fullParenDemo(){  
2.     TNode root = new TNode('+');  
3.     root.left = new TNode('*');  
4.     root.left.left = new TNode('a');  
5.     root.left.right = new TNode('-');  
6.     root.left.right.left = new TNode('d');  
7.     root.left.right.right = new TNode('e');  
8.     root.right = new TNode('/');  
9.     root.right.left = new TNode('b');  
10.     root.right.right = new TNode('c');  
11.     System.out.println("Postfix exp: "+postorderDisplay(root));  
12.     System.out.println("Full Paren: "+fullParen(root));  
13. }  

Run:
Postfix exp: a d e - * b c / +
Full Paren: ((a*(d-e))+(b/c))

Supplement :
* Wiki : Eulerian Path

In graph theory, an Eulerian trail is a trail in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian trail which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736.

This message was edited 4 times. Last update was at 19/10/2010 10:05:15