用C++写一个替罪羊树
时间: 2024-03-09 14:46:13 浏览: 32
好的,以下是用 C++ 实现替罪羊树的代码。替罪羊树是一种平衡二叉树,可以支持插入、删除、查找等操作,并且可以在插入或删除节点时自动平衡树的结构。
```C++
#include <iostream>
#include <algorithm>
using namespace std;
template <typename T>
struct TreeNode {
T val;
int size;
TreeNode<T> *left, *right, *parent;
TreeNode(T val = 0, TreeNode<T> *parent = nullptr, TreeNode<T> *left = nullptr, TreeNode<T> *right = nullptr, int size = 1) :
val(val), parent(parent), left(left), right(right), size(size) {}
};
// 计算节点的大小
template <typename T>
int getSize(TreeNode<T>* node) {
return node ? node->size : 0;
}
// 更新节点的大小
template <typename T>
void updateSize(TreeNode<T>* node) {
if (node) {
node->size = 1 + getSize(node->left) + getSize(node->right);
}
}
// 向左旋转
template <typename T>
void rotateLeft(TreeNode<T>* node) {
TreeNode<T>* temp = node->right;
if (temp) {
node->right = temp->left;
if (temp->left) {
temp->left->parent = node;
}
temp->parent = node->parent;
if (!node->parent) {
node->parent = temp;
} else if (node == node->parent->left) {
node->parent->left = temp;
} else {
node->parent->right = temp;
}
temp->left = node;
node->parent = temp;
updateSize(node);
updateSize(temp);
}
}
// 向右旋转
template <typename T>
void rotateRight(TreeNode<T>* node) {
TreeNode<T>* temp = node->left;
if (temp) {
node->left = temp->right;
if (temp->right) {
temp->right->parent = node;
}
temp->parent = node->parent;
if (!node->parent) {
node->parent = temp;
} else if (node == node->parent->right) {
node->parent->right = temp;
} else {
node->parent->left = temp;
}
temp->right = node;
node->parent = temp;
updateSize(node);
updateSize(temp);
}
}
// 插入节点
template <typename T>
TreeNode<T>* insert(TreeNode<T>* root, T val) {
if (!root) {
return new TreeNode<T>(val);
}
if (val < root->val) {
root->left = insert(root->left, val);
root->left->parent = root;
} else {
root->right = insert(root->right, val);
root->right->parent = root;
}
updateSize(root);
int lSize = getSize(root->left);
int rSize = getSize(root->right);
if (lSize > 2 * rSize || rSize > 2 * lSize) {
int size = lSize + rSize + 1;
TreeNode<T>* node = root;
TreeNode<T>* parent = nullptr;
while (node) {
if (2 * getSize(node->left) < size && 2 * getSize(node->right) < size) {
break;
}
parent = node;
if (getSize(node->left) > getSize(node->right)) {
node = node->left;
} else {
node = node->right;
}
}
if (!parent) {
root = node;
} else if (node == parent->left) {
parent->left = node;
} else {
parent->right = node;
}
node->parent = parent;
while (node != root) {
node = node->parent;
updateSize(node);
}
}
return root;
}
// 删除节点
template <typename T>
TreeNode<T>* remove(TreeNode<T>* root, T val) {
TreeNode<T>* node = root;
while (node && node->val != val) {
if (val < node->val) {
node = node->left;
} else {
node = node->right;
}
}
if (!node) {
return root;
}
if (node->left && node->right) {
TreeNode<T>* temp = node->right;
while (temp->left) {
temp = temp->left;
}
node->val = temp->val;
node = temp;
}
TreeNode<T>* parent = node->parent;
TreeNode<T>* child = node->left ? node->left : node->right;
if (child) {
child->parent = parent;
}
if (!parent) {
root = child;
} else if (node == parent->left) {
parent->left = child;
} else {
parent->right = child;
}
while (parent) {
updateSize(parent);
int lSize = getSize(parent->left);
int rSize = getSize(parent->right);
if (lSize > 2 * rSize || rSize > 2 * lSize) {
int size = lSize + rSize + 1;
node = parent;
parent = node->parent;
if (!parent) {
root = node;
} else if (node == parent->left) {
parent->left = node;
} else {
parent->right = node;
}
node->parent = parent;
while (node != root) {
node = node->parent;
updateSize(node);
}
break;
}
node = parent;
parent = node->parent;
}
delete node;
return root;
}
// 查找节点
template <typename T>
TreeNode<T>* find(TreeNode<T>* root, T val) {
TreeNode<T>* node = root;
while (node && node->val != val) {
if (val < node->val) {
node = node->left;
} else {
node = node->right;
}
}
return node;
}
// 中序遍历
template <typename T>
void inorder(TreeNode<T>* root) {
if (root) {
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
}
int main() {
TreeNode<int>* root = nullptr;
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 2);
root = insert(root, 4);
root = insert(root, 6);
root = insert(root, 8);
cout << "Inorder traversal of the constructed tree: ";
inorder(root);
cout << endl;
root = remove(root, 3);
root = remove(root, 6);
cout << "Inorder traversal after deletion of 3 and 6: ";
inorder(root);
cout << endl;
return 0;
}
```
在上面的代码中,我们使用了模板来支持不同类型的节点值。我们首先定义了一个 TreeNode 结构体,其中包含节点的值、大小、左子树、右子树和父节点等信息。然后我们实现了一些辅助函数,如 getSize、updateSize、rotateLeft 和 rotateRight 等函数,这些函数可以帮助我们更新节点的信息并且实现了左旋和右旋操作。
接下来,我们实现了 insert、remove 和 find 等操作。insert 操作用于插入节点,如果树的不平衡程度超过了阈值,我们就需要进行重构操作。remove 操作用于删除节点,如果删除节点后树的不平衡程度超过了阈值,我们也需要进行重构操作。find 操作用于查找节点,返回节点的指针。
最后,我们实现了一个简单的测试用例,插入一些节点并删除一些节点,最后输出中序遍历的结果。
希望这份代码可以帮助你更好地理解和实现替罪羊树。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)