在这种情况下如何将递归修改为循环版本？

Question

我想修改下面的c++代码，使用循环而不是递归。 我知道有两种修改方法：

1. 学习代码，制作循环算法。在这种情况下，我认为代码的含义是按级别顺序打印B（除了叶子）和打印A（期望根）。对于二叉（搜索）树，如何在循环中从叶到根遍历它（没有指向父级的指针）？

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();
   }
   

Answer 1

假设您正在使用 C++

对于堆栈部分，可以说，代码执行以下操作。

1. 如果节点是叶子，则什么都没有。
2. 否则对每个孩子做同样的事情，然后在每个孩子之后打印A。
3. 然后打印B。

如果我稍微调整一下代码又如何呢？调整仅适合迭代方式。

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();
     }
}

希望我正确地编写了代码。 :) 我希望它有帮助。