设计二叉排序树类(BSTree),实现插入结点、构造二叉排序树、输出查找路径、判断是否二叉排序树,4个成员函数。
时间: 2024-05-09 18:16:34 浏览: 46
下面是一个简单的二叉排序树类的实现,包括插入结点、构造二叉排序树、输出查找路径、判断是否二叉排序树四个成员函数:
```cpp
#include <iostream>
class BSTree {
private:
struct Node {
int val;
Node* left;
Node* right;
Node(int v): val(v), left(nullptr), right(nullptr) {}
};
Node* root;
void insert_helper(Node* node, int val) {
if (val < node->val) {
if (node->left) {
insert_helper(node->left, val);
} else {
node->left = new Node(val);
}
} else {
if (node->right) {
insert_helper(node->right, val);
} else {
node->right = new Node(val);
}
}
}
bool is_bst_helper(Node* node, int min_val, int max_val) {
if (!node) {
return true;
}
if (node->val < min_val || node->val > max_val) {
return false;
}
return is_bst_helper(node->left, min_val, node->val - 1) && is_bst_helper(node->right, node->val + 1, max_val);
}
bool find_helper(Node* node, int val) {
if (!node) {
return false;
}
if (node->val == val) {
std::cout << node->val << std::endl;
return true;
} else if (val < node->val) {
std::cout << node->val << "->";
return find_helper(node->left, val);
} else {
std::cout << node->val << "->";
return find_helper(node->right, val);
}
}
public:
BSTree(): root(nullptr) {}
void insert(int val) {
if (!root) {
root = new Node(val);
} else {
insert_helper(root, val);
}
}
void construct(int arr[], int n) {
for (int i = 0; i < n; ++i) {
insert(arr[i]);
}
}
bool is_bst() {
return is_bst_helper(root, INT_MIN, INT_MAX);
}
bool find(int val) {
return find_helper(root, val);
}
};
```
这个类有一个内部结构体 `Node`,表示二叉树的结点;一个指向根节点的指针 `root`;以及四个成员函数:`insert`、`construct`、`is_bst` 和 `find`。
其中,`insert` 函数用于将一个新的结点插入到二叉树中,如果根节点为空,则将新结点作为根节点;否则,从根节点开始,如果新结点的值小于当前结点,则继续遍历左子树;否则,继续遍历右子树。当遍历到一个叶子结点时,将新结点插入到该叶子结点的位置。
`construct` 函数用于构造二叉排序树,将一个数组中的元素依次插入到二叉树中。
`is_bst` 函数用于判断该二叉树是否是二叉排序树。从根节点开始,对于每个结点,判断它的值是否在最小值和最大值之间,并且它的左子树和右子树也都是二叉排序树。
`find` 函数用于查找一个值在二叉树中的路径,并返回是否找到了该值。从根节点开始,如果该值等于当前结点的值,则返回 true;否则,如果该值小于当前结点的值,则继续遍历左子树;如果该值大于当前结点的值,则继续遍历右子树。在每次遍历时,将当前结点的值输出到标准输出流中。
阅读全文