从二叉树构建 BST 的最佳实践

Question

我在 Java 中创建了一个二叉搜索树，它是从一个已经实现的二叉树扩展而来的，但是当我尝试使用一些继承的方法时它不起作用。让我解释一下：

二叉树：

public class BinaryTree<T>{
     private Node<T> root;

     public class Node<T>{
          T value;
          Node left;
          Node right;

          public Node(T value){
               this.value = value;
               this.left = null;
               this.right = null;
          }
     }
     
     public BinaryTree(){
          ...
     }
     public void printInOrder(){
          ...
     }  
 }

BST:

public class BST extends BinaryTree<Integer>{
      private Node<Integer> root;

      public BST(Integer v){
          super(v);
      }

      public void insert(Integer element){
            insert(this.root, element);
      }

      private insert( Node node, Integer element){
            if(node == null)
               return;
        
            if(node.value > value) {
                  if(node.left != null) {
                       insert(node.left, value);
                  }
                  else {
                       node.left = new NodeBST(value);
                  }
             }else { // Node.value < element
                 if(node.right != null) {
                      insert(node.right, value);
                 }
                 else {
                      node.right = new NodeBST(value);
                 }
             }

         }

   }

应用程序：

public class App{

      public static void main(String[] args){
             BST bst = new BST(4);
             bst.insert(2);
             bst.insert(5);
             bst.insert(3);
             bst.insert(7);

             bst.printInOrder();  //Here I got the problem

     }
}

如果我尝试打印它，它只会打印根节点 (4)，其余节点将为空。当我查看内部情况时，发现有两个根：

BST.Node root，其中包含所有节点的正确顺序
BinaryTree.Node root，只包含root，其他所有节点都是null.

所以我猜它正确地创建了根，因为我在 BST 的构造函数中调用了超级 class，但是当我在 insert 方法[=50 中创建一个新节点时=]，它只将它附加到 BST.Node 根（而不是 BinaryTree.Node 根），因此当我调用 print 时，它是在 BinaryTree 中实现的，从BST 打印 null :/

所以我的问题是：

如何使用 BST 的 print 方法 来打印 BST.Node root 中的所有值？

什么阻止 BinaryTree.Node root 与 BST.Node root 相同？

这样做的最佳做法是什么？

Answer 1

不要在 BST 中再次声明 'root'，它会隐藏基数 class 中的 'root'。

要么在 BinaryTree 中使 'root' 受到保护，要么在那里提供必要的访问器，以便 subclasses 可以使用它。

从二叉树构建 BST 的最佳实践

Best practice to build a BST from a Binary Tree

java

inheritance

binary-search-tree

inner-classes