从键盘输入二叉树的元素,建立二叉树,实现二叉树的遍历程序
时间: 2023-12-01 20:14:24 浏览: 37
好的,关于你的问题,我可以提供以下的 C++ 代码实现二叉树的建立和遍历。
```cpp
#include<iostream>
#include<queue>
using namespace std;
struct TreeNode {
char value;
TreeNode* left;
TreeNode* right;
TreeNode(char val) : value(val), left(nullptr), right(nullptr) {}
};
// 建立二叉树
TreeNode* createBinaryTree() {
char c;
cin >> c;
if (c == '#') {
return nullptr;
}
TreeNode* root = new TreeNode(c);
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
// 前序遍历
void preOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->value << " ";
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
// 中序遍历
void inOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inOrderTraversal(root->left);
cout << root->value << " ";
inOrderTraversal(root->right);
}
// 后序遍历
void postOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->value << " ";
}
// 层次遍历
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->value << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}
int main() {
cout << "请按照前序遍历的顺序输入二叉树的元素,'#'表示空节点:" << endl;
TreeNode* root = createBinaryTree();
cout << "前序遍历结果:";
preOrderTraversal(root);
cout << endl;
cout << "中序遍历结果:";
inOrderTraversal(root);
cout << endl;
cout << "后序遍历结果:";
postOrderTraversal(root);
cout << endl;
cout << "层次遍历结果:";
levelOrderTraversal(root);
cout << endl;
return 0;
}
```
这里提供了四种遍历方式:前序遍历、中序遍历、后序遍历和层次遍历。你可以根据需要选择适合的遍历方式。希望这个代码能够帮到你!