请按照字符型设计一个二叉搜索树的数据结构,并为其编写C++类定义,包括查找深度,输出叶子结点和按照值查找的功能。已知数据节点类型为字符,待你完成其余类型的扩展以及调试和查找操作的实现。
时间: 2024-11-09 07:27:19 浏览: 43
在C++中,我们可以创建一个名为`CharacterBST`的类来表示二叉搜索树,用于存储字符类型的数据。这里是一个基本的实现,包含了插入、查找、获取深度、输出叶子节点等核心功能:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点
class Node {
public:
char data;
Node* left;
Node* right;
// 构造函数
Node(char value) : data(value), left(nullptr), right(nullptr) {}
};
class CharacterBST {
private:
Node* root;
// 查找函数,返回值是否存在,返回指针位置
Node* search(Node* node, char key) {
if (node == nullptr || node->data == key)
return node;
if (node->data < key)
return search(node->right, key);
else
return search(node->left, key);
}
// 插入函数
void insert(Node** node, char key) {
if (*node == nullptr)
*node = new Node(key);
else if (key < (*node)->data)
insert(&(*node)->left, key);
else
insert(&(*node)->right, key);
}
public:
// 构造函数
CharacterBST() : root(nullptr) {}
// 深度计算
int depth() const {
return calculate_depth(root);
}
// 私有辅助函数,递归计算深度
int calculate_depth(Node* node) const {
if (node == nullptr)
return 0;
else
return 1 + max(calculate_depth(node->left), calculate_depth(node->right));
}
// 输出所有叶子节点
void printLeaves() {
cout << "Leaf nodes:\n";
inOrderPrintLeaves(root);
}
// 私有辅助函数,中序遍历打印叶子节点
void inOrderPrintLeaves(Node* node) const {
if (node != nullptr && node->left == nullptr && node->right == nullptr)
cout << node->data << " ";
if (node->left != nullptr)
inOrderPrintLeaves(node->left);
if (node->right != nullptr)
inOrderPrintLeaves(node->right);
}
// 根据值查找节点
bool findNode(char key) {
Node* foundNode = search(root, key);
return foundNode != nullptr;
}
};
int main() {
CharacterBST bst;
bst.insert(&bst.root, 'a');
bst.insert(&bst.root, 'c');
bst.insert(&bst.root, 'b');
bst.insert(&bst.root, 'd');
cout << "Depth of the tree: " << bst.depth() << endl;
bst.printLeaves();
char searchKey = 'b';
if (bst.findNode(searchKey))
cout << "\nFound node with key " << searchKey << ": " << bst.search(&bst.root, searchKey)->data << endl;
else
cout << "\nNode not found.\n";
return 0;
}
```
这个`CharacterBST`类可以处理单个字符类型的输入。为了扩展到其他数据类型,只需将`Node`类的`data`成员和比较逻辑相应地修改即可。请注意,这只是一个基础示例,实际使用时还需要考虑错误处理和内存管理。
阅读全文