0

二分探索ツリーでノードの深さを見つける関数を実装しましたが、実装は重複を処理しません。私は以下のコードを持っていますが、この関数で重複ケースを考慮する方法についていくつか提案をしたいと思います。あなたの助けを本当に感謝します.

public int depth(Node n) {
    int result=0;
    if(n == null || n == getRoot())
        return 0;

    return (result = depth(getRoot(), n, result));
}
public int depth(Node temp, Node n, int result) {
    int cmp = n.getData().compareTo(temp.getData());

    if(cmp == 0) {
        int x = result;
        return x;
    }
    else if(cmp < 0) {
            return depth(temp.getLeftChild(), n, ++result);
        }
        else {
            return depth(temp.getRightChild(), n, ++result);
        }                   
}
4

2 に答える 2

0

重複がある場合、特定の値を持つノードの深さはそれ自体では意味がありません。その値を持つ複数のノードが存在する可能性があるため、複数の深さになります。

それが何を意味するかを決定する必要があります (必ずしも完全なリストではありません)。

  • その値を持つ最も深いノードの深さ。
  • その値を持つ最も浅いノードの深さ。
  • その値で見つかった最初のノードの深さ。
  • その値を持つすべてのノードの平均深度。
  • その値を持つすべてのノードの深さの範囲 (最小/最大)。
  • その値を持つすべてのノードの深さのリスト。
  • クエリを示すエラー コードはほとんど意味がありません。

これらのいずれも、特定の状況では理にかなっている可能性があります。

もちろん、がノードへの実際のポインターである場合、ノードの値をn比較するべきではなく、ポインターを比較する必要があります。そうすれば、一致するものが1 つしか見つからず、その深さが理にかなっています。

次の疑似コードのようなことを行う必要があります。

def getDepth (Node needle, Node haystack, int value):
    // Gone beyond leaf, it's not in tree

    if haystack == NULL: return -1

    // Pointers equal, you've found it.

    if needle == haystack: return value

    // Data not equal search either left or right subtree.

    if needle.data < haystack.data:
        return getDepth (needle, haystack.left, value + 1)

    if needle.data > haystack.data:
        return getDepth (needle, haystack.right, value + 1)

    // Data equal, need to search BOTH subtrees.

    tryDepth = getDepth (needle, haystack.left, value + 1)
    if trydepth == -1:
        tryDepth = getDepth (needle, haystack.right, value + 1)

    return trydepth

値が等しい場合に両方のサブツリーを検索する必要があるのは、目的のノードがいずれかのサブツリーにある可能性があるためです。値が等しくない場合は、それがどのサブツリーにあるかがわかります。したがって、値が等しい場合は一方のサブツリーをチェックし、見つからない場合は他方をチェックします。

于 2012-11-15T06:33:26.600 に答える
0

あなたが示すコードでは、同じ値を持つノードを別のノードよりも優先する方法はありません。差別化するには、いくつかの基準が必要です。たとえば、次の方法を使用して、すべての重複ノードの深さのリストを取得できます。

  1. ノードの深さを見つけます。
  2. 見つかったノードから出現する左サブツリーの同じノードの深さを見つけます - 見つからない場合は停止します。
  3. 以前に見つかったノード (1) の深さを複製の深さに追加します
  4. 見つかったノードから出現する右側のサブツリーの同じノードの深さを見つけます (1) - 見つからない場合は停止します。
  5. 以前に見つかったノード (1) の深さを複製の深さに追加します
  6. 左右のサブツリーについて繰り返します。

ここも参照してください: BST での重複の場合はどうなりますか?

于 2012-11-15T06:34:40.590 に答える