1

私は二分木（二分探索木ではない）の順序どおりの後継を見つけるためのコードを書いていました。それはただの練習問題です。ツリーの概念をブラッシュアップするのが好きです。

私は順番にトラバーサルを行い、前のノードを追跡していました。前のノードが、後継ノードを検索しているノードと等しくなるたびに、現在のノードを出力します。

void inOrder(node* root , node* successorFor) {
  static node* prev = null;
  if(!root)
     return;
  inOrder(root->left,successorFor);
  if(prev == successorFor )
     print(root);
  prev = root;
  inOrder(root->right,successorFor);
}

ソリューションが失敗する可能性のあるテストケースを探していましたか？そして、私のアプローチが正しいかどうか？そうでない場合は、どうすればよいですか？

4

1 に答える 1

0

このアルゴリズムの基本的なロジックはtree walk. あなたは次のように電話をかけますprint(TREE-SUCCESSOR(root, k).key)

TREE-SUCCESSOR(root, k)
    if root == NIL
        return NIL
    left = TREE-SUCCESSOR(root.left, k)
    right = TREE-SUCCESSOR(root.right, k)
    successor = NIL
    if root.key > k
        successor = root
    if left
        if k < left.key
            if successor
                if left.key < successor.key
                    successor = left
            else
                successor = left
    if right
        if k < right.key
            if successor
                if right.key < successor.key
                    successor = right
            else
                successor = right
    return successor
于 2012-09-18T10:50:39.267 に答える