CODEWITHSUNDEEP
c++loopstree
keanehui
keanehui

Reputation: 195

C++ - iteration over a n-ary tree

This is the function with iteration algorithm over a n-ary tree, given a name, and use it to find the parent tree, return parent tree's data if found, "ZERO" if no parent is found, and "NA" if the name is not in any tree in the Tree<string>* vector. It works most of the time, but will occasionally give wrong output that "ZERO", which a parent was supposed to be found, mostly in the leaves.

string getSource(const string name) const { // no recursion
    if (existInVector(name, trees)) { // vector of Tree<string>*
        queue<Tree<string>> treesQueue;
        vector<Tree<string>*>::const_iterator it = trees.begin();
        for (; it != trees.end(); ++it) { // for each tree
            treesQueue.push(**it); // push tree
            for (int i = 0; i < (**it).root->numChildren; ++i) // push children
                treesQueue.push((**it).root->children[i]);
            while (!treesQueue.empty()) {
                Tree<string> temp = treesQueue.front(); // pop front
                treesQueue.pop();
                for (int i = 0; i < temp.root->childCount; ++i) { // check
                    if (temp.root->children[i].root->data == name)
                        return temp.root->data;
                }
            }
            if (it == trees.end()-1 && treesQueue.empty())
                return "ZERO";
        }
    }
    return "NA";
}

Here is the class template of the tree:

template <class T>
class Tree {
private:
    Node<T>* root;
public:
    // ... member functions ...
};

template <class T>
class Node {
private:
    T data;
    int numChildren;
    Tree<T>* children; // Tree<T> array
};

What is the possible reason to get the wrong result sometimes?

// example with wrong result
Tree<string> tree; // below is what is inside, root is Node "G", "H" is child of "G" and so on
G
\-H
  \-I
    \-J

tree.getSource("J") == "ZERO"; // Supposed to be "I"

Upvotes: 1

Views: 613

Answers (1)

Jarod42
Jarod42

Reputation: 217275

You should push children of current node/tree you visit.

I also remove some copies.

std::string getSource(const std::string& name) const {
    if (!existInVector(name, trees)) { // vector of Tree<string>*
        return "NA";
    }
    std::queue<const Tree<std::string>*> treesQueue;
    for (const auto& tree : trees) {
        treesQueue.push(&tree);
        while (!treesQueue.empty()) {
            const auto& current = *treesQueue.front();
            treesQueue.pop();
            for (int i = 0; i != current.root->childCount; ++i) {
                const auto& child = current.root->children[i];
                if (child.root->data == name)
                    return current.root->data;
                treesQueue.push(&child);
            }
        }
    }
    return "ZERO";
}

Upvotes: 1

Related Questions