c++ - 在树中穿行

Question

我正在研究 TreeDecomposition，其中树中的每个节点都可以从图中具有多个顶点。
现在，我正在尝试从树的根中找到包含顶点 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
        }
    }
}

我已经尝试过像上面那样，但它没有返回确切的节点索引。我在哪里做错了。

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;

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