建立一棵二叉树,从键盘接收先序遍历的输入,空节点用空格表示,以二叉链表作为存储结构,建立二叉树(以先序来建立),并采用递归算法对其进行遍历(中序),将遍历结果打印输出。给出完整代码
时间: 2023-06-26 16:08:57 浏览: 46
好的,以下是完整代码:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree() {
char c;
cin >> c;
if (c == ' ') {
return NULL;
}
TreeNode* root = new TreeNode(c);
root->left = buildTree();
root->right = buildTree();
return root;
}
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
cout << "请输入先序遍历序列(空节点用空格表示):" << endl;
TreeNode* root = buildTree();
cout << "中序遍历结果为:" << endl;
inorderTraversal(root);
cout << endl;
return 0;
}
```
输入格式如下:
```
请输入先序遍历序列(空节点用空格表示):
A B D E C F G
```
输出结果如下:
```
中序遍历结果为:
D B E A F C G
```