用C++语言,完成给定关键字序列为{16,5,17,29,11,3,15,20},按表中元素的顺序依次插入,建立相应的二叉排序树,给出其中序序列。
时间: 2023-08-17 22:04:03 浏览: 114
好的,下面是用 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
```
阅读全文