aud.example.IterativePreorderTraversal Class Reference

example: transform recursive preoder traversal to iterative algorithm More...

Static Public Member Functions
static void	recursive_traversal (BinaryTree< String > node, int level)
	recursive algorithm More...
static void	iterative_traversal (BinaryTree< String > root)
	iterative algorithm More...
static void	level_order_traversal (BinaryTree< String > root)
	implement level-order traversal More...
static BinaryTree< String >	exampleTree ()
	generate some tree More...
static void	indent (int n)
	indent output on System.err More...
static void	main (String[] args)

Detailed Description

example: transform recursive preoder traversal to iterative algorithm

We use VerboseStack to show that recursive_traversal and iterative_traversal effectively do the same.

In addition, a level_order_traversal is obtained by replacing the stack by a VerboseQueue.

See also

BinaryTree

BinaryTreeTraversal

Definition at line 17 of file IterativePreorderTraversal.java.

Member Function Documentation

exampleTree()

static BinaryTree< String > aud.example.IterativePreorderTraversal.exampleTree ( )

static

generate some tree

Definition at line 67 of file IterativePreorderTraversal.java.

                                                 {
    BinaryTree<String> root=new BinaryTree<String>
    ("A",
      new BinaryTree<String>("B",
        new BinaryTree<String>("C"),
        new BinaryTree<String>("D")),
        new BinaryTree<String>("E",
          new BinaryTree<String>("F"),
          new BinaryTree<String>("G",
            new BinaryTree<String>("H",
              new BinaryTree<String>("I",
                new BinaryTree<String>("J"),null),
              new BinaryTree<String>("K")
            ),
            null
          )
        )
    );
    return root;
  }

Referenced by aud.example.IterativePreorderTraversal.main().

Here is the caller graph for this function:

indent()

static void aud.example.IterativePreorderTraversal.indent ( int  n )

static

indent output on System.err

Definition at line 89 of file IterativePreorderTraversal.java.

                                   {
    for (int i=0;i<n;++i)
      System.err.print(" ");
  }

Referenced by aud.example.IterativePreorderTraversal.recursive_traversal().

Here is the caller graph for this function:

iterative_traversal()

static void aud.example.IterativePreorderTraversal.iterative_traversal ( BinaryTree< String >  root )

static

iterative algorithm

Definition at line 34 of file IterativePreorderTraversal.java.

                                                                  {
    VerboseStack<BinaryTree<String>> stack=
      new VerboseStack<BinaryTree<String>>();
    stack.push(root);   // initialize
 
    while(!stack.is_empty()) {
      BinaryTree<String> node=stack.pop();
      if (node!=null) {
        System.out.println("output "+node);
        stack.push(node.getRight()); // mind order: right first
        stack.push(node.getLeft());
      }
    }
  }

References aud.BinaryTree< T >.getLeft(), aud.BinaryTree< T >.getRight(), aud.Stack< T >.is_empty(), aud.example.VerboseStack< T >.pop(), and aud.example.VerboseStack< T >.push().

Referenced by aud.example.IterativePreorderTraversal.main().

Here is the call graph for this function:

Here is the caller graph for this function:

level_order_traversal()

static void aud.example.IterativePreorderTraversal.level_order_traversal ( BinaryTree< String >  root )

static

implement level-order traversal

Definition at line 50 of file IterativePreorderTraversal.java.

                                                                    {
    VerboseQueue<BinaryTree<String>> queue=
      new VerboseQueue<BinaryTree<String>>();
    queue.enqueue(root);   // initialize
 
    while(!queue.is_empty()) {
      BinaryTree<String> node=queue.dequeue();
      if (node!=null) {
        System.out.println("output "+node);
        queue.enqueue(node.getLeft()); // mind order: left first
        queue.enqueue(node.getRight());
      }
    }
  }

References aud.example.VerboseQueue< T >.dequeue(), aud.example.VerboseQueue< T >.enqueue(), aud.BinaryTree< T >.getLeft(), aud.BinaryTree< T >.getRight(), and aud.Queue< T >.is_empty().

Referenced by aud.example.IterativePreorderTraversal.main().

Here is the call graph for this function:

Here is the caller graph for this function:

main()

static void aud.example.IterativePreorderTraversal.main ( String[]  args )

static

Definition at line 94 of file IterativePreorderTraversal.java.

                                         {
    BinaryTree<String> tree=exampleTree();
 
    System.out.println("recursive traversal:");
    recursive_traversal(tree,0);
    System.out.println();
 
    System.out.println("iterative traversal:");
    iterative_traversal(tree);
    System.out.println();
 
    System.out.println("level order traversal:");
    level_order_traversal(tree);
  }

References aud.example.IterativePreorderTraversal.exampleTree(), aud.example.IterativePreorderTraversal.iterative_traversal(), aud.example.IterativePreorderTraversal.level_order_traversal(), and aud.example.IterativePreorderTraversal.recursive_traversal().

Here is the call graph for this function:

recursive_traversal()

static void aud.example.IterativePreorderTraversal.recursive_traversal ( BinaryTree< String >  node, int  level  )

static

recursive algorithm

Definition at line 21 of file IterativePreorderTraversal.java.

                                                                {
    indent(level);
    System.err.println("enter with node="+node);
    if (node!=null) {
      System.out.println("output "+node);
      recursive_traversal(node.getLeft(),level+1);
      recursive_traversal(node.getRight(),level+1);
    }
    indent(level);
    System.err.println("leave with node="+node);
  }

References aud.BinaryTree< T >.getLeft(), aud.BinaryTree< T >.getRight(), aud.example.IterativePreorderTraversal.indent(), and aud.example.IterativePreorderTraversal.recursive_traversal().

Referenced by aud.example.IterativePreorderTraversal.main(), and aud.example.IterativePreorderTraversal.recursive_traversal().

Here is the call graph for this function:

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• IterativePreorderTraversal.java