创建名为Traverse工程及同名C++SourceFile(C++源文件)。2)初始化一个数据元素为字符串类型的二叉树,并对其实现创建及先序、中序、后序三种遍历。
时间: 2023-12-10 17:39:48 浏览: 126
二叉树实现(C++)包括三种遍历方式
以下是 Traverse 工程的 C++ 源文件代码,其中包括二叉树的定义、创建和三种遍历函数的实现:
```cpp
#include <iostream>
#include <string>
using namespace std;
// 二叉树结点定义
struct TreeNode {
string data;
TreeNode* left;
TreeNode* right;
TreeNode(string val): data(val), left(nullptr), right(nullptr) {}
};
// 创建二叉树函数,返回根结点指针
TreeNode* createTree() {
string val;
cout << "请输入结点值,输入#表示空结点:" << endl;
cin >> val;
if (val == "#") {
return nullptr;
}
TreeNode* root = new TreeNode(val);
cout << "请输入 " << val << " 的左子结点:" << endl;
root->left = createTree();
cout << "请输入 " << val << " 的右子结点:" << endl;
root->right = createTree();
return root;
}
// 先序遍历函数
void preorder(TreeNode* root) {
if (root != nullptr) {
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
}
// 中序遍历函数
void inorder(TreeNode* root) {
if (root != nullptr) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
// 后序遍历函数
void postorder(TreeNode* root) {
if (root != nullptr) {
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
}
int main() {
TreeNode* root = createTree();
cout << "先序遍历结果为:";
preorder(root);
cout << endl;
cout << "中序遍历结果为:";
inorder(root);
cout << endl;
cout << "后序遍历结果为:";
postorder(root);
cout << endl;
return 0;
}
```
用户在运行程序时,会被提示输入每个结点的值,如果输入 "#" 表示该结点为空。程序会根据用户的输入,创建出一棵二叉树,并对其实现先序、中序和后序三种遍历,输出遍历结果。
阅读全文