c++用模板类实现二叉树
时间: 2024-09-27 10:08:08 浏览: 28
在 C++ 中,模板类可以用于实现二叉树,因为模板允许我们编写通用的算法,适用于任何数据类型。下面是一个简单的二叉搜索树(Binary Search Tree, BST)模板类的示例:
```cpp
template <typename T>
class TreeNode {
public:
T data;
TreeNode<T> *left;
TreeNode<T> *right;
// 构造函数
TreeNode(T val = T()) : data(val), left(nullptr), right(nullptr) {}
};
// 模板二叉搜索树类
template <typename T>
class BinaryTree {
private:
TreeNode<T> *root;
public:
BinaryTree() : root(nullptr) {}
// 插入节点
void insert(T value) {
if (!root)
root = new TreeNode(value);
else
insertNode(root, value);
}
// 递归插入节点
void insertNode(TreeNode<T> *&node, T value) {
if (value < node->data)
node->left = insertNode(node->left, value);
else if (value > node->data)
node->right = insertNode(node->right, value);
return;
}
// 删除节点(简化版本,未处理特殊情况)
void remove(T value) {
root = removeNode(root, value);
}
// 递归删除节点
TreeNode<T> *removeNode(TreeNode<T> *&node, T value) {
if (!node)
return nullptr;
if (value < node->data)
node->left = removeNode(node->left, value);
else if (value > node->data)
node->right = removeNode(node->right, value);
else { // 找到需要删除的节点
if (!node->left && !node->right) { // 叶子节点
delete node;
node = nullptr;
} else if (!node->left) { // 只有右子节点
TreeNode<T> *temp = node;
node = node->right;
delete temp;
} else if (!node->right) { // 只有左子节点
TreeNode<T> *temp = node;
node = node->left;
delete temp;
} else { // 有两个子节点
TreeNode<T> *temp = findMin(node->right); // 找到右子树最小值节点
node->data = temp->data; // 更新当前节点的数据
node->right = removeNode(node->right, temp->data); // 从右子树删除该节点
}
}
return node;
}
// 其他辅助方法...
};
```
这个例子展示了如何用模板类 `TreeNode` 实现二叉树节点,并提供基本的操作如插入和删除。注意这只是一个基础版本,实际应用中可能需要处理更多边界情况和错误。
阅读全文