1

BST内の要素のサクセサは、インオーダートラバーサルによって決定されたソートされた順序での要素のサクセサです。各ノードがその親ノードへのポインターを持っているときに後継者を見つけることは、CLRSのアルゴリズム教科書（MITプレスによるアルゴリズムの紹介）に示されています。

ここでサクセサを見つけるという考え方は、ノードの右側のサブツリーxが空でない場合、のサクセサはx右側のサブツリーの最小要素です。xそれ以外の場合、後継者は、左の子がの祖先でもある最下位の祖先ですx（ノードがそれ自体の祖先であると想定）。

親ノードへのポインタを使用せずに後継者を見つけることはできますか？

ツリーノードにこのポインタがない場合があります。数時間苦労しましたが、正しいコードを書くことができません。

4

5 に答える 5

7

シェルドンのソリューションに触発された、これはソリューションの非再帰バージョンです。


if (right[x]  != NIL)
    return min(right[x]);
else
{
    candidate = NIL;
    y = root; 
    while  (y!= x) // y is used as a probe

        if (key[x] < key[y])
            {
            candidate = y;
            y = y ->left;

             }
        else
            y = y->right;
}
return candidate;
候補==NILの場合、xはツリーの最大値であり、後継はありません。

于 2010-09-26T17:17:31.657 に答える
4

これは機能するはずです：

TREE-SUCCESSOR(T, x)
  if right[x] != NIL
    return TREE-MINIMUM(right[x])
  else
    return FIND-TREE-SUCCESSOR(root[T], x, NIL)

FIND-TREE-SUCCESSOR(y, x, c)
  if y = x
    return c
  if key[x] < key[y]
    return FIND-TREE-SUCCESSOR(left[y], x, y)
  else
    return FIND-TREE-SUCCESSOR(right[y], x, c)

FIND-TREE-SUCCESSORc（候補の）左に曲がった最後のノードを保持します。

于 2010-09-26T00:15:13.487 に答える
2

ここで、親ポインターのない順序どおりの後継者のためのエレガントなソリューションを見つけました-> http://www.geeksforgeeks.org/archives/9999

アイデアは

1.ノードに右のサブツリーがある場合、その後続ノードは右のサブツリーの最小要素です

  1. ノードの右側のサブツリーが空の場合、その後続はその祖先の1つであり、次のアルゴリズムを使用して、親ポインターなしでトップダウンで見つけることができます。

最初にcurrent_nodeをrootとし、succ_node = null;

ケース1：検索要素がcurrent_nodeより小さい場合、現在の要素は潜在的な後継要素です-current_nodeにsucc_nodeを配置し、current_nodeを左側のノードに移動します（検索要素は左側のサブツリーにあるため）

case2：検索要素がcurrent_nodeより大きい場合、それは潜在的な後継者ではありません（どのようにして、より小さな要素が後継者になることができますか？）。したがって、ここにsucc_nodeを配置する必要はありませんが、current_nodeを右に移動します。

nullまたは要素自体に到達し、succ_nodeを返すまで、このプロセスを繰り返します。

于 2012-09-13T00:17:03.250 に答える
0

親ノードへのポインタにアクセスできない場合は、父親が誰であるかを知る必要があります。あなたがそれを知らないなら、どうやって木に登ることができますか？

于 2010-09-25T23:55:55.133 に答える
0

再帰的なJavaソリューションは、次のようになります。

public Integer successor(Integer value) {
    Node n = succ(root, value, null);
    if (null != n) {
       return n.value;
    }
    return null;
}

private Node succ(Node n, Integer x, Node p) {
    if (null == n) {
        return null;
    }

    if (x < n.value) {
        return succ(n.left, x, n);
    } else if (x > n.value) {
        return succ(n.right, x, p);
    }
    if (null != n.right) {
        return min(n.right);
    }
    return p;
}

クライアントとして、後継者を知りたいノードの値を渡すだけです。次に、探している値が見つかるまで、ルートから検索を開始します。現在、2つのケースがあります。

  1. 現在のノードに右の子がある場合、後続のノードの右のサブツリーの最小要素
  2. それ以外の場合は、ノードp（親ポインター）であり、ツリー内を左に移動したときにのみ更新されました。
于 2013-09-09T16:41:18.713 に答える