I want to test my ternary tree class, but I don't know why it always throw the emptyTreeException, can anyone help me to find out why? And here are my codes:
public class TernaryTree<T> implements TernaryTreeInterface<T>{
private TernaryNode<T> root;
public TernaryTree(){
root = null;
}
public TernaryTree(T rootData){
root = new TernaryNode<>(rootData);
}
public TernaryTree(T rootData, TernaryTree<T> leftTree, TernaryTree<T> middleTree, TernaryTree<T> rightTree){
privateSetTree(rootData, leftTree, middleTree, rightTree);
}
public void setTree(T rootData){
root = new TernaryNode<>(rootData);
}
public void setTree(T rootData, TernaryTreeInterface<T> leftTree, TernaryTreeInterface<T> middleTree,
TernaryTreeInterface<T> rightTree){
privateSetTree(rootData, (TernaryTree<T>)leftTree, (TernaryTree<T>)middleTree,
(TernaryTree<T>)rightTree);
}
private void privateSetTree(T rootData, TernaryTree<T> leftTree, TernaryTree<T> middleTree,
TernaryTree<T> rightTree){
root = new TernaryNode<>(rootData);
if((leftTree != null) && !leftTree.isEmpty()){
root.setLeftChild(leftTree.root);
}
if((middleTree != null) && !middleTree.isEmpty()){
if(middleTree != leftTree && middleTree != rightTree){
root.setMiddleChild(middleTree.root);
}
else if(middleTree == leftTree && middleTree == rightTree){
root.setMiddleChild(middleTree.root.copy());
}
}
if ((rightTree != null) && !rightTree.isEmpty()){
if(rightTree != leftTree && rightTree != middleTree){
root.setRightChild(rightTree.root);
}
else if(rightTree == leftTree && rightTree == middleTree){
root.setRightChild(rightTree.root.copy());
}
}
if ((leftTree != null) && (leftTree != this)) {
leftTree.clear();
}
if ((middleTree != null) && (middleTree != this)){
middleTree.clear();
}
if ((rightTree != null) && (rightTree != this)) {
rightTree.clear();
}
}
public T getRootData(){
if(isEmpty()){
throw new EmptyTreeException();
} else{
return root.getData();
}
}
public boolean isEmpty(){
return root == null;
}
public void clear(){
root = null;
}
protected void setRootData(T rootData) {
root.setData(rootData);
}
protected void setRootNode(TernaryNode<T> rootNode) {
root = rootNode;
}
protected TernaryNode<T> getRootNode() {
return root;
}
public int getHeight(){
int height = 0;
if(!isEmpty()){
height = root.getHeight();
}
return height;
}
public int getNumberOfNodes(){
int numberOfNodes = 0;
if(!isEmpty()){
numberOfNodes = root.getNumberOfNodes();
}
return numberOfNodes;
}
public Iterator<T> getPreorderIterator() {
return new PreorderIterator();
}
public Iterator<T> getInorderIterator() {
throw new UnsupportedOperationException();
}
public Iterator<T> getPostorderIterator() {
return new PostorderIterator();
}
public Iterator<T> getLevelOrderIterator() {
return new LevelOrderIterator();
}
private class PreorderIterator implements Iterator<T> {
private StackInterface<TernaryNode<T>> nodeStack;
public PreorderIterator(){
nodeStack = new LinkedStack<>();
if (root != null){
nodeStack.push(root);
}
}
public boolean hasNext(){
return !nodeStack.isEmpty();
}
public T next(){
TernaryNode<T> nextNode;
if(hasNext()){
nextNode = nodeStack.pop();
TernaryNode<T> leftChild = nextNode.getLeftChild();
TernaryNode<T> middleChild = nextNode.getMiddleChild();
TernaryNode<T> rightChild = nextNode.getRightChild();
if(rightChild != null){
nodeStack.push(rightChild);
}
if(middleChild != null){
nodeStack.push(middleChild);
}
if (leftChild != null){
nodeStack.push(leftChild);
}
}else{
throw new NoSuchElementException();
}
return nextNode.getData();
}
public void remove() {
throw new UnsupportedOperationException();
}
}
private class PostorderIterator implements Iterator<T> {
private StackInterface<TernaryNode<T>> nodeStack;
private TernaryNode<T> currentNode;
public PostorderIterator(){
nodeStack = new LinkedStack<>();
currentNode = root;
}
public boolean hasNext(){
return !nodeStack.isEmpty() || (currentNode != null);
}
public T next(){
boolean foundNext = false;
TernaryNode<T> leftChild, rightChild, nextNode = null;
TernaryNode<T> middleChild = null;
while (currentNode != null){
nodeStack.push(currentNode);
leftChild = currentNode.getLeftChild();
if(leftChild == null && middleChild != null){
currentNode = currentNode.getMiddleChild();
}
else if(leftChild == null && middleChild == null){
currentNode = currentNode.getRightChild();
} else{
currentNode = leftChild;
}
}
if (!nodeStack.isEmpty()) {
nextNode = nodeStack.pop();
TernaryNode<T> parent = null;
if (!nodeStack.isEmpty()) {
parent = nodeStack.peek();
if (nextNode == parent.getLeftChild()) {
currentNode = parent.getMiddleChild();
}
else if (nextNode == parent.getMiddleChild()){
currentNode = parent.getRightChild();
}
else{
currentNode = null;
}
} else {
currentNode = null;
}
} else {
throw new NoSuchElementException();
}
return nextNode.getData();
}
public void remove() {
throw new UnsupportedOperationException();
}
}
private class LevelOrderIterator implements Iterator<T> {
private QueueInterface<TernaryNode<T>> nodeQueue;
public LevelOrderIterator() {
nodeQueue = new LinkedQueue<>();
if (root != null) {
nodeQueue.enqueue(root);
}
}
public boolean hasNext() {
return !nodeQueue.isEmpty();
}
public T next() {
TernaryNode<T> nextNode;
if (hasNext()) {
nextNode = nodeQueue.dequeue();
TernaryNode<T> leftChild = nextNode.getLeftChild();
TernaryNode<T> middleChild = nextNode.getMiddleChild();
TernaryNode<T> rightChild = nextNode.getRightChild();
// Add to queue in order of recursive calls
if (leftChild != null) {
nodeQueue.enqueue(leftChild);
}
if (middleChild != null){
nodeQueue.enqueue(middleChild);
}
if (rightChild != null) {
nodeQueue.enqueue(rightChild);
}
} else {
throw new NoSuchElementException();
}
return nextNode.getData();
}
public void remove() {
throw new UnsupportedOperationException();
}
}
}
class TernaryNode<T>{
private T data;
private TernaryNode<T> leftChild;
private TernaryNode<T> middleChild;
private TernaryNode<T> rightChild;
public TernaryNode(){
this(null);
}
public TernaryNode(T dataPortion){
this(dataPortion, null, null, null);
}
public TernaryNode(T dataPortion, TernaryNode<T> newLeftChild, TernaryNode<T> newMiddleChild,
TernaryNode<T> newRightChild){
data = dataPortion;
leftChild = newLeftChild;
middleChild = newMiddleChild;
rightChild = newRightChild;
}
public T getData(){
return data;
}
public void setData(T newData){
data = newData;
}
public TernaryNode<T> getLeftChild(){
return leftChild;
}
public void setLeftChild(TernaryNode<T> newLeftChild){
leftChild = newLeftChild;
}
public boolean hasLeftChild() {
return leftChild != null;
}
public TernaryNode<T> getRightChild() {
return rightChild;
}
public void setRightChild(TernaryNode<T> newRightChild) {
rightChild = newRightChild;
}
public boolean hasRightChild() {
return rightChild != null;
}
public TernaryNode<T> getMiddleChild(){
return middleChild;
}
public void setMiddleChild(TernaryNode<T> newMiddleChild){
middleChild = newMiddleChild;
}
public boolean hasMiddleChild(){
return middleChild != null;
}
public boolean isLeaf() {
return (leftChild == null) && (rightChild == null) && (middleChild == null);
}
public int getNumberOfNodes() {
int leftNumber = 0;
int rightNumber = 0;
int middleNumber = 0;
if (leftChild != null) {
leftNumber = leftChild.getNumberOfNodes();
}
if (rightChild != null) {
rightNumber = rightChild.getNumberOfNodes();
}
if (middleChild != null){
middleNumber = middleChild.getNumberOfNodes();
}
return 1 + leftNumber + rightNumber + middleNumber;
}
/** Computes the height of the subtree rooted at this node.
* @return The height of the subtree rooted at this node. */
public int getHeight() {
return getHeight(this); // Call private getHeight
}
private int getHeight(TernaryNode<T> node) {
int height = 0;
if (node != null)
height = 1 + Math.max(Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild())),getHeight(node.getMiddleChild()));
return height;
}
/** Copies the subtree rooted at this node.
* @return The root of a copy of the subtree rooted at this node. */
public TernaryNode<T> copy() {
TernaryNode<T> newRoot = new TernaryNode<>(data);
if (leftChild != null) {
newRoot.setLeftChild(leftChild.copy());
}
if (rightChild != null) {
newRoot.setRightChild(rightChild.copy());
}
if (middleChild != null){
newRoot.setMiddleChild(middleChild.copy());
}
return newRoot;
}
}
And here is my test method:
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
TernaryTree<String> aTree = new TernaryTree<>("A");
TernaryTree<String> cTree = new TernaryTree<>("C");
TernaryTree<String> eTree = new TernaryTree<>("E");
TernaryTree<String> gTree = new TernaryTree<>("G");
TernaryTree<String> bTree = new TernaryTree<>("B",aTree,cTree,eTree);
TernaryTree<String> fTree = new TernaryTree<>("F",eTree,gTree,bTree);
TernaryTree<String> dTree = new TernaryTree<>("D",bTree,fTree,gTree);
System.out.println("root: " + bTree.getRootData());
System.out.println("height: " + bTree.getHeight());
System.out.println("total number of nodes: " + cTree.getNumberOfNodes());
aTree.getLevelOrderIterator();
aTree.getPreorderIterator();
aTree.getPostorderIterator();
//aTree.getInorderIterator();
}
}
So, I expect to test my post, pre, and levelorder iterator, and getRootData, getHeight, getNumberOfNodes. Somehow I encountered the emptyTreeException on the testing for getRootData, while I expect to return the root "B" for bTree. Can anyone help me? Thanks
Aucun commentaire:
Enregistrer un commentaire