通过c++设计二叉排序树类(BSTree),实现插入结点、构造二叉排序树、输出查找路径、判断是否二叉排序树,4个成员函数。
时间: 2024-05-07 14:21:58 浏览: 110
好的,下面是代码实现:
```cpp
#include <iostream>
using namespace std;
// 二叉排序树结点类
class BSTNode {
public:
int data;
BSTNode *left;
BSTNode *right;
BSTNode(int val) {
data = val;
left = right = NULL;
}
};
// 二叉排序树类
class BSTree {
private:
BSTNode *root;
// 辅助函数:插入结点
void insertNode(int val, BSTNode *&node) {
if (node == NULL) {
node = new BSTNode(val);
} else if (val < node->data) {
insertNode(val, node->left);
} else if (val > node->data) {
insertNode(val, node->right);
}
}
// 辅助函数:构造二叉排序树
void createBSTree(int arr[], int len) {
for (int i = 0; i < len; i++) {
insertNode(arr[i], root);
}
}
// 辅助函数:输出查找路径
bool searchPath(int val, BSTNode *node) {
if (node == NULL) {
return false;
} else if (val == node->data) {
cout << node->data << endl;
return true;
} else if (val < node->data) {
cout << node->data << " ";
return searchPath(val, node->left);
} else if (val > node->data) {
cout << node->data << " ";
return searchPath(val, node->right);
}
}
// 辅助函数:判断是否二叉排序树
bool isBSTree(BSTNode *node, int min_val, int max_val) {
if (node == NULL) {
return true;
}
if (node->data < min_val || node->data > max_val) {
return false;
}
return isBSTree(node->left, min_val, node->data - 1)
&& isBSTree(node->right, node->data + 1, max_val);
}
public:
BSTree() {
root = NULL;
}
// 插入结点
void insert(int val) {
insertNode(val, root);
}
// 构造二叉排序树
void create(int arr[], int len) {
createBSTree(arr, len);
}
// 输出查找路径
void search(int val) {
bool found = searchPath(val, root);
if (!found) {
cout << "Not found!" << endl;
}
}
// 判断是否二叉排序树
bool isBST() {
return isBSTree(root, INT_MIN, INT_MAX);
}
};
int main() {
int arr[] = { 50, 30, 70, 20, 40, 60, 80 };
int len = sizeof(arr) / sizeof(arr[0]);
BSTree bst;
bst.create(arr, len);
int val1 = 40;
bst.search(val1);
int val2 = 90;
bst.search(val2);
bool isBST = bst.isBST();
cout << "Is a binary search tree: " << isBST << endl;
return 0;
}
```
这里使用了递归实现插入结点、构造二叉排序树、输出查找路径、判断是否二叉排序树这四个成员函数。其中,构造二叉排序树函数接受一个整型数组和数组长度,通过循环调用插入结点函数来构造二叉排序树。输出查找路径函数会输出查找到的结点以及经过的路径,如果没找到则输出 "Not found!"。判断是否二叉排序树函数使用了限制最大值和最小值的方法来确保每个结点都符合二叉排序树的定义。
在主函数中,我们创建了一个整型数组并调用了 BSTree 类的成员函数来操作二叉排序树,最后输出是否是二叉排序树。
阅读全文