在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++中遍历通用树的两种常用方法。根据具体的需求和场景,选择递归遍历或迭代遍历的方式来实现对通用树的遍历操作。
领取专属 10元无门槛券
手把手带您无忧上云