用c++,以字符串的形式定义一棵二叉树:根左子树右子树例如: 可用 ABo Co o Do 进行定义。 首先根据二叉树的字符串定义建立一棵二叉链表树,然后按中序遍历这棵二叉树输出每个结点上的字母,最后按照后序遍历的释放这棵二叉树。
时间: 2024-01-23 11:04:55 浏览: 115
首先,我们需要定义二叉树的节点结构体:
```cpp
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
```
然后,我们可以使用递归的方式来构建二叉树:
```cpp
TreeNode* constructTree(string s, int& i) {
if (i >= s.size() || s[i] == 'o') { // 如果当前节点为空,则返回NULL
i++;
return NULL;
}
TreeNode* root = new TreeNode(s[i++]); // 创建当前节点
root->left = constructTree(s, i); // 递归构建左子树
root->right = constructTree(s, i); // 递归构建右子树
return root;
}
```
接下来,我们可以使用中序遍历输出每个节点的值:
```cpp
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
```
最后,我们可以使用后序遍历释放二叉树:
```cpp
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
delete root;
}
```
完整代码如下:
```cpp
#include <iostream>
#include <string>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* constructTree(string s, int& i) {
if (i >= s.size() || s[i] == 'o') {
i++;
return NULL;
}
TreeNode* root = new TreeNode(s[i++]);
root->left = constructTree(s, i);
root->right = constructTree(s, i);
return root;
}
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
delete root;
}
int main() {
string s = "ABCoDo";
int i = 0;
TreeNode* root = constructTree(s, i);
inorderTraversal(root);
cout << endl;
postorderTraversal(root);
return 0;
}
```
阅读全文