用c++实现二叉树的先序遍历和层次遍历带注释
时间: 2024-03-17 21:45:32 浏览: 126
c实现二叉树先序层序遍历
5星 · 资源好评率100%
好的,下面是用 C++ 实现二叉树的先序遍历和层次遍历的代码,带有详细注释:
```
#include <iostream>
#include <queue>
using namespace std;
// 定义二叉树的节点结构体
struct TreeNode {
int val; // 节点的值
TreeNode* left; // 左子节点指针
TreeNode* right; // 右子节点指针
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} // 构造函数
};
// 先序遍历二叉树,参数为根节点指针
void preOrder(TreeNode* root) {
if (root == nullptr) { // 如果节点为空,直接返回
return;
}
cout << root->val << " "; // 输出节点的值
preOrder(root->left); // 递归遍历左子树
preOrder(root->right); // 递归遍历右子树
}
// 层次遍历二叉树,参数为根节点指针
void levelOrder(TreeNode* root) {
if (root == nullptr) { // 如果节点为空,直接返回
return;
}
queue<TreeNode*> que; // 定义队列,用于存储每一层的节点
que.push(root); // 将根节点入队
while (!que.empty()) { // 队列非空时循环
TreeNode* node = que.front(); // 取出队首节点
que.pop(); // 将队首节点出队
cout << node->val << " "; // 输出节点的值
if (node->left != nullptr) { // 如果左子节点不为空,入队
que.push(node->left);
}
if (node->right != nullptr) { // 如果右子节点不为空,入队
que.push(node->right);
}
}
}
int main() {
// 构建一棵二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 先序遍历二叉树
cout << "Pre-order traversal: ";
preOrder(root);
cout << endl;
// 层次遍历二叉树
cout << "Level-order traversal: ";
levelOrder(root);
cout << endl;
return 0;
}
```
这个程序将输出以下结果:
```
Pre-order traversal: 1 2 4 5 3 6 7
Level-order traversal: 1 2 3 4 5 6 7
```
其中,先序遍历的结果为 `1 2 4 5 3 6 7`,层次遍历的结果为 `1 2 3 4 5 6 7`。
阅读全文