org.grinvin.engine.apengine

Class BinaryTree

Implemented Interfaces:
Cloneable
Known Direct Subclasses:
LabeledBinaryTree

public class BinaryTree
extends java.lang.Object
implements Cloneable

This class represents a binary tree. It is implemented as an array with pointers to the children.

Field Summary

protected int
binaryCount
protected int[]
contents
protected int
firstfreepos
protected int
unaryCount

Constructor Summary

BinaryTree(int unaryOperators, int binaryOperators)
Create a new binary tree with unaryOperators unary operators and binaryOperators binary operators.
BinaryTree(int[] newcontents, int firstfreeposition, int unaryCount, int binaryCount)
Create a new binary tree.

Method Summary

int
childCount(int parent)
Return the number of children for the given node.
int[]
children(int parent)
Return the children of the given node.
BinaryTree
clone()
int
extendOn(int depth, int pos)
Add a new node on depth depth and position pos.
int
getBinaryCount()
Return the current number of binary operators.
int
getNodeCount()
Return the current number of nodes, this equals: binaryCount * 2 + unaryCount + 1.
int
getUnaryCount()
Return the current number of unary operators.
boolean
hasLeftChild(int parent)
Does the node have a left child?
boolean
hasRightChild(int parent)
Does the node have a right child?
int
leftChild(int parent)
Return the left child of the given node.
int
newLeftChild(int parent)
Create a new left child for the given node.
int
newRightChild(int parent)
Create a new right child for the given node.
int
nodesonlevel(int depth)
Return the number of nodes on the given depth.
void
removeLeftChild(int parent)
Remove the left child of the given node.
void
removeOn(int depth, int pos, int parent)
Remove the node on the given depth and pos with the given parent.
void
removeRightChild(int parent)
Remove the right child of the given node.
int
rightChild(int parent)
Return the right child of the given node.
String
toString()
protected String
toString(int parent)

Field Details

binaryCount

protected int binaryCount

contents

protected int[] contents

firstfreepos

protected int firstfreepos

unaryCount

protected int unaryCount

Constructor Details

BinaryTree

public BinaryTree(int unaryOperators,
                  int binaryOperators)
Create a new binary tree with unaryOperators unary operators and binaryOperators binary operators.

BinaryTree

protected BinaryTree(int[] newcontents,
                     int firstfreeposition,
                     int unaryCount,
                     int binaryCount)

Method Details

childCount

public final int childCount(int parent)
Return the number of children for the given node.
Parameters:
parent - the parent to start counting
Returns:
the number of children for the given node

children

public final int[] children(int parent)
Return the children of the given node.
Parameters:
parent - the parent of the children
Returns:
an array of size <= 2 containing the left and the right child

clone

public BinaryTree clone()

extendOn

public final int extendOn(int depth,
                          int pos)
Add a new node on depth depth and position pos.
Parameters:
depth - the depth to add a new node
pos - the position to add a new node
Returns:
the parent of the new node, or -1 when no node could be added

getBinaryCount

public final int getBinaryCount()
Return the current number of binary operators.

getNodeCount

public final int getNodeCount()
Return the current number of nodes, this equals: binaryCount * 2 + unaryCount + 1.

getUnaryCount

public final int getUnaryCount()
Return the current number of unary operators.

hasLeftChild

public final boolean hasLeftChild(int parent)
Does the node have a left child?
Parameters:
parent - parent node nummber
Returns:
true when parent has a left child or false otherwise

hasRightChild

public final boolean hasRightChild(int parent)
Does the node have a right child?
Parameters:
parent - parent node nummber
Returns:
true when parent has a right child or false otherwise

leftChild

public final int leftChild(int parent)
Return the left child of the given node.
Parameters:
parent - the parent of the child
Returns:
the left child of the parent

newLeftChild

public final int newLeftChild(int parent)
Create a new left child for the given node.
Parameters:
parent - the node that will get a new left child
Returns:
the new child

newRightChild

public final int newRightChild(int parent)
Create a new right child for the given node.
Parameters:
parent - the node that will get a new right child
Returns:
the new child or -1 if there is no left child

nodesonlevel

public final int nodesonlevel(int depth)
Return the number of nodes on the given depth.
Parameters:
depth - the depth of the tree
Returns:
the number of nodes on the given depth

removeLeftChild

public final void removeLeftChild(int parent)
Remove the left child of the given node.
Parameters:
parent - the parent of which the left child should be removed

removeOn

public final void removeOn(int depth,
                           int pos,
                           int parent)
Remove the node on the given depth and pos with the given parent.

removeRightChild

public final void removeRightChild(int parent)
Remove the right child of the given node.
Parameters:
parent - the parent of which the right child should be removed

rightChild

public final int rightChild(int parent)
Return the right child of the given node.
Parameters:
parent - the parent of the child
Returns:
the right child of the parent

toString

public String toString()

toString

protected String toString(int parent)