设计二叉排序树类(BSTree),实现插入结点、构造二叉排序树、输出查找路径、判断是否二叉排序树,4个成员函数。
时间: 2024-05-04 10:22:31 浏览: 24
下面是一个 C++ 实现的二叉排序树类(BSTree):
```cpp
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
class BSTree {
public:
BSTree(); // 构造函数
~BSTree(); // 析构函数
void insert(int value); // 插入结点
Node* build(int arr[], int n); // 构造二叉排序树
void printPath(int value); // 输出查找路径
bool isBST(); // 判断是否二叉排序树
private:
Node* root; // 根结点
void insert(Node*& p, int value);
void destroy(Node* p);
void printPath(Node* p, int value);
bool isBST(Node* p, int minVal, int maxVal);
};
BSTree::BSTree() : root(nullptr) {}
BSTree::~BSTree() {
destroy(root);
}
void BSTree::insert(int value) {
insert(root, value);
}
Node* BSTree::build(int arr[], int n) {
for (int i = 0; i < n; i++) {
insert(arr[i]);
}
return root;
}
void BSTree::printPath(int value) {
printPath(root, value);
}
bool BSTree::isBST() {
return isBST(root, INT_MIN, INT_MAX);
}
void BSTree::insert(Node*& p, int value) {
if (p == nullptr) {
p = new Node;
p->data = value;
p->left = p->right = nullptr;
} else if (value < p->data) {
insert(p->left, value);
} else if (value > p->data) {
insert(p->right, value);
}
}
void BSTree::destroy(Node* p) {
if (p != nullptr) {
destroy(p->left);
destroy(p->right);
delete p;
}
}
void BSTree::printPath(Node* p, int value) {
if (p == nullptr) {
return;
} else {
cout << p->data << " ";
if (value == p->data) {
cout << endl;
return;
} else if (value < p->data) {
printPath(p->left, value);
} else {
printPath(p->right, value);
}
}
}
bool BSTree::isBST(Node* p, int minVal, int maxVal) {
if (p == nullptr) {
return true;
} else if (p->data < minVal || p->data > maxVal) {
return false;
} else {
return isBST(p->left, minVal, p->data - 1) && isBST(p->right, p->data + 1, maxVal);
}
}
```
其中,`Node` 结构体表示二叉排序树的结点,包含一个整数和两个指向左右子树的指针。`BSTree` 类实现了插入结点、构造二叉排序树、输出查找路径、判断是否二叉排序树这 4 个成员函数。具体实现如下:
- `insert` 函数用于插入一个新结点,采用递归实现。
- `build` 函数用于构造二叉排序树,接收一个整数数组和数组长度作为参数,依次将数组中的元素插入到二叉排序树中。
- `printPath` 函数用于输出查找路径,接收一个整数作为参数,从根结点开始遍历二叉排序树,输出查找路径上的所有结点值。
- `isBST` 函数用于判断是否二叉排序树,采用递归实现。对于每个结点,判断其值是否在给定的最小值和最大值范围内,如果是,则递归判断左右子树是否也是二叉排序树。
需要注意的是,在 `insert` 函数和 `destroy` 函数中,左子树和右子树的指针都是指向指针的指针,这样才能在递归中改变它们的值。在 `printPath` 函数和 `isBST` 函数中,则直接使用指针即可。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)