dimanche 30 juillet 2017

Test client for ternary tree

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