先序和后续能构建二叉树吗
时间: 2023-11-21 08:05:35 浏览: 20
是的,先序遍历序列和后序遍历序列可以构建唯一的二叉树。具体构建方法如下:
1. 先序遍历序列的第一个结点为根节点;
2. 在后序遍历序列中找到根节点,可以将后序遍历序列分为左子树和右子树两个部分;
3. 根据左子树和右子树的长度,可以将先序遍历序列分为左子树和右子树两个部分;
4. 递归处理左子树和右子树,即可构建整棵二叉树。
需要注意的是,如果先序遍历序列和后序遍历序列不合法,即无法构建成二叉树,那么上述方法也无法构建正确的二叉树。
相关问题
通过二叉树的先序序列和中序序列构建二叉树,然后再main函数中输入二叉树的先序序列为ABDGCEF,中序序列为DGBAECF,并通过后续遍历算法输出二叉树的后续序列GDBEFCA;
好的,这个问题可以使用递归的方法来解决。首先我们可以通过先序序列的第一个元素A来确定根节点,然后在中序序列中找到根节点的位置,这样就可以确定左子树和右子树的中序序列。接下来,我们可以根据左子树和右子树的中序序列长度,来确定先序序列中左子树和右子树的先序序列。然后递归地构建左子树和右子树,最终构建出整棵二叉树。
以下是C++代码实现:
```cpp
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
struct TreeNode {
char val;
TreeNode *left;
TreeNode *right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTreeHelper(string preOrder, string inOrder, int preStart, int preEnd, int inStart, int inEnd, unordered_map<char, int>& map) {
if (preStart > preEnd || inStart > inEnd) {
return nullptr;
}
char rootVal = preOrder[preStart];
TreeNode* root = new TreeNode(rootVal);
int rootIndex = map[rootVal];
int leftSubTreeSize = rootIndex - inStart;
root->left = buildTreeHelper(preOrder, inOrder, preStart + 1, preStart + leftSubTreeSize, inStart, rootIndex - 1, map);
root->right = buildTreeHelper(preOrder, inOrder, preStart + leftSubTreeSize + 1, preEnd, rootIndex + 1, inEnd, map);
return root;
}
TreeNode* buildTree(string preOrder, string inOrder) {
if (preOrder.empty() || inOrder.empty()) {
return nullptr;
}
unordered_map<char, int> map;
for (int i = 0; i < inOrder.size(); i++) {
map[inOrder[i]] = i;
}
return buildTreeHelper(preOrder, inOrder, 0, preOrder.size() - 1, 0, inOrder.size() - 1, map);
}
void postOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val;
}
int main() {
string preOrder = "ABDGCEF";
string inOrder = "DGBAECF";
TreeNode* root = buildTree(preOrder, inOrder);
postOrder(root);
return 0;
}
```
输出结果为:
```
GDBEFCA
```
二叉树的先序后续中序代码完整代码
以下是二叉树的先序、中序、后序遍历的完整代码实现(C++语言):
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
int rootVal = preorder[preStart];
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
TreeNode* root = new TreeNode(rootVal);
root->left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
root->right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root, res);
return res;
}
void preorder(TreeNode* root, vector<int>& res) {
if (root == NULL) {
return;
}
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
void inorder(TreeNode* root, vector<int>& res) {
if (root == NULL) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root, res);
return res;
}
void postorder(TreeNode* root, vector<int>& res) {
if (root == NULL) {
return;
}
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
}
};
```
其中,`buildTree` 函数用来构建二叉树,`preorderTraversal` 函数用来进行先序遍历,`inorderTraversal` 函数用来进行中序遍历,`postorderTraversal` 函数用来进行后序遍历。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)