时间戳

首页 > 解决方案 > C++ - 在 n 叉树上迭代

c++ - C++ - 在 n 叉树上迭代

问题描述

这是在 n 元树上具有迭代算法的函数，给定 a name，并使用它来查找父树，parent tree's data如果找到则返回，"ZERO"如果没有找到父树，并且"NA"如果name不在Tree<string>*向量中的任何树中。它大部分时间都有效，但偶尔会给出错误的输出，"ZERO"应该找到父级，主要在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";
}

这是树的类模板：

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

有时得到错误结果的可能原因是什么？

// 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"

标签： c++loopstree

解决方案

您应该推送您访问的当前节点/树的子节点。

我还删除了一些副本。

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

推荐阅读