遍历树数据结构

Question

我正在进行一项树分解，其中树中的每个节点可以来自图中的多个顶点。
现在，我正在尝试从树的根节点开始找到包含顶点u的第一个节点。

int Tree::traversing(Node* node, int u){ 
    //search in current node
    int j = node->point_in_bag(u); //this function returns position of vertex u in node if not available -1
    if(j != -1){
       return node->index;
    }
    else{       
    // traverse in its children
    for(int k=0; k<node->children.size(); k++){ // children has the node's childs in it
        Node* nod = node->children[k];
        cout << "nod index is " << nod->index << endl;
        traversing(nod,u); // if vertex isn't found in node, traverse again in its children
        }
    }
}

我已经尝试了上述方法，但没有返回确切的节点索引。我错在哪里了。

- user322

---

你的缩进和注释一团糟。事实上，有些明显应该在注释中的字符却没有，导致代码格式错误。请努力编写易读的代码供他人审查。 - Marcelo Cantos

抱歉，我会尽力改进它。 - user322

这个问题是算法中的基础问题。首先尝试理解如何以递归或非递归方式遍历二叉树。 - Mihai8

Answer 1

您在这里漏掉了一个return：

traversing(nod,u);

所以你的递归调用返回了一些随机数据（并且具有未定义的行为）。

即使你已经返回，你只会返回第一个子节点的索引。
如果没有找到，你需要继续查找。

for(int k=0; k<node->children.size(); k++){
    Node* nod = node->children[k];
    int childIndex = traversing(nod,u);
    if (childIndex != -1)
        return childIndex;
}
return -1;

你应该提高编译器的警告级别。

- molbdnilo

---

@user2139106 在编译器中启用警告。它应该能够捕捉到函数返回空值的情况。或者，如果已启用，请不要忽略它们。 - Alexey Frunze

@KarolyHorvath 是的，我只能遍历第一个子节点。我现在必须去解决这个问题。非常感谢您这么早就指出了这个问题。 - user322

@KarolyHorvath 哎呀，我错过了那部分。 - molbdnilo