用c++代码实现二叉树的创建与遍历
时间: 2023-12-16 12:06:33 浏览: 29
二叉树的创建和遍历可以使用递归来实现,下面给出一份基于 C++ 的代码示例:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 创建二叉树
TreeNode* createTree() {
int val;
cin >> val;
if (val == -1) { // 如果输入 -1,表示该节点为空
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = createTree(); // 递归创建左子树
root->right = createTree(); // 递归创建右子树
return root;
}
// 前序遍历
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
int main() {
TreeNode* root = createTree();
cout << "前序遍历结果:" << endl;
preOrder(root);
cout << endl;
cout << "中序遍历结果:" << endl;
inOrder(root);
cout << endl;
cout << "后序遍历结果:" << endl;
postOrder(root);
cout << endl;
return 0;
}
```
示例输入:
```
1
2
-1
-1
3
4
-1
-1
5
-1
-1
```
示例输出:
```
前序遍历结果:
1 2 3 4 5
中序遍历结果:
2 1 4 3 5
后序遍历结果:
2 4 5 3 1
```
以上代码实现了二叉树的创建和前、中、后序遍历。在创建二叉树时,输入 -1 表示该节点为空,遍历时输出每个节点的值即可。