inorderでバイナリ検索ツリーを通過するときの最初の要素を取得する方法は？</p> <pre><code>public Karte giveFirst(BinarySearchTree<Karte> t){ if(t.getLeftTree() != null) { return giveFirst(t.getLeftTree()); }else{ return t.getContent(); } } </code></pre> <p>完全なバイナリ検索ツリーコード：

Question

私の試みは（私にNullPointerExceptionが与えた）

package Model; 


    private class BSTNode<CT extends ComparableContent<CT>> { 

     private CT content; 
     private BinarySearchTree<CT> left, right; 

     public BSTNode(CT pContent) { 

      this.content = pContent; 
      left = new BinarySearchTree<CT>(); 
      right = new BinarySearchTree<CT>(); 
     } 

    } 

    private BSTNode<ContentType> node; 

    public BinarySearchTree() { 
     this.node = null; 
    } 

    public void insert(ContentType pContent) { 
     if (pContent != null) { 
      if (isEmpty()) { 
       this.node = new BSTNode<ContentType>(pContent); 
      } else if (pContent.isLess(this.node.content)) { 
       this.node.left.insert(pContent); 
      } else if(pContent.isGreater(this.node.content)) { 
       this.node.right.insert(pContent); 
      } 
     } 
    } 

    public BinarySearchTree<ContentType> getLeftTree() { 
     if (this.isEmpty()) { 
      return null; 
     } else { 
      return this.node.left; 
     } 
    } 

    public ContentType getContent() { 
     if (this.isEmpty()) { 
      return null; 
     } else { 
      return this.node.content; 
     } 
    } 

    public BinarySearchTree<ContentType> getRightTree() { 
     if (this.isEmpty()) { 
      return null; 
     } else { 
      return this.node.right; 
     } 
    } 

    public void remove(ContentType pContent) { 
     if (isEmpty()) { 
      return; 
     } 

     if (pContent.isLess(node.content)) { 
      node.left.remove(pContent); 
     } else if (pContent.isGreater(node.content)) { 
      node.right.remove(pContent); 
     } else { 
      if (node.left.isEmpty()) { 
       if (node.right.isEmpty()) { 
        node = null; 
       } else { 
        node = getNodeOfRightSuccessor(); 
       } 
      } else if (node.right.isEmpty()) { 
       node = getNodeOfLeftSuccessor(); 
      } else { 
       if (getNodeOfRightSuccessor().left.isEmpty()) { 
        node.content = getNodeOfRightSuccessor().content; 
        node.right = getNodeOfRightSuccessor().right; 
       } else { 
        BinarySearchTree<ContentType> previous = node.right 
          .ancestorOfSmallRight(); 
        BinarySearchTree<ContentType> smallest = previous.node.left; 
        this.node.content = smallest.node.content; 
        previous.remove(smallest.node.content); 
       } 
      } 
     } 
    } 

    public ContentType search(ContentType pContent) { 
     if (this.isEmpty() || pContent == null) { 
      return null; 
     } else { 
      ContentType content = this.getContent(); 
      if (pContent.isLess(content)) { 
       return this.getLeftTree().search(pContent); 
      } else if (pContent.isGreater(content)) { 
       return this.getRightTree().search(pContent); 
      } else if (pContent.isEqual(content)) { 
       return content; 
      } else { 
       return null; 
      } 
     } 
    } 
    private BinarySearchTree<ContentType> ancestorOfSmallRight() { 
     if (getNodeOfLeftSuccessor().left.isEmpty()) { 
      return this; 
     } else { 
      return node.left.ancestorOfSmallRight(); 
     } 
    } 

    private BSTNode<ContentType> getNodeOfLeftSuccessor() { 
     return node.left.node; 
    } 

    private BSTNode<ContentType> getNodeOfRightSuccessor() { 
     return node.right.node; 
    } 

} 

（「あなたのポストはほとんどのコードであるように見えます。いくつかの詳細を追加してください」を^^ ） 私はそれを動作させるために自分のコードを変更/書き換えできますか？ ご協力いただければ幸いです！

Answer 1

左端のリーフノードに到達したらどうなるか考えてください。

左のツリーはnullになります。つまり、whileループから抜け出すことになります。この後にnullを返すので、戻り値の状態にアクセスしようとすると例外がスローされます。それは、ツリー内の最小の要素も

Answer 2

になるように、それはもう左子供を持っていないときは、このノードを返す必要があります

あなたはBinarySearchTreeとBSTNodeを持っている理由、私は知りません。 BSTNodeはツリーを構築するのに十分なはずです。より良い理解のためにチュートリアル/レッスンをご覧ください。

inorderでバイナリ検索ツリーを通過するときの最初の要素を取得するにはどうすればよいですか？

もう少し左に出ないようにしておきましょう。ノードに左の子がある場合は、そのノードに移動してください。あなたが左の子を持たないノードに達するまでこれを続けます。あなたがそこにいるとき、あなたはあなたが木の最も左の部分にいることを知っています。次のコードスニペットは、BSTのrootが与えられた場合に、これを達成する方法のアイデアを示しています。

public BSTNode getSmallest(BSTNode root) { 
    if(root.left != null) 
     return getSmallest(root.left); 
    return root; 
}