How can I instantiate this very sophisticated generic Class appears in book Open Data Structures?

user_19528473 0
Viewed 73

I am reading the book Open Data Structures by Pat Morin. The author use very sophisticated generic code in java to implement BinaryTree. The code really confuses me. I even can't figure out how to instantiate the BinaryTree Class, can anyone help? Thanks very much.

package ods;

import java.util.LinkedList;
import java.util.Queue;

/**
 * An implementation of binary trees
 * @author morin
 *
 * @param <Node>
 */
public class BinaryTree<Node extends BinaryTree.BTNode<Node>> {
    
    public static class BTNode<Node extends BTNode<Node>> {
        public Node left;
        public Node right;
        public Node parent; 
    }

    
    protected Node sampleNode;
    
    
    protected Node r;

    
    protected Node nil;

    
    public BinaryTree(Node sampleNode, Node nil) {
        this.sampleNode = sampleNode;
        this.nil = nil;
        r = nil;
    }

    
    public BinaryTree(Node sampleNode) {
        this.sampleNode = sampleNode;
    }
    
    
    @SuppressWarnings({"unchecked"})
    protected Node newNode() {
        try {
            Node u = (Node)sampleNode.getClass().newInstance();
            u.parent = u.left = u.right = nil;
            return u;
        } catch (Exception e) {
            return null;
        }
    }
//some method below

}
generics java
2 Answers

I think you have to define a class to represent a node type. It will hold what you want to put in the tree. For example :

public class StringNode extends BinaryTree.BTNode<StringNode> {
    private final String stringValue;

    public StringNode(String stringValue) {
        this.stringValue = stringValue;
    }

    public String getValue() {
        return stringValue;
    }
}

Then you can use it to instantiate a tree of that node type :

StringNode firstNode = new StringNode("firstValue");
BinaryTree<StringNode> stringTree = new BinaryTree<StringNode>(firstNode);

The Node type parameter is defined as a subclass of BTNode, so that one can implement recursive methods with it. For example, let's look at the size(Node) method :

int size(Node u) {
    if (u == nil) return 0;
    return 1 + size(u.left) + size(u.right);
}

It is not possible to write this without Node being a BTNode itself. Because if it is not, there is no such thing as u.left or u.right.

user_173350010

For the basic it should be looking like this and normaly it should be abstract and you should create extending classes of this tree. Keep clear that each tree also is a node (of some other tree). Remeber that this is only some base now you could implement more methods like getting some seeking node/load in the tree or get the highest or lowest load and so on.

/**
 * An implementation of binary trees
 *
 * @param <V> load type
 * @param <N> node type
 * @author morin
 */
public class BinaryTree<V, N extends BinaryTree<V, N>> {

    protected V load;


    protected N rightNode;


    protected N leftNode;


    public BinaryTree(V load, N rightNode, N leftNode) {
        this.load = load;
        this.rightNode = rightNode;
        this.leftNode = leftNode;
    }

    public BinaryTree(V load) {
        this(load, null, null);
    }

    public V getLoad() {
        return load;
    }

    public void setLoad(V load) {
        this.load = load;
    }

    public N getRightNode() {
        return rightNode;
    }

    public void setRightNode(N rightNode) {
        this.rightNode = rightNode;
    }

    public N getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(N leftNode) {
        this.leftNode = leftNode;
    }
    
    //some more methods
}
user_178428770
Related