com.pow2.structures.tree
Class BinaryTree

java.lang.Object
  com.pow2.structures.tree.BinaryTree

Direct Known Subclasses:

BinarySearchTree, ItemTree

public abstract class BinaryTree

extends Object

Binary tree abstract class.
Extend this class and implement the build method.

Author:

particle (www.theparticle.com), Luca Fossato

Field Summary

protected org.apache.log4j.Category	cat Log4j category
static int	INTRAVERSE use this value to specify the in-traverse algorithm
protected NodeVisitorInterface	nodeVisitor the nodeVisitor reference
static int	POSTRAVERSE use this value to specify the post-traverse algorithm
static int	PRETRAVERSE use this value to specify the pre-traverse algorithm
protected Node	root The root node of the tree
protected int	traverseMode Specify the tree traverse mode.

Constructor Summary

BinaryTree()
Default constructor for the BinaryTree object.

BinaryTree(Object o)
Constructor for BinaryTree object.

Method Summary

boolean	addLeft(Node p, Node c) Add a new left node to the parent node left node list.
boolean	addRight(Node p, Node c) Add a new right node to the parent node right node list.
abstract void	build() Build the tree.
Object	getData() Gets the data object of the tree root node
Node	getLeft() Gets the left node of the root node
NodeVisitorInterface	getNodeVisitor() Gets the nodeVisitor attribute of the BinaryTree object
Node	getRight() Gets the right node of the root node
Node	getRoot() Get the root node of the BinaryTree object
int	getTraverseMode() Get the traverse mode attribute of the BinaryTree object.
boolean	insertLeft(Node p, Node c) Insert a new left node into the tree.
boolean	insertRight(Node p, Node c) Insert a new right node into the tree.
protected void	intrav(Node p) Traverse the tree, using in-order algorithm, starting from the input node.
boolean	isEmpty() Test if the Binary Tree is empty.
void	move(Node p, Node c, boolean isLeft) Move the input c node over the new parent p node.
protected void	postrav(Node p) Traverse the tree, using post-order algorithm, starting from the input node.
protected void	pretrav(Node p) Traverse the tree, using pre-order algorithm, starting from the input node.
protected void	remove(Node n) Remove the input node from the tree, rearranging the parent and the child nodes references.
void	remove(Node n, boolean recursive) Remove the input node from the tree.
void	setData(Object o) Sets the data object of the tree root node.
void	setNodeVisitor(NodeVisitorInterface nodeVisitor) Sets the nodeVisitor attribute of the BinaryTree object
void	setRoot(Node r) Set the root node of the BinaryTree object
void	setTraverseMode(int traverseMode) Set the traverseMode attribute of the BinaryTree object.
void	traverse() Traverse the tree, using the traverse algorithm specified using setTraverseMode.
void	visit(Node n) Visit the content of the input node.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

PRETRAVERSE

public static final int PRETRAVERSE

use this value to specify the pre-traverse algorithm

See Also:

Constant Field Values

INTRAVERSE

public static final int INTRAVERSE

use this value to specify the in-traverse algorithm

See Also:

Constant Field Values

POSTRAVERSE

public static final int POSTRAVERSE

use this value to specify the post-traverse algorithm

See Also:

Constant Field Values

cat

protected org.apache.log4j.Category cat

Log4j category

root

protected Node root

The root node of the tree

traverseMode

protected int traverseMode

Specify the tree traverse mode.
It can have one of the following values:

• BynaryTree.PRETRAVERSE - use the pre-traverse algorithm
• BynaryTree.INTRAVERSE - use the in-traverse algorithm
• BynaryTree.POSTRAVERSE - use the post-traverse algorithm

nodeVisitor

protected NodeVisitorInterface nodeVisitor

the nodeVisitor reference

Constructor Detail

BinaryTree

public BinaryTree()

Default constructor for the BinaryTree object.
Set the traverse mode to PRETRAVERSE.

BinaryTree

public BinaryTree(Object o)

Constructor for BinaryTree object.
Set the input object as the data object related to the root node of the tree.

Parameters:

o - the data object to relate to the tree root node

Method Detail

build

public abstract void build()

Build the tree.

setData

public void setData(Object o)

Sets the data object of the tree root node.
If the tree root node is null, instance a new root node and set its data property.

Parameters:

o - The new root node data object

setNodeVisitor

public void setNodeVisitor(NodeVisitorInterface nodeVisitor)

Sets the nodeVisitor attribute of the BinaryTree object

Parameters:

nodeVisitor - The new nodeVisitor value

setRoot

public void setRoot(Node r)

Set the root node of the BinaryTree object

Parameters:

r - The new root value

setTraverseMode

public void setTraverseMode(int traverseMode)

Set the traverseMode attribute of the BinaryTree object. traverseMode can have one of the following values:

• BynaryTree.PRETRAVERSE to use the pre-traverse algorithm
• BynaryTree.INTRAVERSE to use the in-traverse algorithm
• BynaryTree.POSTRAVERSE to use the post-traverse algorithm

Parameters:

traverseMode - the traversing mode.

isEmpty

public boolean isEmpty()

Test if the Binary Tree is empty.
A binary tree is empty if the root element of the tree is null.

Returns:

true if the the root element of the tree is null; false otherwise.

getData

public Object getData()

Gets the data object of the tree root node

Returns:

The data object of the tree root node, or null if the root node is null

getNodeVisitor

public NodeVisitorInterface getNodeVisitor()

Gets the nodeVisitor attribute of the BinaryTree object

Returns:

The nodeVisitor value

getLeft

public Node getLeft()

Gets the left node of the root node

Returns:

The left node of the root node, or null if the root node is null

getRoot

public Node getRoot()

Get the root node of the BinaryTree object

Returns:

The root value

getRight

public Node getRight()

Gets the right node of the root node

Returns:

The right node of the root node, or null if the root node is empty

getTraverseMode

public int getTraverseMode()

Get the traverse mode attribute of the BinaryTree object.

Returns:

the traverse mode attribute of the BinaryTree object

insertLeft

public boolean insertLeft(Node p,
                          Node c)

Insert a new left node into the tree.

Parameters:

p - the parent node where to insert the new left node

c - the new left node to add to the parent node

Returns:

true if the insertion is successfull; false otherwise

insertRight

public boolean insertRight(Node p,
                           Node c)

Insert a new right node into the tree.

Parameters:

p - the parent node where to insert the new right node

c - the new right node to add to the parent node

Returns:

true if the insertion is successfull; false otherwise

addLeft

public boolean addLeft(Node p,
                       Node c)

Add a new left node to the parent node left node list.

Parameters:

p - the parent node

c - the left node to add to the parent node left node list

Returns:

true if the addition is successfull; false otherwise

addRight

public boolean addRight(Node p,
                        Node c)

Add a new right node to the parent node right node list.

Parameters:

p - the parent node

c - the node to add to the the parent node right node list

Returns:

true if the addition is successfull; false otherwise

move

public void move(Node p,
                 Node c,
                 boolean isLeft)

Move the input c node over the new parent p node.

Parameters:

p - the new parent node for c node

c - the node to move

isLeft - true if c must be inserted as a left node of p; false if c must be inserted as right node of p

remove

public void remove(Node n,
                   boolean recursive)

Remove the input node from the tree.

Parameters:

n - the node to remove

recursive - true to remove all the input node children; false otherwise

remove

protected void remove(Node n)

Remove the input node from the tree, rearranging the parent and the child nodes references.

Parameters:

n - the node to remove

traverse

public void traverse()
              throws Exception

Traverse the tree, using the traverse algorithm specified using setTraverseMode.

Throws:

Exception - if any error occurs

pretrav

protected void pretrav(Node p)
                throws Exception

Traverse the tree, using pre-order algorithm, starting from the input node.
pre-order traversal: first looks at the data (of the current node), then the left nodes, and then the right nodes.

Parameters:

p - the node where to start the tree traversing

Throws:

Exception - if any error occurs

intrav

protected void intrav(Node p)
               throws Exception

Traverse the tree, using in-order algorithm, starting from the input node.
in-order traversal: first look at the right nodes, then the nodes data, and then the left nodes.

Parameters:

p - the node where to start the tree traversing.

Throws:

Exception - if any error occurs

postrav

protected void postrav(Node p)
                throws Exception

Traverse the tree, using post-order algorithm, starting from the input node.
post-order traversal: looks at the left child, then right child, and only then data.

Parameters:

p - the node where to start the tree traversing.

Throws:

Exception - if any error occurs

visit

public void visit(Node n)
           throws Exception

Visit the content of the input node.

Parameters:

n - the node to visit

Throws:

Exception - if any error occurs