只用中序遍历创建二叉树c++
时间: 2023-11-21 10:06:18 浏览: 69
可以使用中序遍历序列创建二叉树,具体步骤如下:
1. 定义二叉树结构体,包括左右子树指针和节点值。
2. 定义一个递归函数,输入参数为中序遍历序列和序列起始位置和结束位置的下标,输出为创建的二叉树的根节点指针。
3. 在递归函数中,首先判断起始位置是否大于结束位置,如果是则返回空指针。
4. 否则,取中间位置为根节点,创建一个新节点,并将中间位置的值赋给新节点。
5. 递归调用函数,传入左半部分序列和起始位置和中间位置的前一个位置作为参数,将返回值赋给新节点的左子树指针。
6. 递归调用函数,传入右半部分序列和中间位置的后一个位置和结束位置作为参数,将返回值赋给新节点的右子树指针。
7. 返回新节点的指针。
下面是使用C++实现的代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& inorder, int start, int end) {
if (start > end) {
return NULL;
}
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(inorder[mid]);
root->left = buildTree(inorder, start, mid - 1);
root->right = buildTree(inorder, mid + 1, end);
return root;
}
int main() {
vector<int> inorder = {1, 2, 3, 4, 5};
TreeNode* root = buildTree(inorder, 0, inorder.size() - 1);
return 0;
}
```