прохождение по дереву

Question

прохождение по дереву

Я работаю над TreeDecomposition, где каждый узел в дереве может иметь более одной вершины графа.
Теперь я пытаюсь найти первый узел который содержит вершина у из корня дерева.

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
}
}
}

Я пытался, как выше, но это не возвращает точный индекс узла. где я делаю не так

3

c++tree-traversal

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы забыли 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;

Вы должны увеличить уровень предупреждения на вашем компиляторе.

2