设计二叉排序树类(BSTree),实现插入结点、构造二叉排序树、输出查找路径、判断是否二叉排序树,4个成员函数。
时间: 2024-05-15 17:13:48 浏览: 49
以下是一个简单的实现:
```cpp
#include <iostream>
using namespace std;
class BSTree {
private:
struct Node {
int data;
Node* left;
Node* right;
Node(int data) : data(data), left(nullptr), right(nullptr) {}
};
Node* root;
void insert(Node*& node, int data) {
if (!node) {
node = new Node(data);
} else if (data < node->data) {
insert(node->left, data);
} else if (data > node->data) {
insert(node->right, data);
}
}
void printPath(Node* node, int data) {
if (!node) {
return;
} else if (data == node->data) {
cout << node->data << endl;
} else if (data < node->data) {
cout << node->data << " ";
printPath(node->left, data);
} else {
cout << node->data << " ";
printPath(node->right, data);
}
}
bool isBSTUtil(Node* node, int min, int max) {
if (!node) {
return true;
}
if (node->data < min || node->data > max) {
return false;
}
return (isBSTUtil(node->left, min, node->data - 1) &&
isBSTUtil(node->right, node->data + 1, max));
}
public:
BSTree() : root(nullptr) {}
void insert(int data) {
insert(root, data);
}
void printPath(int data) {
printPath(root, data);
}
bool isBST() {
return isBSTUtil(root, INT_MIN, INT_MAX);
}
void inorder() {
inorderUtil(root);
cout << endl;
}
void inorderUtil(Node* node) {
if (node) {
inorderUtil(node->left);
cout << node->data << " ";
inorderUtil(node->right);
}
}
};
```
这个类实现了一个二叉排序树,其中`Node`结构体表示树的节点,有`data`、`left`和`right`三个成员变量,分别代表节点的值、左子树和右子树。
`BSTree`类包含了四个成员函数:
- `insert(int data)`:插入一个新节点到二叉排序树中。
- `printPath(int data)`:输出查找值为`data`的节点的路径。
- `isBST()`:判断二叉树是否为二叉排序树。
- `inorder()`:按中序遍历输出整个二叉排序树。
其中,`insert`函数使用递归实现,如果当前节点为空则新建一个节点,否则根据比较结果递归插入左子树或右子树。
`printPath`函数也使用递归实现,如果当前节点为空则直接返回,如果当前节点的值等于`data`则直接输出,否则根据比较结果递归进入左子树或右子树,并输出当前节点的值。
`isBST`函数实现了一个工具函数`isBSTUtil`,用于递归判断当前节点是否符合二叉排序树的定义,即左子树的所有节点都小于当前节点,右子树的所有节点都大于当前节点。如果当前节点为空,则返回`true`。如果当前节点的值超出了指定的最小值和最大值范围,则返回`false`。否则递归判断左子树和右子树是否符合二叉排序树的定义。
`inorder`函数使用中序遍历输出整个二叉排序树。
以上是一个简单的二叉排序树实现,当然还有很多可以优化和改进的地方,比如增加删除节点的功能、实现平衡二叉排序树等。
阅读全文