C++:编写一个程序,在自定义函数中完成下列功能并在主函数进行测试:(1)由树的先序遍历序列和中序遍历序列创建一棵二叉树。 (2)输出二叉树的后序遍历序列。 测试数据: 先序遍历序列: ABDGCEF 中序遍历序列:DGBAECF
时间: 2024-10-23 14:14:44 浏览: 15
在C++中,我们可以使用递归的方式来实现从先序遍历和中序遍历序列重建二叉树的功能。这里是一个简单的示例,我们将使用`TreeNode`作为节点类,并提供三个辅助函数`preorderToTree`, `inorderToTree`和`postorderTraversal`来分别处理先序、中序遍历和后序遍历:
```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* preorderToTree(string str, int& i) {
if (i == str.size()) return nullptr;
TreeNode* root = new TreeNode(str[i++]);
root->left = preorderToTree(str, i);
root->right = inorderToTree(str, i);
return root;
}
// 中序遍历转换成二叉树
TreeNode* inorderToTree(string str, int& i) {
if (str[i] == '\0') return nullptr;
int start = i;
while (str[i] != '\0' && str[i++] != ',')
;
TreeNode* node = new TreeNode(str[start--]);
node->left = inorderToTree(str, i);
node->right = inorderToTree(str, i);
return node;
}
// 后序遍历序列输出
void postorderTraversal(TreeNode* root, string& result) {
if (!root) return;
postorderTraversal(root->left, result);
postorderTraversal(root->right, result);
result += root->val;
}
int main() {
string preorder = "ABDGCEF";
string inorder = "DGBAECF";
int i = 0;
TreeNode* root = preorderToTree(preorder, i);
cout << "Building tree from given sequences:\n";
// 测试打印先序遍历
cout << "Preorder traversal: ";
printPreOrder(root);
cout << endl;
string postorderResult;
postorderTraversal(root, postorderResult);
cout << "Postorder traversal: " << postorderResult << endl;
return 0;
}
```
在这个例子中,我们首先通过先序遍历构建了根节点,然后找到中序遍历的开始位置,继续递归构建左右子树。最后,我们通过后序遍历的方式遍历整棵树并将其结果添加到字符串`result`中。
阅读全文