二分探索木

Question

こんにちは 私は{23,16,45,26,2,5,9} のようにそれにいくつかの数字を持つ配列のリストを持っていると私は、この配列リストとバイナリ検索ツリーを作りたい"array"とその要素が持つオブジェクトである2フィールド、1)digit2)levelけどここで私はちょうどそのdigitフィールドを使用したい。dListはDoublyLinkedListです。 これは私のコードですが、例外が発生しました。

private void method(ArrayList<Element> array) { 
    DNode header = new DNode(null, null, null); 
    DNode trailer = new DNode(null, header, null); 
    header.next = trailer; 
    DNode node = new DNode(array.get(0), header, trailer); 
    dList.addLast(node); 
    header = node 
    for(int i = 1;i<array.size();i++){ 
    makeBST(node, array.get(i)); 
    } 
} 

private void makeBST(DNode node, Element e) { 

    if (!e.equals(node.getElement())) { 
     DNode nodeOne = new DNode(e, null, null); 
     if (node.getElement().getDigit() > e.getDigit()) { 
      node.prev = nodeOne; 
     } else if (node.getElement().getDigit() < e.getDigit()) { 
      node.next = node; 
     } 
    } 
    if (e.getDigit() < node.getElement().getDigit()) { 
     makeBST(node.prev, e); 
    } 
    makeBST(node.next, e); 
} 

例外：

Exception in thread "main" java.lang.StackOverflowError 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:43) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54) 

例外の最初の行のコード行のためである：

if (!e.equals(node.getElement())) 

Answer 1

あなたの再帰的な方法 "プライベート無効makeBST（DNodeノード、要素E）"何らかのタイプの終了条件（それ自身を呼び出すのを妨げる流路）が必要です。スタックオーバーフローエラーの原因となっている再帰的な呼び出しを続けます。

Answer 2

あなたはStackOverflowErrorを持っています。これは無限の（おそらく少なくとも潜在的に）再帰エラーを指しています。

p.s.なぜTreeMap<K,V>を使用しないのですか？ここで、Kはデータのインデックス、Vはデータ値です。

Answer 3

あなたのコードは基本的である：

private void makeBST(DNode node, Element e) { 
    // ... (the rest of your code) 
    makeBST(node.next, e); 
} 

それはほぼ同等です：あなたは無限ループ（ただししばらくして、しかし、再帰で）を作っ

private void makeBST(DNode node, Element e) { 
    while(true) { 
     // ... (the rest of your code) 
     node = node.next; 
    } 
} 

。スタックのサイズは非常に限られているため、いくつかの反復の後にStackOverflowErrorを取得します。

とにかく、単なる教育実験の場合は問題ありません。正常に動作するBSTが必要な場合は、java.util.TreeSetまたはjava.util.TreeMapを使用します。

Answer 4

私はあなたが試しているのを見ることができますが、あなたは解決策から遠いです。

再帰を使用しているため、停止しているケースが必要です。これは持っていません。

あなたはまた、おそらく持っている必要がある場合は...他にあれば...むしろあなたが持っているものよりも（もし... ...あれば）...

if (!e.equals(node.getElement())) { は、どちらかの意味がないことライン

バイナリツリーやバイナリ検索ツリーに関するウィキペディアの記事を参照してください...おそらく役立つでしょう。