Simple binary tree. More...

Inheritance diagram for aud.BinaryTree< T >:

Collaboration diagram for aud.BinaryTree< T >:

Public Member Functions
	BinaryTree (T data)
	create new root node without children More...

	BinaryTree (T data, BinaryTree< T > left, BinaryTree< T > right)
	create new root node with children More...

BinaryTree< T >	setLeft (BinaryTree< T > tree)
	set left subtree More...

BinaryTree< T >	setRight (BinaryTree< T > tree)
	set right subtree More...

void	setData (T data)
	set node data More...

T	getData ()
	get node data More...

BinaryTree< T >	getParent ()
	get node's parent or `null` for root More...

BinaryTree< T >	getLeft ()
	get left child or `null` More...

BinaryTree< T >	getRight ()
	get right child or `null`) More...

String	toDot ()
	Get dot representation. More...

GraphvizDecorator	getDecorator ()
	get decoration or `null` More...

boolean	isRoot ()
	Iscode this} root? More...

boolean	isLeaf ()
	Is `this` a leaf? More...

BinaryTree< T >	getRoot ()
	traverse upwards to find root node More...

BinaryTreeTraversal< T >.Preorder	preorder ()
	Get preorder iterator over nodes in tree . More...

BinaryTreeTraversal< T >.Inorder	inorder ()
	Get inorder iterator over nodes in tree . More...

BinaryTreeTraversal< T >.Postorder	postorder ()
	Get postorder iterator over nodes in tree . More...

BinaryTreeTraversal< T >.Levelorder	levelorder ()
	Get level-order iterator over nodes in tree . More...

String	toString ()
	Get string presentation of node data. More...

GraphvizDecorator	getDecorator ()
	get decoration or `null` More...

String	toDot ()
	Get dot representation. More...

String	toText ()
	get multiline text visualization More...

String	toTikZ ()
	get TikZ code for LaTeX export More...

String	dotLabel ()

String	textLabel ()
	Get string representation of data in `toText`. More...

String	tikzNodeStyle ()

String	toTikZ (int level)

static void	main (String[] args)

Detailed Description

Simple binary tree.

The BinaryTree class represents a node and simultaneously its subtree. We do not explclitly distinguish between nodes and a (rooted) tree.

Used for demos (e.g., aud.example.BinaryTreeTraversal) and as base class for various binary trees.

For every node, we store an uplink to its parent, see getParent.

See also: aud.BinaryTreeTraversal BinaryTreeTraversal (iterators); aud.example.BinaryTreeTraversal example.BinaryTreeTraversal (recursive traversal demo)

Definition at line 25 of file BinaryTree.java.

Constructor & Destructor Documentation

◆ BinaryTree() [1/2]

aud.BinaryTree< T >.BinaryTree ( T data )

create new root node without children

Definition at line 34 of file BinaryTree.java.

                            {
    data_=data;
  }

◆ BinaryTree() [2/2]

aud.BinaryTree< T >.BinaryTree	(	T	data,
		BinaryTree< T >	left,
		BinaryTree< T >	right
	)

create new root node with children

Definition at line 41 of file BinaryTree.java.

                                            {
    this(data);
    left_=left; right_=right;
    if (left!=null)  left_.parent_ =this;
    if (right!=null) right_.parent_=this;
  }

Member Function Documentation

◆ dotLabel()

String aud.BinaryTree< T >.dotLabel ( )

protected

Definition at line 193 of file BinaryTree.java.

193{ return getData().toString(); }

aud.BinaryTree.getData

T getData()

get node data

Definition: BinaryTree.java:81

References aud.BinaryTree< T >.getData().

Here is the call graph for this function:

◆ getData()

T aud.BinaryTree< T >.getData ( )

get node data

Definition at line 81 of file BinaryTree.java.

81{ return data_; }

Referenced by aud.BinaryTree< T >.dotLabel(), aud.example.expr.Divide.getValue(), aud.example.expr.ExpressionTree.getValue(), aud.example.expr.Minus.getValue(), aud.example.expr.Plus.getValue(), aud.example.expr.Power.getValue(), aud.example.expr.Times.getValue(), aud.example.expr.UnaryMinus.getValue(), aud.example.expr.ExpressionTreeTraversal.output(), aud.BinaryTree< T >.textLabel(), aud.BinaryTree< T >.toString(), aud.BinaryTreeTraversal< T >.Traversal.toString(), aud.example.expr.ExpressionTree.toString(), and aud.BinaryTree< T >.toTikZ().

Here is the caller graph for this function:

◆ getDecorator()

GraphvizDecorator aud.BinaryTree< T >.getDecorator ( )

get decoration or null

Implements aud.util.GraphvizDecorable.

Reimplemented in aud.example.expr.ExpressionTree.

Definition at line 158 of file BinaryTree.java.

                                                    {
    return null;
  }

Referenced by aud.BinaryTree< T >.toDot().

Here is the caller graph for this function:

◆ getLeft()

BinaryTree< T > aud.BinaryTree< T >.getLeft ( )

get left child or null

Definition at line 86 of file BinaryTree.java.

86{ return left_; }

Here is the caller graph for this function:

◆ getParent()

BinaryTree< T > aud.BinaryTree< T >.getParent ( )

get node's parent or null for root

Definition at line 84 of file BinaryTree.java.

84{ return parent_; }

Referenced by aud.BinaryTree< T >.getRoot(), aud.BinaryTree< T >.isRoot(), and aud.test.BinaryTreeTest.testBinaryTree().

Here is the caller graph for this function:

◆ getRight()

BinaryTree< T > aud.BinaryTree< T >.getRight ( )

get right child or null)

Definition at line 88 of file BinaryTree.java.

88{ return right_; }

Here is the caller graph for this function:

◆ getRoot()

BinaryTree< T > aud.BinaryTree< T >.getRoot ( )

traverse upwards to find root node

Definition at line 103 of file BinaryTree.java.

                                 {
    BinaryTree<T> node=this;
    while (!node.isRoot())
      node=node.getParent();
    return node;
  }

References aud.BinaryTree< T >.getParent(), and aud.BinaryTree< T >.isRoot().

Referenced by aud.test.BinaryTreeTest.testBinaryTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ inorder()

BinaryTreeTraversal< T >.Inorder aud.BinaryTree< T >.inorder ( )

Get inorder iterator over nodes in tree .

Returns: instance of Iterable

See also: preorder; BinaryTreeTraversal.InorderIterator

Definition at line 126 of file BinaryTree.java.

                                                  {
    return new BinaryTreeTraversal<T>().inorder(this);
  }

References aud.BinaryTreeTraversal< T >.inorder().

Referenced by aud.BinaryTree< T >.main(), and aud.test.BinaryTreeTest.testBinaryTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isLeaf()

boolean aud.BinaryTree< T >.isLeaf ( )

Is this a leaf?

Definition at line 96 of file BinaryTree.java.

                          {
    return getLeft()==null && getRight()==null;
  }

References aud.BinaryTree< T >.getLeft(), and aud.BinaryTree< T >.getRight().

Referenced by aud.example.expr.AtomicExpression.isTerminal(), aud.test.BinaryTreeTest.testBinaryTree(), and aud.example.expr.ExpressionTree.toString().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isRoot()

boolean aud.BinaryTree< T >.isRoot ( )

Iscode this} root?

Definition at line 92 of file BinaryTree.java.

92{ return getParent()==null; }

aud.BinaryTree.getParent

BinaryTree< T > getParent()

get node's parent or null for root

Definition: BinaryTree.java:84

References aud.BinaryTree< T >.getParent().

Referenced by aud.BinaryTree< T >.getRoot(), aud.test.BinaryTreeTest.testBinaryTree(), and aud.example.expr.ExpressionTree.toString().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ levelorder()

BinaryTreeTraversal< T >.Levelorder aud.BinaryTree< T >.levelorder ( )

Get level-order iterator over nodes in tree .

Returns: instance of Iterable

See also: preorder; BinaryTreeTraversal.LevelorderIterator

Definition at line 142 of file BinaryTree.java.

                                                        {
    return new BinaryTreeTraversal<T>().levelorder(this);
  }

References aud.BinaryTreeTraversal< T >.levelorder().

Referenced by aud.BinaryTree< T >.main(), and aud.test.BinaryTreeTest.testBinaryTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ main()

static void aud.BinaryTree< T >.main ( String[] args )

static

Reimplemented in aud.example.expr.ExpressionTree.

Definition at line 281 of file BinaryTree.java.

                                         {
    BinaryTree<String> a=new BinaryTree<String>("A");
    BinaryTree<String> b=new BinaryTree<String>("B");
    BinaryTree<String> c=new BinaryTree<String>("C");
    BinaryTree<String> d=new BinaryTree<String>("D");
 
    a.setLeft(b);
    a.setRight(c);
    c.setLeft(d);
 
    System.out.println(a);
    System.out.println(a.toText());
    System.out.println(a.toTikZ());
 
    System.out.println("preorder: "+a.preorder().toString());
    System.out.println("inorder: "+a.inorder().toString());
    System.out.println("postorder: "+a.postorder().toString());
    System.out.println("level-order: "+a.levelorder().toString());
 
    //System.out.println(a.toDot());
  }

References aud.BinaryTree< T >.inorder(), aud.BinaryTree< T >.levelorder(), aud.BinaryTree< T >.postorder(), aud.BinaryTree< T >.preorder(), aud.BinaryTree< T >.setLeft(), aud.BinaryTree< T >.setRight(), aud.BinaryTreeTraversal< T >.Traversal.toString(), aud.BinaryTree< T >.toText(), and aud.BinaryTree< T >.toTikZ().

Here is the call graph for this function:

◆ postorder()

BinaryTreeTraversal< T >.Postorder aud.BinaryTree< T >.postorder ( )

Get postorder iterator over nodes in tree .

Returns: instance of Iterable

See also: preorder; BinaryTreeTraversal.PostorderIterator

Definition at line 134 of file BinaryTree.java.

                                                      {
    return new BinaryTreeTraversal<T>().postorder(this);
  }

References aud.BinaryTreeTraversal< T >.postorder().

Referenced by aud.BinaryTree< T >.main(), aud.example.expr.ExpressionParser.main(), aud.example.expr.ExpressionParser2.main(), aud.example.expr.ExpressionTree.main(), and aud.test.BinaryTreeTest.testBinaryTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ preorder()

BinaryTreeTraversal< T >.Preorder aud.BinaryTree< T >.preorder ( )

Get preorder iterator over nodes in tree .

Examples:

Iterator<BinaryTree<T> > ii=tree.preorder().iterator();

for (BinaryTree<T> node : tree.preorder()) { ... }

Returns: instance of Iterable

See also: BinaryTreeTraversal.PreorderIterator

Definition at line 118 of file BinaryTree.java.

                                                    {
    return new BinaryTreeTraversal<T>().preorder(this);
  }

References aud.BinaryTreeTraversal< T >.preorder().

Referenced by aud.BinaryTree< T >.main(), and aud.test.BinaryTreeTest.testBinaryTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setData()

void aud.BinaryTree< T >.setData ( T data )

set node data

Definition at line 79 of file BinaryTree.java.

79{ data_=data; }

◆ setLeft()

BinaryTree< T > aud.BinaryTree< T >.setLeft ( BinaryTree< T > tree )

set left subtree

Returns: previous subtree or null

Definition at line 55 of file BinaryTree.java.

                                {
    BinaryTree<T> old=left_;
    left_=tree;
    if (tree!=null)
      tree.parent_=this;
    if (old!=null)
      old.parent_=null;
    return old;
  }

Referenced by aud.BinaryTree< T >.main(), and aud.test.BinaryTreeTest.testBinaryTree().

Here is the caller graph for this function:

◆ setRight()

BinaryTree< T > aud.BinaryTree< T >.setRight ( BinaryTree< T > tree )

set right subtree

Returns: previous subtree or null

Definition at line 68 of file BinaryTree.java.

                                                    {
    BinaryTree<T> old=right_;
    right_=tree;
    if (tree!=null)
      tree.parent_=this;
    if (old!=null)
      old.parent_=null;
    return old;
  }

Referenced by aud.BinaryTree< T >.main(), and aud.test.BinaryTreeTest.testBinaryTree().

Here is the caller graph for this function:

◆ textLabel()

String aud.BinaryTree< T >.textLabel ( )

protected

Get string representation of data in toText.

Returns: getData().toString() (default implementation)

Definition at line 263 of file BinaryTree.java.

263{ return getData().toString(); }

References aud.BinaryTree< T >.getData().

Here is the call graph for this function:

◆ tikzNodeStyle()

String aud.BinaryTree< T >.tikzNodeStyle ( )

protected

Definition at line 269 of file BinaryTree.java.

269{ return ""; }

Referenced by aud.BinaryTree< T >.toTikZ().

Here is the caller graph for this function:

◆ toDot()

String aud.BinaryTree< T >.toDot ( )

Get dot representation.

Implements aud.util.Graphvizable.

Definition at line 162 of file BinaryTree.java.

                                  {
    String dot="graph BinaryTree {\n";
 
    GraphvizDecorator decorator=getDecorator();
    if (decorator!=null) {
      String d=decorator.getGlobalStyle();
      if (d!=null) dot+=" "+d+";\n";
      d=decorator.getGraphDecoration(this);
      if (d!=null) dot+=" graph ["+d+"];\n";
    }
 
    dot+=treeToDot();
 
    dot+="\n}\n";
    //System.out.println(dot);
    return dot;
  }

References aud.BinaryTree< T >.getDecorator(), aud.util.GraphvizDecorator.getGlobalStyle(), and aud.util.GraphvizDecorator.getGraphDecoration().

Here is the call graph for this function:

◆ toString()

String aud.BinaryTree< T >.toString ( )

Get string presentation of node data.

This method only encodes the node's content as string, it does not encode the entire tree! (This makes it easier to, e.g., print out a Stack of nodes.)

Returns: getData.toString

See also: BinaryTreeTraversal.Traversal::toString

Reimplemented in aud.example.expr.ExpressionTree.

Definition at line 154 of file BinaryTree.java.

                                     {
    return getData()!=null ? getData().toString() : "null";
  }

References aud.BinaryTree< T >.getData().

Here is the call graph for this function:

◆ toText()

String aud.BinaryTree< T >.toText ( )

get multiline text visualization

Definition at line 235 of file BinaryTree.java.

                         {
    return toText(0);
  }

References aud.BinaryTree< T >.toText().

Referenced by aud.BinaryTree< T >.main(), and aud.BinaryTree< T >.toText().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toTikZ() [1/2]

String aud.BinaryTree< T >.toTikZ ( )

get TikZ code for LaTeX export

Definition at line 266 of file BinaryTree.java.

                         {
    return "\\"+toTikZ(0)+";\n";
  }

References aud.BinaryTree< T >.toTikZ().

Referenced by aud.BinaryTree< T >.main(), aud.example.expr.ExpressionParser.main(), aud.example.expr.ExpressionParser2.main(), and aud.BinaryTree< T >.toTikZ().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toTikZ() [2/2]

String aud.BinaryTree< T >.toTikZ ( int level )

protected

Definition at line 270 of file BinaryTree.java.

                                     {
    String spaces=Sys.indent(level);
    String tex=spaces+"node "+tikzNodeStyle()+" {"+getData().toString()+"}\n";
    if (getLeft()!=null)
      tex+=spaces+" child[left] {\n"+getLeft().toTikZ(level+1)+spaces+" }\n";
    if (getRight()!=null)
      tex+=spaces+" child[right] {\n"+getRight().toTikZ(level+1)+spaces+" }\n";
 
    return tex;
  }

References aud.BinaryTree< T >.getData(), aud.BinaryTree< T >.getLeft(), aud.BinaryTree< T >.getRight(), aud.util.Sys.indent(), and aud.BinaryTree< T >.tikzNodeStyle().

Here is the call graph for this function:

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

BinaryTree.java

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ BinaryTree() [1/2]

◆ BinaryTree() [2/2]

Member Function Documentation

◆ dotLabel()

◆ getData()

◆ getDecorator()

◆ getLeft()

◆ getParent()

◆ getRight()

◆ getRoot()

◆ inorder()

◆ isLeaf()

◆ isRoot()

◆ levelorder()

◆ main()

◆ postorder()

◆ preorder()

◆ setData()

◆ setLeft()

◆ setRight()

◆ textLabel()

◆ tikzNodeStyle()

◆ toDot()

◆ toString()

◆ toText()

◆ toTikZ() [1/2]

◆ toTikZ() [2/2]