4

反復版を書くように頼まれましたが、再帰版を書きました。

void inorderTraverse(BinaryTree root)
{
    if(root==NULL)
        printf("%d",root->id);
    else
    {
        inorderTraverse(root->left);
        printf("%d",root->id);
        inorderTraverse(root->right);
    }
}

私はコードを探しているわけではありません。これがどのように行われるかを理解したいのです。それが最後の再帰呼び出しだったら、私はそうしていただろう

void inorderTraverse(BinaryTree root)
{
    while(root!=NULL)
    {
        printf("%d",root->id);
        root=root->right;
    }
}

しかし、再帰呼び出しが 2 つある場合、どのように反復プログラムに変換すればよいでしょうか?

ここに型定義があります。

struct element{
    struct element* parent;
    int id;
    char* name;
    struct element* left;
    struct element* right;
};
typedef element* BinaryTree;

これは私が考えたことです、私は正しい軌道に乗っていますか？

temp=root;
while(1)
{
    while(temp!=NULL)
    {
     push(s,temp);
     temp=temp->left;
     continue;
    }

    temp=pop(s);
    if(temp==NULL)
    return;
    printf("%d\t",temp->data);
    temp=temp->right;
}
4

4 に答える 4

4

あなたが見ている問題は、反復していた最後の場所を「覚えておく」必要があるということです。
再帰を行うとき、プログラムは内部的に「スタック」を使用して、どこに戻るかを記憶します。
しかし、反復を行うときはそうではありません。

でも...それはあなたにアイデアを与えますか？

于 2011-09-25T19:42:25.500 に答える
0

親ノードから左ノードへの反復は問題ではないと私は当然のことと考えています。問題は、1 つのノードから親ノードに移動するときに何をすべきかを知ることです。正しい子ノードを取得する必要がありますか、それとももう 1 つの親ノードに移動する必要がありますか?

次のトリックが役に立ちます。

上に行く前に、現在のノードを思い出してください。それから上に行きます。これで比較できます: 左のノードに行ったことがありますか: 次に、右のノードを使用します。それ以外の場合は、親ノードをもう 1 つ上に移動します。

このために必要な参照/ポインタは 1 つだけです。

于 2011-09-25T20:38:28.147 に答える
0

これを繰り返しオフハンドで行うための本当にエレガントな方法は考えられません。

1つの可能性は、「マークアルゴリズム」を使用することです。この場合、すべてのノードを「マークなし」で開始し、ノードを「マーク」して処理します。マーカーは、オブジェクト モデルに追加することも、別のエンティティに保持することもできます。

擬似コード:

for (BinaryTree currentNode = leftmostNode(root); currentNode != null; currentNode = nextNode(currentNode)):
  print currentNode;
  currentNode.seen = true;

sub nextNode(BinaryTree node):
  if (!node.left.seen):
    return leftmostNode(node.left)
  else if (!node.seen)
    return node
  else if (!node.right.seen)
    return leftmostNode(node.right)
  else 
    return nextUnseenParent(node)

sub leftmostNode(BinaryTree node):
  while (node.left != null)
    node = node.left
  return node;

sub nextUnseenParent(BinaryTree node):
  while (node.parent.seen)
    node = node.parent
  return node.parent
于 2011-09-25T19:55:54.450 に答える