1

以下の C++ コードを変更して、再帰の代わりにループを使用したいと考えています。私はそれを変更する2つの方法を知っています:

  1. コードから学び、ループ アルゴリズムを作成します。この場合、コードの意味は、レベル順で printB (葉を除く) と printA (ルートを期待) にあると思います。二分 (検索) ツリーの場合、ループ内で (親へのポインターなしで) リーフからルートにトラバースするにはどうすればよいですか?

  2. スタックを使用して、スタック上のプロセスを模倣します。その場合、うまくいかないのですが、役に立つ考えを教えてもらえますか?

    void func(const Node& node) {

    if (ShouldReturn(node)) {
        return;
    }

    for (int i = 0; i < node.children_size(); ++i) {
        const Node& child_node = node.child(i);
        func(child_node);
        PrintA();
    }

    PrintB();
}
4

1 に答える 1

0

C++を使用していると仮定します

スタック部分については、たとえば、コードは次のことを行います。

  1. ノードがリーフの場合は何もありません。
  2. それ以外の場合は、各子に対して同じことを行い、それぞれの後に printA を実行します。
  3. 次にprintB。

では、コードを少し調整するとどうなるでしょうか。調整は反復的な方法にのみ適合します。

void func(const Node& node) {
    if(ShouldReturn(node)) return;
    PrintB();
    for(int i = 0; i < node.children_size(); ++i) {
        printA();
        const Node& child_node = node.child(i);
        func(child_node, false);
    }
}
// This way should make it print As & Bs in reverse direction.
// Lets re-adjust the code even further.

void func(const Node& node, bool firstCall = true) {
    if(!firstCall) printA; //Placed that here, as printA is always called if a new Node is called, but not for the root Node, that's why I added the firstCall.
    if(ShouldReturn(node)) return;
    PrintB();
    for(int i = 0; i < node.children_size(); ++i) {
        const Node& child_node = node.child(i);
        func(child_node, false);
    }
}

AとBの印刷の順序が逆になるはずです。間違っていないことを願っています:Dだから、今は2つのベクトルが必要です。

// Lets define an enum
typedef enum{fprintA, fprintB} printType;

void func(const Node& node){
     vector<printType> stackOfPrints;
     vector<Node*> stackOfNodes; stackOfNodes.push_back(node);
     bool first = true; //As we don't need to printA before the root.
     while ((int)stackOfNodes.size() > 0){
         const Node& fNode = stackOfNodes.back();
         stackOfNodes.pop_back();
         if (!first) stackOfPrints.push_back(fprintA); // If not root printA.
         first = false;
         if(ShouldReturn(fNode)) continue;
         stackOfPrints.push_back(fprintB);
         // here pushing the Nodes in a reverse order so that to be processed in the stack in the correct order.
         for(int i = (int)fNode.children_size() - 1; i >= 0; --i){
               stackOfNodes.push_back(fNode.child(i));
         }
     }

     // Printing the stackOfPrints in reverse order (remember we changed the code, to initially print As & Bs in reverse direction) 
     // this way, it will make the function print them in the correct required order
     while((int)stackOfPrints.size() > 0){
         switch(stackOfPrints.back()){
            case fprintA: printA(); break;
            case fprintB: printB(); break;
            default: break;
         };
         stackOfPrints.pop_back();
     }
}

コードを正しく書くことを望みましょう。:) お役に立てば幸いです。

于 2012-09-17T18:22:33.340 に答える