多叉树全路径遍历C++示例

多叉树（也称n叉树或多度树），除了每个节点最多有两个子节点外，每个节点可以有任意数量的子节点。全路径遍历，又称为深度优先搜索（DFS），对于多叉树，就是按照从根节点到叶子节点的路径顺序访问所有节点。

下面是一个简单的C++示例，使用递归实现了多叉树的全路径遍历：

#include <iostream>
#include <vector>

// 定义一个多叉树节点
template<int N>
class MultiTreeNode {
public:
    std::vector<int> children;  // 存储子节点的值
    void addChild(int value) { children.push_back(value); }  // 添加子节点
};

// 遍历函数
template<int N>
void dfs(const MultiTreeNode<N>& node, std::string& path) {
    if (!node.children.empty()) {
        for (const auto& child : node.children) {
            path += to_string(child) + " -> ";
            dfs(node.children[child], path);
        }
        path.pop_back();  // 移除最后一个箭头
    } else {
        std::cout << path << node.children[0] << '\n';  // 如果是叶子节点，则打印路径
    }
}

int main() {
    MultiTreeNode<3> root;
    root.addChild(1);
    root.addChild(2);
    root.children[0].addChild(3);
    root.children[0].addChild(4);

    std::string path = "";
    dfs(root, path);
    return 0;
}

在这个例子中，我们首先创建了一个3叉树的根节点，然后添加了一些子节点。`dfs` 函数接受一个节点和当前的路径，对每个子节点进行递归调用，直到遇到叶子节点，最后打印出完整的路径。