搜索树和输出的路径在C++节点

Question

假设我们有以下结构：

struct ATree { 
    string id; 
    int numof_children; 
    ATree *children[5]; 
}; 

我如何将能够路径搜索ID和输出到ID？我有一种方法来查找id是否在树中，但输出正确的路径是另一回事。我曾尝试使用字符串流，但它似乎并没有正常工作（我得到的路径，包括ID不会导致我想要的ID）。注意：假定ids可能只在树中出现一次

这是否应该使用递归完成？或者可以使用循环来完成？

Answer 1

对于您正在经历的每个节点，您应该基本上保留从哪个节点到达当前节点。然后将它们弹出并在您找到正确路径时将其打印出来。

如果将它们保留在std::stack结构中，当您在到达树叶后返回并且找不到所需的id时，您将很容易弹出它们。

如果你递归执行，那么你只需要有你的调用堆栈，它应该是足够的，如果你将它们转换为循环（迭代），那么你需要std::stack记住状态，但它非常简单，真的。

Answer 2

算法的粗线条：

std::vector< const ATree* > 
getPath(const ATree* tree, const std::string& id) 
{ 
     std::vector< const ATree* > path; 

     if (tree->id == id) { 
       path.push_back(tree); 
     } else { 
       for (int i=0; i < tree->numof_children; i++) { 
         std::vector< const ATree* > tmp= 
           getPath(tree->children[i], id); 
         if (tmp.size() > 0) { 
          path.push_back(tree); 
          path.insert(path.end(), tmp.begin(), tmp.end()); 
           break; 
         } 
       } 
     } 

     return path; 
} 

Answer 3

我相信下面的代码给你的，你应该做的（递归）一个概念：

bool find(const string& i_id, const ATree* i_tree, string& o_path) { 
    if(!i_tree) return false; 
    if (i_id == i_tree->id) { 
    o_path = i_tree->id; 
    return true; 
    } 
    string path; 
    for (size_t i = 0; i < i_tree->numof_children; ++i) { 
    if (find(id, i_tree->children[i], path)) { 
     o_path = i_tree->id + '/' + path; 
     return true; 
    } 
    } 
    return false; 
}