3

二分探索木が与えられます。その境界を見つける必要があります。

したがって、二分木が 

           10
       /         \
     50           150
    /  \         /   \
  25    75     200    20
 / \           /      / \
15 35        120    155 250

印刷する必要があります50 25 15 35 120 155 250 20 150 10。

二分木が

               10
           /         \
         50           150
        /  \         /   
      25    75     200   
     / \   / \    
    15 35 65 30

のようになります50 25 15 35 65 30 200 150 10。

これはどのように行うことができますか？これを二分木に一般化すると、問題はさらに難しくなりますか？

リンクを介したヘルプも歓迎されます。

PS：パターンがルートからではなく、左から始まることを確認してください（この場合）。また、rightで始まる場合もありますが、常にrootで終わります。

4

4 に答える 4

2

あなたが求めているのは、修正された深さ優先走査であり、ノードの値は、1）ノードがリーフノードであるか、2）ノードがツリーの「外部パス」に沿っている場合にのみ出力/返されます。パス」は次のように定義されます

ルートからすべての左（または右）パスをたどってノードに到達した場合、またはノードが親ノードの右（または左）子であった場合、ノードは「外部パス」の一部です。それ自体は「外側の道」の一部ですが、左（または右）の子供はいませんでした。

DFSのコーディング方法を知っている場合は、トラバーサル中にいくつかの追加条件をチェックすることで、ここでの変更を実装できます。

于 2010-09-20T17:46:29.483 に答える
0

これが二分木であるかどうかが重要かどうかはわかりません。ウォークアルゴリズムはどちらの方法でも同じだと思います。

左側のサブツリーから開始し、ノードが左側の兄弟またはエッジである場合にのみノードを出力する、変更された幅優先探索を実行します。これにより、左の兄弟が端に当たるまで印刷され、次に葉が印刷されます。

次に、変更された深さを実行します。最初に、右の兄弟または葉のいずれかを印刷する右の木を歩きます。これにより、すべての適切なサブツリーの葉が印刷され、次に適切な兄弟が印刷されます。

于 2010-09-20T17:56:20.330 に答える
0 
printBorder(node *n){

   printLeft(n);   O(log n)
   printBottom(n); O(n)
   printRight(n);  O(log n)
}

printBottom(node *n)
{
  int h = treeHeight(n);
  printBottomHelper(n, 0);
}
printBottomHelper(n, h, max)
{
   if(h == max) {
    print n->data
  }
   printBottomHelper(n->left, h+1, max);
   printBottomHelper(n->right, h+1, max);
}
printLeft(node *n)
{
  while(n!= null){
   node *l = n->left;
   l!= null ? print l->data:1
   n =l;
  }
}
于 2011-08-30T15:59:04.163 に答える
0

何を印刷するかを言うために2つのブール値を維持できます。

printBorder（root、true、true）を呼び出して開始します。編集：最後にルートを出力しませんが、最初は特別な場合が必要です。

function printBorder(
Node node, bool printLeft, bool printRight, int height, const int MAX_HEIGHT) {
  if (printLeft || printRight ||
  (node.left == null && node.right == null && height == MAX_HEIGHT)) {
    print node;
  }
  if (node.left) printBorder(node.left, printLeft, printRight && node.right==null)
  if (node.right) printBorder(node.right, printLeft && node.left == null, printRight)
}

ここで、MAX_HEIGHTはmaxdepth（root、0）;によって検出されます。

int maxdepth(Node node, int height) {
  if (node == null) return height;
  return max(maxdepth(node.left, height+1), maxdepth(node.right, height+1))
}
于 2011-12-09T08:13:12.977 に答える