c++ - 在处理 N 元树遍历时我完全被卡住了

Question

事情是这样的。我想遍历我的 N 叉树(在这种情况下是家谱)中的任意两个节点。下面是我从根遍历到任意节点的情况的简化代码:

#include <iostream>
#include <string>
using namespace std;

const int max=100;

//structure definition
//every children has only one parent
struct Tree {
   string name;
   int numChildren;
   Tree *children[max];
   ~Tree(){delete [] children;}
}; 

//Label the nodes that are supposed to be in the path
//Suppose the names of those nodes do not contain whitespaces,just trivial names
int *travel_point(Tree *tree,string s){
    Tree *node = new Tree;
    Tree *temp = new Tree;
    node = tree;

    int a[100],i=0,j;
    for(j=0;j<100;j++) a[j]=-1;
    while(tree){
        if(tree->name == s){
           a[i]=0;
           break;
        }
        else{
           for(j=0;j<node->numChildren;j++){
              if(travel_point(node->children[j],s)!=NULL){
                break;      
                }
              }
           a[i]=j+1;
           i++;
           temp=node->children[j];
           node=temp;
        }
    }
    if(a[i-1]==-1) return NULL;
    else a;
}

这大致就是我一直在做的事情。因为每个 child 只有一个 parent ，那么从根到一个任意节点的路径也是唯一的。所以我想将所有其他路径设置为 NULL，以防我可以采取递归期间的优势。

我知道递归不是一个好主意，但我只是想试一试。

Answer 1

好吧，我不想解决你的作业，但我想给你一些建议。首先，树的递归函数通常很好，通常树的高度不会太深，所以递归函数很好。它们更易于编写和理解。

1) 你不能在你的堆栈内存中返回一个指向数组的指针并假装它会工作:)

2) 你需要一个堆栈类，使用std::stack<int> ，将一个非常量引用作为参数传递给它，这样您就可以在所有函数中修改它，并返回一个 bool 值，指示您是否找到了该节点。然后您可以将堆栈转换为 vector 或数组，但正如我想象的算法，您需要一个堆栈数据结构。

3) 不需要通过复制传递字符串，传递一个常量引用给它。 (常量字符串& s)

4)算法错误，重写。多想想。

5) 析构函数错误，它不会杀死子节点，但会进行无效的释放，你需要一个循环。

6) 我会使用 std::vector<Tree*> 而不是 [max] 个子树的数组

我把这个函数想象成...

bool travel_point(const Tree *tree, const string& s, stack<int>& result)

并使用它...

stack<int> path;
if (travel_point(mytree, "ciao", path))
{
    // print path
}