1

it's ラベルを使用してノードを検索し、ターゲット ノードの下に新しいノードを追加しようとしています。再帰を使用して検索しようとすると、常に間違ったターゲットが返されるか、null が返されます。誰もそれを修正する方法を知っていますか?

public TreeNode getNodeReference(String label){

    if(left!=null){
        if(check(left,label)==true)
            return left;
         left.getNodeReference(label);
    }

    if(middle!=null){
        if(check(middle,label)==true)
           return middle;
        middle.getNodeReference(label);
    }
    if(right!=null)
     { if(check(right,label)==true)
          return right;
        right.getNodeReference(label);
    }
    return null;
}


public boolean check(TreeNode tree,String label){

    if(tree.getLabel().equals(label))
        return true;
    else return false;
}
4

2 に答える 2

1

問題は次のとおりです。内部呼び出しから返された値で何もしていません。

例えば ​​：

  1. 左が null ではない
  2. false を返す
  3. ラベルを付けて getNodeReference を呼び出す
  4. 左が null ではない
  5. check return true
    (最初の呼び出しに true を返しますが、それをキャッチするものは何もありません)
  6. 真ん中はnullではありません

  7. チェック...
    ...

    X. null を返します。

    ブーム！

于 2013-08-06T03:13:48.217 に答える
0

コードを実際にトレースすると、誤った結果が返される理由が明確にわかります。ツリーの最初のレベルの子のいずれもラベルと一致しない場合は、以下のコード パスにマークを付けました (左/中央/右がすべて非 null であると仮定します)。

public TreeNode getNodeReference(String label){

  if(left!=null){ // 1: left is not null
    if(check(left,label)==true) // 2: no match, proceed to 3
        return left;
    left.getNodeReference(label); // 3: called, but why? no side effect, no return.
  }

  if(middle!=null){ // 4
    if(check(middle,label)==true) // 5
       return middle;
    middle.getNodeReference(label); // 6
  }

  if(right!=null) { // 7
    if(check(right,label)==true) // 8
       return right;
    right.getNodeReference(label); // 9
  }

  return null; // 10: and finally we're here and we return null
}

基本的には、child.getNodeReference(label) を呼び出しますが、それだけです。あなたはそれを呼びます。次に、返された値を破棄して続行します。したがって、最初に getNodeReference を呼び出したノードの最初のレベルを超えて検索が実質的に下回ることはありません。

したがって、まず、この一般的なパターンが必要です。

if (child != null) { 
    if (check(child, label))
        return child; // match found
    TreeNode childResult = child.getNodeReference(label);
    if (childResult != null)
        return childResult; // match found deeper in tree; this is what you did not do.
}

そうは言っても、ここに短い実装があります（実装が getNodeReference が最初に呼び出された実際のノードのチェックもスキップしたため、これはあなたが持っていたものとまったく同じではないことに注意してください）：

public TreeNode getNodeReference (String label) {

    if (check(this, label))
        return this;

    TreeNode childResult = null; 
    if (left != null)
        childResult = left.getNodeReference(label);
    if (childResult == null && middle != null)
        childResult = middle.getNodeReference(label);
    if (childResult == null && right != null)
        childResult = right.getNodeReference(label);

    return childResult;

}

一般に、腰を落ち着けてコードをよく見て、一度に 1 行ずつ実行する必要があります。通常、それを行うと、このような問題が明らかになります。

それが役立つことを願っています。

于 2013-08-06T03:13:39.467 に答える