根据输入序列10,6,1,4,5,11,12,13, 8, 9,用c++构造一棵平衡二叉树,要求写出构建过程。
时间: 2024-05-07 08:19:45 浏览: 10
构建平衡二叉树的过程可以采用递归的方式实现。具体步骤如下:
1. 将序列排序,找到中间结点作为根节点。
2. 将左边的序列递归构建成左子树,右边的序列递归构建成右子树。
下面是C++代码实现:
```c++
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//定义二叉树节点
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
//构建平衡二叉树
TreeNode* buildTree(vector<int>& nums, int left, int right){
if(left > right) return NULL; //边界条件
//找到中间结点作为根节点
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
//递归构建左子树和右子树
root->left = buildTree(nums, left, mid - 1);
root->right = buildTree(nums, mid + 1, right);
return root;
}
int main(){
vector<int> nums = {10,6,1,4,5,11,12,13,8,9};
sort(nums.begin(), nums.end()); //排序
TreeNode* root = buildTree(nums, 0, nums.size() - 1); //构建平衡二叉树
return 0;
}
```