用C++按照序列(20,16,5,27,30,20,67,60,7)中的9个元素的顺序构造一棵二叉排序树
时间: 2024-04-30 14:20:47 浏览: 11
首先,我们要明白二叉排序树的性质:对于任意节点,其左子树上的所有节点的值都小于该节点的值,其右子树上的所有节点的值都大于该节点的值。
根据这个性质,我们可以采用如下的方法构造二叉排序树:
1. 将第一个元素20作为根节点。
2. 依次将16、5、27、30、20、67、60、7插入树中。
3. 对于每个要插入的元素,从根节点开始,比较该元素与当前节点的值的大小关系,并根据大小关系选择往左子树或右子树插入。具体地,如果要插入的元素小于当前节点的值,则往左子树插入;否则往右子树插入。
4. 插入完所有元素后,得到的二叉排序树如下所示:
```
20
/ \
16 27
/ / \
5 30 67
\ /
7 60
```
这就是按照序列(20,16,5,27,30,20,67,60,7)中的9个元素的顺序构造的二叉排序树。
相关问题
用C++按照序列(20,16,5,27,30,20,67,60,7)中的9个元素的顺序构造一棵二叉排序树,写出代码
以下是用C++实现按照序列(20,16,5,27,30,20,67,60,7)中的9个元素的顺序构造一棵二叉排序树的代码:
```cpp
#include <iostream>
using namespace std;
// 二叉排序树结点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 插入二叉排序树结点的函数
void insert(TreeNode*& root, int val) {
if (root == NULL) {
root = new TreeNode(val);
return;
}
if (val < root->val) {
insert(root->left, val);
}
else if (val > root->val) {
insert(root->right, val);
}
}
// 中序遍历输出二叉排序树结点的函数
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
int arr[] = {20, 16, 5, 27, 30, 20, 67, 60, 7};
int n = sizeof(arr) / sizeof(arr[0]);
TreeNode* root = NULL;
for (int i = 0; i < n; i++) {
insert(root, arr[i]);
}
inorderTraversal(root);
return 0;
}
```
输出结果为:5 7 16 20 27 30 60 67 。
用C++语言,完成给定关键字序列为{16,5,17,29,11,3,15,20},按表中元素的顺序依次插入,建立相应的二叉排序树,给出其中序序列。
好的,下面是用 C++ 实现的代码:
```cpp
#include <iostream>
using namespace std;
// 二叉排序树的结构体
struct BSTNode {
int key;
BSTNode* left;
BSTNode* right;
};
// 向二叉排序树中插入结点
void insert(BSTNode*& root, int key) {
if (root == nullptr) { // 如果树为空,直接插入
root = new BSTNode{key, nullptr, nullptr};
return;
}
if (key < root->key) { // 如果插入的值小于当前结点的值,向左子树插入
insert(root->left, key);
} else { // 如果插入的值大于等于当前结点的值,向右子树插入
insert(root->right, key);
}
}
// 中序遍历二叉排序树
void inorder(BSTNode* root) {
if (root == nullptr) {
return;
}
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
int main() {
int keys[] = {16, 5, 17, 29, 11, 3, 15, 20};
int n = sizeof(keys) / sizeof(keys[0]);
BSTNode* root = nullptr;
for (int i = 0; i < n; i++) {
insert(root, keys[i]);
}
inorder(root);
cout << endl;
return 0;
}
```
输出结果为:
```
3 5 11 15 16 17 20 29
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)