1

二分探索木の 2 つのノードが交換されます。

入力ツリー:

     10
    /  \
   5    8
  / \
 2   20

上記のツリーでは、ノード 20 と 8 を交換してツリーを修正する必要があります。

出力ツリー:

     10
    /  \
   5    20
  / \
 2   8

ここに記載されている解決策に従いました。しかし、次の理由により、解決策が正しくないと感じています。

サイトによると：

  1. スワップされたノードは、BST の順序どおりのトラバーサルでは隣接していません。

    たとえば、ノード 5 と 25 は で交換され{3 5 7 8 10 15 20 25}ます。
    与えられたツリーの順不同のトラバーサルは次のとおりです。3 25 7 8 10 15 20 5 注意深く観察すると、順不同のトラバーサル中に、ノード 7 が以前に訪問したノード 25 よりも小さいことがわかります。ここで、ノード 25 (前のノード) のコンテキストを保存します。ここでも、ノード 5 が前のノード 20 よりも小さいことがわかります。今回は、ノード 5 (現在のノード) のコンテキストを保存します。最後に、2 つのノードの値を交換します。

したがって、私のポイントは、5 よりも大きいため 20 を考慮すべきよりも 7 よりも大きいために 25 を考慮している場合です。

4

2 に答える 2

2

はい。7 より大きいので 25 を考慮しています。しかし、5 より大きいので 20 も考慮すべきではありません。代わりに、20 より小さいので 5 を考慮すべきです。

元の配列の 5 の位置が最後の配列であるため、この例はあまり適切ではありません。ソートされた配列を考えてみましょう{1, 2, 3, 4, 5}。2 と 4 を交換すると、 が得られ{1, 4, 3, 2, 5}ます。ソートされた配列内の 2 つの要素 (隣接していない) が交換された場合、 のようなすべてのペアについて(A[i], A[i+1])、間違った順序、つまり降順になっているペアが 2 つだけ存在します。の場合、{1, 4, 3, 2, 5}ペア(4, 3)、およびペアがあり(3, 2)ます。とのようなペア(A[p], A[p+1])とペアがあると仮定すると、それは交換されていると主張できます。の場合は4と2の入れ替わりです。(A[q], A[q+1])A[p] > A[p+1]A[q] > A[q+1]A[p]A[q+1]{1, 4, 3, 2, 5}

3 25 7 8 10 15 20 5では、25, 7と20 5の 2 つのペアだけが間違った順序になっています。次に、25 と 5 がスワップされる 2 つの要素です。

于 2013-11-09T23:03:56.547 に答える