帮我写一个二叉树的建立与遍历的代码
时间: 2023-08-28 16:18:39 浏览: 70
好的,下面是二叉树的建立与遍历的代码实现:
```cpp
#include <iostream>
#include <queue>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 递归方式建立二叉树
void buildTree(TreeNode*& root) {
int val;
cin >> val;
if (val == -1) { // 如果输入值为 -1,表示该节点为空节点
root = nullptr;
} else {
root = new TreeNode(val);
buildTree(root->left); // 递归建立左子树
buildTree(root->right); // 递归建立右子树
}
}
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (root != nullptr) {
cout << root->val << " "; // 先访问根节点
preorderTraversal(root->left); // 再访问左子树
preorderTraversal(root->right); // 最后访问右子树
}
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root != nullptr) {
inorderTraversal(root->left); // 先访问左子树
cout << root->val << " "; // 再访问根节点
inorderTraversal(root->right); // 最后访问右子树
}
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root != nullptr) {
postorderTraversal(root->left); // 先访问左子树
postorderTraversal(root->right); // 再访问右子树
cout << root->val << " "; // 最后访问根节点
}
}
// 层序遍历
void levelorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}
}
int main() {
TreeNode* root;
buildTree(root);
cout << "前序遍历结果:" << endl;
preorderTraversal(root);
cout << endl;
cout << "中序遍历结果:" << endl;
inorderTraversal(root);
cout << endl;
cout << "后序遍历结果:" << endl;
postorderTraversal(root);
cout << endl;
cout << "层序遍历结果:" << endl;
levelorderTraversal(root);
cout << endl;
return 0;
}
```
代码中使用了递归方式建立二叉树,并实现了四种遍历方式:前序遍历、中序遍历、后序遍历和层序遍历。你可以根据需要选择不同的遍历方式来输出二叉树的节点值。
阅读全文