ツリー内の要素をJavaで上書きする

Question

ツリー内の要素を上書きする必要があります。クラスツリーには、キーと左と右があります。 BSTではないとしましょう。

ここまでは私のコードです。それは木の左半分ではうまくいくが、右半分ではうまくいかない。私はそれを動作させるためのほんの少しの変更だと思うが、何らかの助けがなければそれをやり遂げることはできない。

public T overwriteOne(TreeNode<T> tree, T element, T newElement) { 
    if (tree == null) 
     return null; 

    if (tree.key.equals(element)) { 
     tree.key = newElement; 
     return tree.key; 
    } 
    else if (tree.left != null) { 
     return overwriteOne(tree.left, element, newElement); 
    } 
    else if (tree.right != null){ 
     return overwriteOne (tree.right, element, newElement); 
    } 
    return null; 
} 

Answer 1

検索しているノードが正しい分岐にある場合、コードは機能しません。左のブランチがヌルでない場合は、左に再帰的にコールし、右は無視します。

通常、要素の検索を高速化するためにツリーを使用しています。現在のノードよりも小さい要素は左側に格納され、現在のノードよりも大きい要素は右側に格納されます。あなたはそれが再帰呼び出しの最初のテストだからtree.leftまたはtree.rightがnullかどうかをテストする必要はありません

public T overwriteOne(TreeNode<T> tree, T element, T newElement) { 
    if (tree == null) { 
     return null; 
    } else if (tree.key.equals(element)) { 
     tree.key = newElement; 
    } else if (tree.key.compareTo(element) < 0) { 
     return overwriteOne(tree.left, element, newElement); 
    } else if (tree.key.compareTo(element) > 0) { 
     return overwriteOne(tree.right, element, newElement); 
    } else { 
     return null; 
    } 
} 

：

は、私はあなたのコードのようになります期待します。

ツリーはその後、注文されていない場合は、左と右の両方のブランチをテストする必要があります：

T result = overwriteOne(tree.left, element, newElement); 
if (result == null) 
    result = overwriteOne(tree.right, element, newElement); 
return result; 

Answer 2

で起動するには：

• すぐに通過した後を返さないでください。左のサブツリーのみ。そうすることによって、あなたは正しいサブツリーを横断しているわけではありませんが、それは間違っています！
• 戻す前に、要素が見つかったかどうかを確認していません。要素がまだツリーに存在していても、NULLで返す可能性は非常に高いです。
• else-ifはここでは適用されません。左サブツリーがある場合、右サブツリーを単にスキップすることはできません。

要素が存在する（置換可能）かどうかを確認するには、ツリーの各ノードを走査する必要があります。下記の

はそれを動作させるためのコードです：

public T overwriteOne(TreeNode<T> tree, T element, T newElement) { 
    if (tree == null) return null; 

    T returnVal = null; 

    if (tree.key.equals(element)) { 
     tree.key = newElement; 
     returnVal = tree.key; 
    } 
    if (tree.left != null) { 
     returnVal = overwriteOne(tree.left, element, newElement); 
    } 
    if (returnVal == null && tree.right != null){ 
     returnVal = overwriteOne (tree.right, element, newElement); 
    } 
    return returnVal; 
}