将条件递归算法转化为迭代算法

Question

最近，我写了一个基于递归的算法，用于水平打印二叉树。一般来说，我在将基于递归的算法转换为基于迭代的算法时没有任何问题，但我只是想不出如何做到这一点。

假设我们是一个向量

std::vector<int> tree = {10,9,8,7,6,5,4};

它表示以下树：

     10
    / \
   9   8
  /\   /\
 7 6   5 4

我的算法的工作方式如下：

index ->  left -> left      Or in our case 10 -> 9 -> 7
               -> right                            -> 6
      -> right -> left                        -> 8 -> 5
               -> right                            -> 4

等和扩展取决于树的大小。当我有条件地使用递归时，我无法思考的是如何将代码转换为while循环。我不太擅长解释，这是代码。

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unistd.h>

/* The Padding function handles the spacing and the vertical lines whenever we print a  *
 * right child. This depends on the previous parent-child hierarchy of the child        *
 * Printer handles the work of printing the elements and uses a depth-first-search      *
 * algorithm as it's core. Left children are printed horizontally while the right ones  *   
 * are printed vertically. Print_tree is a wrapper. It also finds the max-length value  *
 * which will be used for formatting so that the formatting won't get messed up because *
 * of the different number of digits.                                                   */           

std::string do_padding (unsigned index, unsigned mlength){
  std::string padding;
  while(int((index-1)/2) != 0){
    padding = (int((index-1)/2) % 2 == 0) ?
    std::string(mlength+4,' ') + " "  + padding :
    std::string(mlength+3,' ') + "| " + padding ;
    index = int((index-1)/2);
  }
  return padding;
}

template <class T>
void printer (std::vector<T> const & tree, unsigned index, unsigned mlength){
  auto last = tree.size() - 1 ;
  auto  left = 2 * index + 1 ;
  auto  right = 2 * index + 2 ;
  std::cout << " " << tree[index] << " " ;
  if (left <= last){
    auto llength = std::to_string(tree[left]).size();
    std::cout << "---" << std::string(mlength - llength,'-');
    printer(tree,left,mlength);
    if (right <= last) {
      auto rlength = std::to_string(tree[right]).size();
      std::cout << std::endl<< do_padding(right,mlength) << std::string(mlength+ 3,' ') << "| " ;
      std::cout << std::endl << do_padding(right,mlength) << std::string(mlength+ 3,' ') << "└─" <<
      std::string(mlength - rlength,'-');
      printer(tree,right,mlength);
    }
  }
}

template <class T>
void print_tree (std::vector<T> & tree){
  unsigned mlength = 0;
  for (T & element : tree){
    auto length = std::to_string(element).size();
    if (length > mlength) {
      mlength = length;
    }
  }
  std::cout <<  std::fixed << std::string(mlength- std::to_string(tree[0]).size(),' ') ;
  printer(tree,0,mlength);
}

int main() {
  std::vector<int> test;
  for (auto i =0; i != 200; ++i) {
    test.push_back(rand() % 12200);
  }
  std::make_heap(test.begin(),test.end());
  std::cout << std::endl << "Press ENTER to show heap tree.." << std::endl;
  std::cin.ignore();
  print_tree(test);
  std::cout << std::endl;
}

这可能不值得重写，但我想知道如何处理这样的递归，以防我将来要做类似的事情。

Answer 1

我记得，你贴了以树格式打印堆数组的问题。因此，对我来说(没有读过代码)，树遍历的核心算法是DFS。

要使这个递归算法迭代，您可以做的是使用堆栈。堆栈基本上保存所有已访问的节点，并允许返回它所选择的路径。在迭代DFS与递归DFS及不同元素顺序上给出了一个例子。

Answer 2

对于大多数遍历树的算法，如果要以非递归的方式构造数据结构，则需要额外的数据结构。对于深度优先遍历(在您的情况下)，通常使用堆栈(对于广度优先遍历，使用队列.)

在伪代码中，打印树看起来就像

function print_tree(tree_vector)
  s = new stack<int>()
  s.push(0)
  while (!s.empty())
    index = s.pop()
    print (tree_vector[index])
    left = 2*index + 1
    right = 2*index + 2
    if (right < tree_vector.size())
      s.push(right)
    if (left < tree_vector.size())
      s.push(left)
  end while
end function

请注意，此堆栈隐含地表示编译器在进行递归调用时内部使用的调用堆栈。