example: visualize binary tree traversal More...

Inheritance diagram for aud.example.BinaryTreeTraversal:

Collaboration diagram for aud.example.BinaryTreeTraversal:

Classes
class	MyTree
	simple tree with decorator for visualization

Public Member Functions
	BinaryTreeTraversal (MyTree tree)
	create traversal application for `tree` More...

void	traverse (String type)
	start traversal More...

Public Member Functions inherited from aud.util.SingleStepper
	SingleStepper (JFrame parent)
	create new instance More...

	SingleStepper (String caption)
	create new instance More...

JFrame	parent ()
	get parent widget More...

void	halt (String text, int timeout)
	display `text` and wait for user or `timeout` More...

void	setTimeout (int timeout)
	Set global timeout. More...

SingleStepper	whereAmI ()
	print location of calling code More...

SingleStepper	showSource ()
	jmp to caller's location in editor (emacs only) More...

void	halt (String text)
	display `text` and wait for user (or global timeout) More...

void	halt ()
	wait for user More...

Static Public Member Functions
static MyTree	exampleTree ()
	generate some tree More...

static void	main (String[] args)

static void	main (String[] args)

Protected Member Functions
void	onHalt ()

void	output (MyTree node)
	output node during traversal More...

void	see (MyTree node)
	arrived `node` for first time (for visualization) More...

void	preorder (MyTree node)
	recursive preorder traversal More...

void	inorder (MyTree node)
	recursive inorder traversal More...

void	postorder (MyTree node)
	recursive postorder traversal More...

void	levelorder (MyTree root)
	level order traversdal More...

Protected Member Functions inherited from aud.util.SingleStepper
JComponent	createComponents ()

void	onNext ()
	call on button pressed More...

void	println (String text)
	print to both, text area and stdout More...

void	onHalt ()

Protected Attributes
MyTree	tree_ = null

DotViewer	viewer_

SimpleDecorator	decorator

Protected Attributes inherited from aud.util.SingleStepper
JFrame	frame

JTextArea	history

JButton	next

Object	monitor = new Object()

int	timeout = 0

Detailed Description

example: visualize binary tree traversal

See also: aud.BinaryTree; aud.example.IterativePreorderTraversal; aud.BinaryTreeTraversal BinaryTreeTraversal (iterators)

Definition at line 12 of file example/BinaryTreeTraversal.java.

Constructor & Destructor Documentation

◆ BinaryTreeTraversal()

aud.example.BinaryTreeTraversal.BinaryTreeTraversal ( MyTree tree )

create traversal application for tree

Definition at line 20 of file example/BinaryTreeTraversal.java.

                                          {
    super("aud.example.BinaryTreeTraversal");
    tree_=tree;
    decorator=(SimpleDecorator) tree_.getDecorator(); // same per tree
  }

References aud.example.BinaryTreeTraversal.decorator, and aud.example.BinaryTreeTraversal.tree_.

Member Function Documentation

◆ exampleTree()

static MyTree aud.example.BinaryTreeTraversal.exampleTree ( )

static

generate some tree

Definition at line 45 of file example/BinaryTreeTraversal.java.

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

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

Here is the caller graph for this function:

◆ inorder()

void aud.example.BinaryTreeTraversal.inorder ( MyTree node )

protected

recursive inorder traversal

Definition at line 123 of file example/BinaryTreeTraversal.java.

                                      {
    if (node!=null) {
      see(node);
 
      inorder((MyTree) node.getLeft());
      output(node);
      inorder((MyTree) node.getRight());
    }
  }

References aud.example.BinaryTreeTraversal.inorder(), aud.example.BinaryTreeTraversal.output(), and aud.example.BinaryTreeTraversal.see().

Referenced by aud.example.BinaryTreeTraversal.inorder(), and aud.example.BinaryTreeTraversal.traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ levelorder()

void aud.example.BinaryTreeTraversal.levelorder ( MyTree root )

protected

level order traversdal

Definition at line 143 of file example/BinaryTreeTraversal.java.

                                         {
    Queue<MyTree> queue=new Queue<MyTree>();
    queue.enqueue(null);     // marker: next level
    queue.enqueue(root);
    int level=0;             // keep track of/count levels
    while (!queue.is_empty()) {
      MyTree node=queue.dequeue();
 
      if (node==null) {
        halt("enter next level "+(level++));
        if (!queue.is_empty())
          queue.enqueue(null); // marker: next level
      }
      else {
        see(node);
 
        if (node.getLeft()!=null)
          queue.enqueue((MyTree) node.getLeft());
        if (node.getRight()!=null)
          queue.enqueue((MyTree) node.getRight());
        output(node);
      }
    }
  }

References aud.Queue< T >.dequeue(), aud.Queue< T >.enqueue(), aud.util.SingleStepper.halt(), aud.Queue< T >.is_empty(), aud.example.BinaryTreeTraversal.output(), and aud.example.BinaryTreeTraversal.see().

Referenced by aud.example.BinaryTreeTraversal.traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ main()

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

static

Reimplemented from aud.util.SingleStepper.

Definition at line 168 of file example/BinaryTreeTraversal.java.

                                         {
    BinaryTreeTraversal app=
      new BinaryTreeTraversal(BinaryTreeTraversal.exampleTree());
 
    if (args.length==0)
      app.traverse("preorder");
    else
      for (String type : args)
        app.traverse(type);
 
    app.halt("QUIT");
    System.exit(0);
  }

References aud.example.BinaryTreeTraversal.exampleTree(), aud.util.SingleStepper.halt(), and aud.example.BinaryTreeTraversal.traverse().

Here is the call graph for this function:

◆ onHalt()

void aud.example.BinaryTreeTraversal.onHalt ( )

protected

Reimplemented from aud.util.SingleStepper.

Definition at line 26 of file example/BinaryTreeTraversal.java.

                                    {
    if (tree_!=null)
      viewer_.display(tree_);
  }

References aud.util.DotViewer.display(), aud.example.BinaryTreeTraversal.tree_, and aud.example.BinaryTreeTraversal.viewer_.

Here is the call graph for this function:

◆ output()

void aud.example.BinaryTreeTraversal.output ( MyTree node )

protected

output node during traversal

See also: traverse

Definition at line 69 of file example/BinaryTreeTraversal.java.

                                     {
    decorator.markNode(node);
    decorator.highlightNode(node);
    decorator.setGraphLabel(decorator.getGraphLabel()+node);
    halt("output "+node);
  }

References aud.example.BinaryTreeTraversal.decorator, aud.util.CommonGraphvizDecorator.getGraphLabel(), aud.util.SingleStepper.halt(), aud.util.SimpleDecorator.highlightNode(), aud.util.SimpleDecorator.markNode(), and aud.util.CommonGraphvizDecorator.setGraphLabel().

Referenced by aud.example.BinaryTreeTraversal.inorder(), aud.example.BinaryTreeTraversal.levelorder(), aud.example.BinaryTreeTraversal.postorder(), and aud.example.BinaryTreeTraversal.preorder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ postorder()

void aud.example.BinaryTreeTraversal.postorder ( MyTree node )

protected

recursive postorder traversal

Definition at line 133 of file example/BinaryTreeTraversal.java.

                                        {
    if (node!=null) {
      see(node);
 
      postorder((MyTree) node.getLeft());
      postorder((MyTree) node.getRight());
      output(node);
    }
  }

References aud.example.BinaryTreeTraversal.output(), aud.example.BinaryTreeTraversal.postorder(), and aud.example.BinaryTreeTraversal.see().

Referenced by aud.example.BinaryTreeTraversal.postorder(), and aud.example.BinaryTreeTraversal.traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ preorder()

void aud.example.BinaryTreeTraversal.preorder ( MyTree node )

protected

recursive preorder traversal

Definition at line 113 of file example/BinaryTreeTraversal.java.

                                       {
    if (node!=null) {
      see(node);
 
      output(node);
      preorder((MyTree) node.getLeft());
      preorder((MyTree) node.getRight());
    }
  }

References aud.example.BinaryTreeTraversal.output(), aud.example.BinaryTreeTraversal.preorder(), and aud.example.BinaryTreeTraversal.see().

Referenced by aud.example.BinaryTreeTraversal.preorder(), and aud.example.BinaryTreeTraversal.traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ see()

void aud.example.BinaryTreeTraversal.see ( MyTree node )

protected

arrived node for first time (for visualization)

Definition at line 76 of file example/BinaryTreeTraversal.java.

                                  {
    decorator.markEdge(node);
  }

References aud.example.BinaryTreeTraversal.decorator, and aud.util.SimpleDecorator.markEdge().

Referenced by aud.example.BinaryTreeTraversal.inorder(), aud.example.BinaryTreeTraversal.levelorder(), aud.example.BinaryTreeTraversal.postorder(), and aud.example.BinaryTreeTraversal.preorder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ traverse()

void aud.example.BinaryTreeTraversal.traverse ( String type )

start traversal

Parameters

type	denotes the type of traversal "preorder", "inorder","postorder"

Exceptions

RuntimeException for unknown type

Definition at line 85 of file example/BinaryTreeTraversal.java.

                                    {
    decorator.clear();
    decorator.setGraphLabel("Traversal: ");
 
    if (type.toLowerCase().startsWith("pre")) {
      halt("START preorder traversal");
      preorder(tree_);
    }
    else if (type.toLowerCase().startsWith("in")) {
      halt("START inorder traversal");
      inorder(tree_);
    }
    else if (type.toLowerCase().startsWith("post")) {
      halt("START postorder traversal");
      postorder(tree_);
    }
    else if (type.toLowerCase().startsWith("level")) {
      halt("START level-order traversal");
      levelorder(tree_);
    }
    else
      throw new RuntimeException("unknown traversal '"+type+"'");
 
    decorator.highlightNode(null);
    halt("FINISHED");
  }