C++编写程序,输入先序和中序遍历,构建二叉树。
时间: 2024-03-24 13:37:18 浏览: 136
二叉树的先序、中序、后序、分层遍历C++实现
4星 · 用户满意度95%
好的,我可以为您解答这个问题。这个问题涉及到二叉树的构建和遍历,需要用到递归的思想。
首先,我们需要了解先序遍历和中序遍历的定义。先序遍历是指先访问根节点,然后访问左子树,最后访问右子树。中序遍历是指先访问左子树,然后访问根节点,最后访问右子树。在构建二叉树时,先序遍历和中序遍历都是必须的。
接下来,我们可以根据先序遍历和中序遍历的结果来构建二叉树。具体的步骤如下:
1. 首先,我们可以通过先序遍历得到根节点的值,然后在中序遍历中找到这个值的位置,以此来确定左子树和右子树的范围。
2. 然后,我们可以递归地构建左子树和右子树。具体的方法是,以左子树的范围为基础,从先序遍历中找到下一个根节点的值,然后在中序遍历中找到这个值的位置,以此来确定左子树和右子树的范围。然后,我们可以递归地构建左子树和右子树。
3. 最后,我们可以把左子树和右子树连接到根节点上,构建出完整的二叉树。
下面是一个使用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) {
if (preorder.empty() || inorder.empty()) return NULL;
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 len = rootIndex - inStart;
TreeNode* root = new TreeNode(rootVal);
root->left = build(preorder, preStart + 1, preStart + len, inorder, inStart, rootIndex - 1);
root->right = build(preorder, preStart + len + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}
};
```
这个程序使用了递归的方法,首先根据先序遍历和中序遍历的范围,构建出根节点,然后递归地构建左子树和右子树。
阅读全文