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

}

CodePudding user response：

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;
    }
}

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);

CodePudding user response：

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
}