如何实例化《Open Data Structures》中复杂的泛型BinaryTree类？

这段代码用了递归泛型（F-bounded泛型），核心是让节点类能在父树类中正确引用自身类型，避免不必要的强制转换。要实例化这个BinaryTree，你得按以下步骤来：

第一步：定义自定义节点类 #

首先需要创建一个继承自BinaryTree.BTNode的子类，泛型参数填自身类型，这样才能满足BinaryTree对泛型参数的要求：

class MyNode extends BinaryTree.BTNode<MyNode> {
    // 可以添加自定义数据字段，比如存储节点值
    public int data;
}

第二步：实例化BinaryTree类 #

有两种构造方式可选：

方式一：带nil节点的构造

nil是用来标记空节点的特殊实例，用这种方式初始化后，newNode()方法会自动把新节点的parent、left、right指向这个nil节点：

// 创建nil节点（空节点标记）
MyNode nil = new MyNode();
// 创建示例节点（用于反射生成新节点的模板）
MyNode sample = new MyNode();
// 实例化二叉树
BinaryTree<MyNode> tree = new BinaryTree<>(sample, nil);

方式二：不带nil节点的构造

这种方式下nil初始为null，后续需要手动设置，否则调用newNode()时可能出现空指针：

MyNode sample = new MyNode();
BinaryTree<MyNode> tree = new BinaryTree<>(sample);
// 手动初始化nil节点
tree.nil = new MyNode();

补充说明 #

• sampleNode的作用是给newNode()方法提供反射模板，通过它的getClass().newInstance()来创建新的节点实例。
• 递归泛型Node extends BinaryTree.BTNode<Node>保证了BTNode中的left、right、parent字段类型都是你自定义的节点类，不用在代码里做强制类型转换。

内容的提问来源于stack exchange，提问作者ll cool