C++实现完全二叉树
时间: 2023-11-14 09:11:38 浏览: 56
C++实现完全二叉树需要定义一个完全二叉树类,其中需要包含添加结点、查找结点、删除结点等功能。在实现过程中,可以使用数组的形式来存储完全二叉树,同时需要定义一个指针来指向完全二叉树的根节点。下面是一个完全二叉树类的示例代码:
```
template <typename T>
class CompleteBinaryTree {
public:
CompleteBinaryTree() {
size_ = 0;
root_ = nullptr;
}
void Add(T data) {
if (size_ == 0) {
root_ = new Node(data);
size_++;
return;
}
int index = size_ + 1;
Node* node = root_;
while (index > 1) {
if (index % 2 == 0) {
node = node->left;
} else {
node = node->right;
}
index /= 2;
}
if (size_ % 2 == 0) {
node->left = new Node(data);
} else {
node->right = new Node(data);
}
size_++;
}
bool Find(T data) {
Node* node = root_;
int index = size_;
while (index > 0) {
if (index % 2 == 0) {
node = node->left;
} else {
node = node->right;
}
index /= 2;
}
if (node == nullptr) {
return false;
}
return node->data == data;
}
void Delete(T data) {
if (root_ == nullptr) {
return;
}
if (root_->data == data) {
delete root_;
root_ = nullptr;
size_--;
return;
}
Node* parent = FindParent(data);
if (parent == nullptr) {
return;
}
Node* node = nullptr;
if (parent->left != nullptr && parent->left->data == data) {