用链式结构表示二叉树的生成
时间: 2023-06-17 15:08:39 浏览: 57
在链式结构中,每个节点可以看作是一个包含三个部分的数据结构:左子树、右子树和节点值。因此,我们可以定义一个二叉树节点的结构体如下:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
其中,val 表示节点的值,left 和 right 分别指向节点的左子树和右子树。
通过递归的方式,可以根据一个数组构建一个二叉树。具体步骤如下:
1. 如果数组为空,则返回 NULL。
2. 找到数组的中间元素作为根节点的值。
3. 创建一个新的 TreeNode,将中间元素的值赋给它。
4. 递归地构建左子树,将左半部分数组作为参数传递给它。
5. 递归地构建右子树,将右半部分数组作为参数传递给它。
6. 将左子树和右子树分别挂在根节点的 left 和 right 上。
7. 返回根节点。
代码实现如下:
```
TreeNode* buildTree(vector<int>& nums, int start, int end) {
if (start > end) {
return NULL;
}
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);
}
```
其中,sortedArrayToBST 函数是主函数,它接受一个有序数组作为参数,返回一个构建好的二叉树的根节点。buildTree 函数是递归函数,用于构建二叉树的每个节点。它接受三个参数:nums 数组、start 和 end,表示当前要构建的子树在 nums 数组中的起始位置和结束位置。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)