建立一颗用二叉链表方式存储的二叉树,并实现对其进行先序,中序,后序,三种方法遍历,输出遍历结果
时间: 2023-06-14 11:02:29 浏览: 284
好的,我可以帮你实现这个任务。
首先,我们需要定义二叉树的节点结构体:
```c++
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};
```
然后,我们可以使用递归方式来构建二叉树。假设我们已经读入了二叉树的先序遍历序列(其中空节点用字符 `#` 表示),可以按照如下方式构建二叉树:
```c++
TreeNode* buildTree(string& preorder, int& i) {
if (i >= preorder.size() || preorder[i] == '#') {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[i]);
root->left = buildTree(preorder, ++i);
root->right = buildTree(preorder, ++i);
return root;
}
```
其中,`i` 表示当前遍历到的字符的下标。我们可以将 `i` 设为引用类型,这样可以在递归过程中不断更新 `i` 的值。
接下来,我们就可以实现二叉树的三种遍历方式了。以先序遍历为例:
```c++
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
```
中序遍历和后序遍历的实现类似,这里不再赘述。完整代码如下:
```c++
#include <iostream>
#include <string>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(string& preorder, int& i) {
if (i >= preorder.size() || preorder[i] == '#') {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[i]);
root->left = buildTree(preorder, ++i);
root->right = buildTree(preorder, ++i);
return root;
}
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
int main() {
string preorder = "ABD##E##CF###";
int i = 0;
TreeNode* root = buildTree(preorder, i);
cout << "Preorder traversal: ";
preorderTraversal(root);
cout << endl;
cout << "Inorder traversal: ";
inorderTraversal(root);
cout << endl;
cout << "Postorder traversal: ";
postorderTraversal(root);
cout << endl;
return 0;
}
```
输出结果为:
```
Preorder traversal: A B D E C F
Inorder traversal: D B E A C F
Postorder traversal: D E B F C A
```