由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树,所以对二叉树做如下处理,将二叉树的空结点用·补齐,如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树,扩展二叉树的先序和后序序列能唯一确定其二叉树。 现给出扩展二叉树的先序序列,要求输出其中序和后序序列。输入:输入先序序列,其中空结点用.表示。输出:输出2行,分别为中序序列和后序序列。用C++
时间: 2023-04-06 14:03:42 浏览: 245
我可以回答这个问题。对于扩展二叉树的先序序列,我们可以通过递归的方式来构建其对应的二叉树,然后再通过中序遍历和后序遍历来输出中序序列和后序序列。具体实现可以参考以下代码:
#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* buildTree(string& preorder, int& index) {
if (index >= preorder.size() || preorder[index] == '.') {
index++;
return NULL;
}
TreeNode* root = new TreeNode(preorder[index++]);
root->left = buildTree(preorder, index);
root->right = buildTree(preorder, index);
return root;
}
void inorderTraversal(TreeNode* root, string& inorder) {
if (!root) return;
inorderTraversal(root->left, inorder);
inorder += root->val;
inorderTraversal(root->right, inorder);
}
void postorderTraversal(TreeNode* root, string& postorder) {
if (!root) return;
postorderTraversal(root->left, postorder);
postorderTraversal(root->right, postorder);
postorder += root->val;
}
int main() {
string preorder;
cin >> preorder;
int index = 0;
TreeNode* root = buildTree(preorder, index);
string inorder = "";
inorderTraversal(root, inorder);
string postorder = "";
postorderTraversal(root, postorder);
cout << inorder << endl;
cout << postorder << endl;
return 0;
}
阅读全文