如何使用c++构造二叉树
时间: 2023-12-13 16:04:10 浏览: 33
构造二叉树的基本思路是使用递归,具体步骤如下:
1. 定义二叉树的节点结构体,包含节点值、左子树和右子树指针。
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
2. 定义一个函数,该函数输入一个数组,返回根节点指针。该函数内部使用递归构造左右子树。递归终止条件是数组为空,此时返回空指针。
```
TreeNode* buildTree(vector<int>& nums, int start, int end) {
if (start > end) {
return nullptr;
}
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildTree(nums, start, mid - 1);
root->right = buildTree(nums, mid + 1, end);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return buildTree(nums, 0, nums.size() - 1);
}
```
3. 在主函数中调用该函数,输入一个有序数组,即可构造出相应的二叉树。
```
int main() {
vector<int> nums = { -10, -3, 0, 5, 9 };
TreeNode* root = sortedArrayToBST(nums);
// do something with the root node
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)