1

親ノードと子ノードで構成されるツリーデータ構造があります。次のようなものです。

<Node1>
  <Node2/>

  <Node3>
    <Node4/>
  </Node3>
</Node1>

そして、構造を解析するために、μ再帰関数を使用します。

void RecursiveFunction(NodeT node)
{
    if(node.has_child())
        RecursiveFunction(node.child());
}

たとえば、Node2などのパラメータとしてRecursiveFunctionを呼び出す場合、最初のノードのデータは作成前に呼び出しスタックに保存されているため、追加のデータ構造を使用してこれらのデータを保存せずに、父（Node1）データにアクセスしたいと思います。再帰呼び出し。したがって、Node2を解析しているときに、コールスタックにアクセスして、Node1のデータを読み取る必要があります。これは、父親への直接アクセスに失敗するなどです。

たとえば、Node4を解析している場合：

void RecursiveFunction(NodeT node)
{
    /* Access to Node3 and Node1 data...

    if(Node4.has_child())
        RecursiveFunction(Node4.child()); */
}

出来ますか？どのように？

ありがとう。

4

5 に答える 5

1

それは可能ですが、そうすることは非常に危険です。これは主に、プロセススタックを混乱させたいためです。また、そうするためのライブラリ関数はないと思います。それを実現するには、いくつかのポインタ演算を実行する必要があると言われています。

于 2012-04-23T11:41:42.753 に答える
1

呼び出し元の関数からデータにアクセスする方法を見つけたとしても、他のプログラマーがあなたの行動を理解するのは簡単ではありません。

再帰を反復に置き換えて、やりたいことを明確に表現できるようにすることをお勧めします。詳細については、再帰から反復への移行方法を参照してください。

于 2012-04-23T11:47:22.937 に答える
1

コールスタックへのアクセスは、私にとって少し過剰な作業です。関数を再帰から反復に変換し、独自のスタックを使用します。スタックには、NodeTのインスタンスと、ノードの子の数がすでに処理されていることを関数に通知する整数値が含まれている必要があります。この値がノードの子カウントよりも小さい場合、ループはこの値をインクリメントし、次の子をスタックに追加します。それ以外の場合は、ノードを処理してからスタックからポップします。

もう1つの利点は、プログラムのスタックのサイズによる制限がなくなり、そのような必要がある場合は、より多くのネストされた構造を処理できることです。そうでなければ、あなたは危険を冒します、まあ、スタックオーバーフローと言うことを恐れないでください。

于 2012-04-23T11:49:23.930 に答える
0

再帰を使用する必要がある場合（宿題の要件など）は、関数の2番目の引数として親ノードを追加します。デフォルトNULLは、現在のノードがルートノードであることを示します。すなわち：

void RecursiveFunction(NodeT const& node, NodeT const* parentPtr=NULL)
{
    if(node.has_child())
        RecursiveFunction(node.child(), &node);
}

constを参照して最初の引数を受け入れるように関数を変更したことに注意してください。そうしないと、ツリーのコピーが多数作成されます。

于 2012-04-23T11:55:48.327 に答える
0

呼び出しスタックは関数パラメーターにも使用されるため*、それを使用してチェーンを構築します。

struct chain {
  NodeT* node;
  chain const* parent;
}
void RecursiveFunction(chain const& c)
{
    if(c.node->has_child()) {
       chain child = { c.node->child(), &c };
        RecursiveFunction(child);
    }
}

[*]少なくとも概念的には; 実際の実装は異なる場合があります。いずれにせよ、このC ++コードは、低レベルのハックとは異なり、移植可能です。

于 2012-04-23T13:27:16.080 に答える