Clever Geek Handbook

How can I avoid casting on an inherited recursive class using a template?

1) Suppose you have the following abstract class definition:

abstract class AbstractBinaryTree<T> {
    AbstractBinaryTree<T> parent;
    AbstractBinaryTree<T> leftChild;
    AbstractBinaryTree<T> rightChild;
    T value;     
}

and the implementation of this class with a new method that has not been previously declared or implemented:

public class BinarySearchTree<T extends Comparable<T>> extends AbstractBinaryTree<T> {
    public BinarySearchTree(T pVal) {
        super(pVal);
    }


    public Boolean isBST(){
    if(leftChild != null && rightChild != null){
        return (leftChild.value.compareTo(value) < 0 
                && rightChild.value.compareTo(value) >= 0 )
                && ((BinarySearchTree<T>) leftChild).isBST() 
                && ((BinarySearchTree<T>) rightChild).isBST();
    }
    else if(leftChild != null){
        return leftChild.value.compareTo(value) < 0 
                && ((BinarySearchTree<T>) leftChild).isBST() ;
    }
    else if (rightChild != null){
        return rightChild.value.compareTo(value) >= 0
        && ((BinarySearchTree<T>) rightChild).isBST();
    }
    else{
        return true;
    }
}

How do you avoid leaving all the left and right kids?

2) Likewise, suppose I had the following abstract definition in AbstractBinaryTree:

    public abstract AbstractBinaryTree<T> findMinTree();

and its implementation in BST:

/***
 * @return the subtree rooted at the min value
 */
public BinarySearchTree<T> findMinTree(){
    if(leftChild != null)
        return (BinarySearchTree<T>) leftChild.findMinTree();
    return this;
}

How to avoid broadcasting in

public BinarySearchTree<T> findMinTree(){
    if(leftChild != null)
        return (BinarySearchTree<T>) leftChild.findMinTree();
    return this;
}

or when will I name it on the baby?

BinarySearchTree<T> y = ((BinarySearchTree<T>) x.rightChild).findMinTree();

I am not allergic to casting, but in this case it is very difficult. Thanks in advance for your answers!

+3


source to share


2 answers


You can use even more generics, namely CRTP :



abstract class AbstractBinaryTree<T, TTree extends AbstractBinaryTree<T, TTree>> {
    TTree parent;
    TTree leftChild;
    TTree rightChild;
    T value;     
}
+4


source


Instead of a class having an abstract superclass referring to a reference to itself for the tree structure, I would use a class Node

that has references to its parent Node

, and to the left and right of the children Nodes

. The class AbstractBinaryTree

would have a reference to the root Node

.

abstract class AbstractBinaryTree<T> {
    Node<T> root;
    static class Node<E>
    {
        Node<E> parent;
        Node<E> leftChild;
        Node<E> rightChild;
        E value;
    }
}


Then the subclasses do not need a type Node

to change its own type; BinarySearchTree

would also use Node

s.

class BinarySearchTree<T extends Comparable<T>> extends AbstractBinaryTree<T>
{
    // No need to redefine the structure types here.
}
0


source






More articles:


All Articles