能否提供C++中实现基本树数据结构(如二叉搜索树或AVL树)常用操作(插入、删除、查找)的示例代码?
时间: 2024-12-25 09:34:49 浏览: 9
当然可以,这里我会简要地给出C++中二叉搜索树(Binary Search Tree,BST)的基本操作——插入、删除和查找的示例代码。假设我们有一个简单的二叉搜索树节点定义:
```cpp
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
### 插入(Insertion)
```cpp
TreeNode* insert(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val) root->left = insert(root->left, val);
else root->right = insert(root->right, val);
return root;
}
```
### 查找(Search)
```cpp
TreeNode* search(TreeNode* root, int val) {
if (!root || root->val == val) return root;
if (root->val > val) return search(root->left, val);
return search(root->right, val);
}
```
### 删除(Deletion)
删除操作会更复杂一些,因为需要考虑多种情况,包括删除的节点无子节点、有单个子节点以及有两个子节点的情况。这里仅给出删除节点的基本思路:
```cpp
TreeNode* remove(TreeNode* &root, int key) {
if (!root) return root;
// 分别处理左子树、右子树和键值相等的情况
if (key < root->val)
root->left = remove(root->left, key);
else if (key > root->val)
root->right = remove(root->right, key);
// 找到并删除键值相等的节点
else {
if (!root->left && !root->right) { // 无子节点
delete root;
root = nullptr;
} else if (!root->left) { // 只有右子树
TreeNode *temp = root;
root = root->right;
delete temp;
} else if (!root->right) { // 只有左子树
TreeNode *temp = root;
root = root->left;
delete temp;
} else { // 有两个子节点,找到最右边的左子节点(最小值的父节点)
TreeNode *temp = findMin(root->right);
root->val = temp->val;
root->right = remove(root->right, temp->val); // 删除临时节点
}
}
return root;
}
// 辅助函数,找到最左边的节点(最大值)
TreeNode* findMin(TreeNode* node) {
while (node->left) {
node = node->left;
}
return node;
}
```
这只是一个基础版本,实际应用中可能还需要考虑更复杂的边界条件和错误处理。
阅读全文