2

このインタビューの質問を理解するのに助けが必要です:

Q: 各ノードがその親へのリンクを持つ二分探索木で、特定のノードの次のノード (たとえば、順序どおりの後続ノード) を見つけるアルゴリズムを見つけてください。

親とは、順序どおりの先行者を意味しますか、それとも直接の親を意味しますか? ノードがルートノードまたは順序付けされた先行ノードへのリンクを持つツリーを作成するにはどうすればよいでしょうか? 以下のデータ構造とプログラムを理解する上で助けになれば幸いです...

解決策（フォームに投稿されたとおり）を以下に示します。

 public static TreeNode inorderSucc(TreeNode e) {
   if (e != null) {
     TreeNode p;

     // Found right children -> return 1st inorder node on right
     if (e.parent == null || e.right != null) {
       p = leftMostChild(e.right);
     } else {
       // Go up until we’re on left instead of right (case 2b)
       while ((p = e.parent) != null) {
         if (p.left == e) {
           break;
         }
         e = p;
       }
     }
     return p;
   }
   return null;
 }

 public static TreeNode leftMostChild(TreeNode e) {
   if (e == null) return null;
   while (e.left != null) e = e.left;
   return e;
 }
4

1 に答える 1

8

ノードが親へのポインタを格納する場合、ほとんどの場合、後続ノードではなく直接の親を意味します。このインタビューでの質問は、ツリーをナビゲートして順不同の後継者を見つける方法です。

in order の後継者を見つける方法は、再帰的にツリーの in order walk を実行した場合に何が起こるかを考え、次に何が起こるかを模倣することです。特に、順序通りのトラバーサルのロジックは、常にノードの左側のサブツリーのすべてを訪れ、次にノード自体、そして右側のサブツリーを訪れます。適切な後継者を見つけるには、自分がどのケースにいるかを確認する必要があります。

現在いるノードに適切なサブツリーがある場合、そのツリーの順序どおりの後継ノードは、順序どおりのトラバーサル中にそのサブツリーで最初にアクセスされるノードである必要があります。これは、そのツリーの最小要素です。これを見つけるには、右側のサブツリーに降りてから、ツリーの左側の背骨を下って、一番左のノードが見つかるまで進みます。

ノードに適切なサブツリーがない場合、それはサブツリー内の最大のノードです。再帰がどのように機能するかを考えてみると、順序通りのトラバーサルの次のステップは、正しいサブツリーの展開を終えたばかりのすべての再帰呼び出しを返すことです。この最後のフレームが戻ると、左側のサブツリーだけを展開した最初のツリーのノードにアクセスします。したがって、ノードの順序どおりの後継者は、左の子であるノードに到達するまでツリーを上ることで見つけることができます。このノードの親が後続ノードになります。または、エッジ ケースとして、ツリーのルートにヒットした場合、それも後継者になります。

お役に立てれば！

于 2011-03-06T20:38:10.257 に答える