0

BST内のノードの順序どおりの後続を見つけようとしていました。そして、以下は私のサンプルコードです。

public TreeNode getInorderSuccesor(TreeNode t)
{

    if(t == null)
    {
        return null;
    }

    if(t.getRight()!=null)
    {
        t = t.getRight();
        while(t.getLeft()!=null)
        {
            t = t.getLeft();
        }
        return t;
    }
    else
    {
        TreeNode parent = t.getParent();

        while(parent!=null && parent.getLeft() != t)
        {
            t = parent;
            parent = t.getParent();
        }
        return parent;
    }
}

失敗する条件があれば教えてください。そして、親ノードのないインオーダーサクセサを見つけるためにalgo / code/sudocodeを共有できる人がいる場合はもう1つ。ありがとう！！！

4

2 に答える 2

0

ツリー内のノードに一意の値がある場合、それは非常に単純です。あなたはただ見つける必要があります：

  • 後続ノードを決定する必要があるノードの値以下の最大数のノード
  • 後継者を決定する必要のあるノードの値よりも厳密に大きい最小数のノード。

後者のノードが答えになります。最初のノードは、入力ノードがツリー内の有効なノードであるかどうかを確認するために使用できます。

擬似コード：

function inOrderSuccessor(val, tree):
    (left, right) = findRange(val, tree.rootnode, null, null)

    if (left.val != val):
        throw Error("No node with specified value")

    return right


function findRange(val, currnode, left, right):
    if (currnode == null):
        return (left, right)

    if (currnode.val <= val):
        return findRange(val, currNode.right, currnode, right)
    else:
        return findRange(val, currNode.right, left, currnode)

ツリー内のノードの値が重複している可能性がある場合、順序どおりの後続ノードはあまり明確に定義されていません。ノードがいつ与えられるか、同じ値を持つ異なるノードをどのように区別するかを知る必要があります。ツリー内のノードへの実際の参照が与えられていますか？

単にノードへの参照が与えられ、ツリー内に同じ値を持つ他のノードがあるというトリッキーなケースでは、次の2つのケースがあります。

  • ケース1：ノードに適切なサブツリーがある場合、適切なサブツリーで最小の要素を見つけるだけで済みます。
  • ケース2：ノードに正しいサブツリーがありません。同じ値を持つすべてのノードとの参照の同等性をチェックする必要があります。ツリーでノードを見つけたら、ノードからルートに戻って上向きにトラバースし（これはスタックにあります）、左折する最初のノードを見つけます。
于 2013-02-28T14:38:11.343 に答える
0

後続関数の基本的なロジックは次のとおりです。先行機能は似ていますが、逆になっています。再帰関数は、要求されたキーを検索するためにツリーを下降し、左のサブツリーに続く場合は毎回可能な後続として現在のツリーを追跡します。キーが見つかった場合、その後続要素は、null ノードに到達するまで左のサブツリーを追跡することによって見つかった、右のサブツリーの最小要素です。検索がヌル ノードに達したためにキーが見つからない場合、ツリー内で次に大きいキーが後続キーであり、各再帰呼び出しで保存された可能性のある後続キーで見つかります。最近、このアルゴリズムをブログに実装しました。

于 2013-02-28T13:53:08.727 に答える