在c++中遍历通用树

在C++中遍历通用树的方法有多种，以下是其中几种常用的方法：

递归遍历：递归是一种简单直观的遍历通用树的方法。通过递归函数，可以依次访问树的每个节点，并对其进行相应的操作。递归遍历通用树的常用方法有前序遍历、中序遍历和后序遍历。

前序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。
中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。
后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

以下是一个示例代码，展示了如何使用递归遍历通用树：

struct TreeNode {
    int val;
    vector<TreeNode*> children;
};

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    
    // 前序遍历
    cout << root->val << " ";
    
    for (TreeNode* child : root->children) {
        traverse(child);
    }
    
    // 后序遍历
    // cout << root->val << " ";
}

int main() {
    // 构建通用树
    TreeNode* root = new TreeNode{1, {
        new TreeNode{2, {
            new TreeNode{5, {}},
            new TreeNode{6, {}}
        }},
        new TreeNode{3, {}},
        new TreeNode{4, {}}
    }};
    
    // 遍历通用树
    traverse(root);
    
    return 0;
}

迭代遍历：除了递归遍历，还可以使用迭代的方式遍历通用树。迭代遍历通用树通常借助栈或队列来实现。

层序遍历：使用队列实现，先将根节点入队，然后依次出队并访问节点，将其子节点入队，直到队列为空。
其他遍历方式：使用栈实现，先将根节点入栈，然后循环出栈并访问节点，将其子节点入栈，直到栈为空。

以下是一个示例代码，展示了如何使用迭代遍历通用树：

struct TreeNode {
    int val;
    vector<TreeNode*> children;
};

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    
    stack<TreeNode*> stk;
    stk.push(root);
    
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        
        // 前序遍历
        cout << node->val << " ";
        
        // 将子节点逆序入栈
        for (int i = node->children.size() - 1; i >= 0; i--) {
            stk.push(node->children[i]);
        }
        
        // 后序遍历
        // cout << node->val << " ";
    }
}

int main() {
    // 构建通用树
    TreeNode* root = new TreeNode{1, {
        new TreeNode{2, {
            new TreeNode{5, {}},
            new TreeNode{6, {}}
        }},
        new TreeNode{3, {}},
        new TreeNode{4, {}}
    }};
    
    // 遍历通用树
    traverse(root);
    
    return 0;
}

以上是在C++中遍历通用树的两种常用方法。根据具体的需求和场景，选择递归遍历或迭代遍历的方式来实现对通用树的遍历操作。