namespace MyHeap
{
template<class Type>class Heap//堆（创建大根堆）
{
private://节点类
template<class Type>class Node
{
public:
Type data;
void setData(const Type new_data)noexcept { data = new_data; }
Node<Type> * left; //左节点
Node<Type> * right; //右节点
Node<Type> * parent;//父节点
Node(Type newData, Node<Type> * _left = nullptr, Node<Type> * _right = nullptr, Node<Type> * _parent = nullptr)
:data(newData), left(_left), right(_right), parent(_parent) {};
~Node() { left = right = parent = nullptr; data = Type(); };
};
public:
Heap() :root(nullptr) {};
Heap(const Heap<Type> & heap) = delete;
Heap<Type> operator=(const Heap<Type> & heap) = delete;
virtual ~Heap()
{
clear(root);
}
void test()
{
if (root->right->left->right == nullptr)
{
cout << "当前为空";
}
else
{
cout << "当前不为空:"<< root->right->left->right->data;
}
}
virtual bool empty()const noexcept
{
return (root == nullptr);
}
virtual void insert(const Type & insert_value)noexcept//添加元素
{
if (empty())
{
root = new Node<Type>(insert_value);
}
else
{
if (!search(insert_value))//重复插入无效
{
queue<Node<Type>*>Queue;//创建队列
Queue.push(root);//将根节点添加到队列中
while (!Queue.empty())
{
Node<Type> * first = Queue.front();//获取队列第一个节点
//处理左边
if (first->left == nullptr)//非空判断
{
first->left = new Node<Type>(insert_value, nullptr, nullptr, first);
while (first != nullptr)
{
if (first->data < first->left->data)//大小判断,需要交换2个节点的值
{
swap(first, first->left);//还需要判断交换后的值左右节点是否比父节点小
}
else if (first->right != nullptr && first->data < first->right->data)
{
swap(first, first->right);
}
else
{
break;
}
first = first->parent;
}
break;
}
else
{
Queue.push(first->left);
}
//处理右边
if (first->right == nullptr)//非空判断
{
first->right = new Node<Type>(insert_value, nullptr, nullptr, first);
while (first != nullptr)
{
if (first->data < first->right->data)//大小判断,需要交换2个节点的值
{
swap(first, first->right);
}
else if (first->data < first->left->data)
{
swap(first, first->left);
}
else
{
break;
}
first = first->parent;
}
break;
}
else
{
Queue.push(first->right);
}
Queue.pop();//弹出顶端元素
}
}
}
}
virtual int size()const noexcept
{
return size(root);
}
void preorder()
{
preorder(root);
cout << endl;
}
virtual void print_tree()const noexcept
{
cout << endl;
queue<Node<Type>*>Queue;
Queue.push(root);
auto Power = [](int value, int power)
{
if (power == 0)
{
return 1;
}
int sum = 1;
for (int index = 0; index < power; sum = sum * value, index++);
return sum;
};
int count = 0, result = 0, add = 0;
while (!Queue.empty())
{
Node<Type> * first = Queue.front();
cout << first->data << " ";
if (++count == result + Power(2, add))
{
result = result + Power(2, add++);
cout << endl;
}
if (first->left != nullptr)
{
Queue.push(first->left);
}
if (first->right != nullptr)
{
Queue.push(first->right);
}
Queue.pop();
}
cout << endl;
}
virtual int height()const noexcept//获取高度
{
return height(root);
}
virtual bool search(const Type search_value)const noexcept
{
return search(search_value, root);
}
virtual bool remove(const Type remove_value)//删除节点总是报错
{
return remove(root, remove_value);
}
virtual bool remove()
{
if (empty())
{
return false;
}
queue<Node<Type>*>Queue;
Queue.push(root);
int count = 1;
while (!Queue.empty())
{
Node<Type> * first = Queue.front();
if (first->left != nullptr)
{
if (++count == size())
{
delete first->left;
first->left = nullptr;
return true;
}
Queue.push(first->left);
}
if (first->right != nullptr)
{
if (++count == size())
{
delete first->right;
first->right = nullptr;
return true;
}
Queue.push(first->right);
}
Queue.pop();
}
return false;
}
virtual void clear()
{
clear(root);
}
protected:
bool remove(Node<Type> * start_node, const Type remove_value)
{
if (empty() || start_node == nullptr || !search(remove_value))
{
return false;
}
if (start_node->data == remove_value)
{
while (start_node->left != nullptr || start_node->right != nullptr)//将目标节点往下移动
{
if (start_node->right != nullptr && start_node->left->data > start_node->right->data)
{
swap(start_node->left, start_node);
start_node = start_node->left;
}
else
{
swap(start_node->right, start_node);
start_node = start_node->right;
}
}
delete start_node;
start_node = nullptr;
return true;
}
return remove(start_node->left, remove_value) || remove(start_node->right, remove_value);
}
void preorder(Node<Type> * _Root)
{
if (_Root == nullptr)
{
return;
}
cout << _Root->data << " ";
preorder(_Root->left);
preorder(_Root->right);
}
bool search(const Type search_value, Node<Type> * start_node)const noexcept
{
if (start_node == nullptr || empty())
{
return false;
}
if (search_value == start_node->data)
{
return true;
}
return search(search_value, start_node->left) || search(search_value, start_node->right);
}
int height(Node<Type> * Root)const noexcept
{
if (Root == nullptr)
{
return 0;
}
int _left = height(Root->left) + 1, _right = height(Root->right) + 1;
return _left > _right ? _left : _right;
}
int size(Node<Type> * Root)const noexcept
{
if (Root == nullptr)
{
return 0;
}
return size(Root->left) + size(Root->right) + 1;
}
void swap(Node<Type> * left, Node<Type> * right)noexcept//只交换2个节点的值
{
if (left == nullptr || right == nullptr)
{
return;
}
Type temp = left->data;
left->setData(right->data);
right->setData(temp);
}
void clear(Node<Type> *& node)//需要加引用
{
while (node != nullptr)
{
clear(node->left);
clear(node->right);
delete node;
node = nullptr;
}
//root = nullptr;//或者加上这一句
}
private:
Node<Type> * root; //根节点
};
} |
|
收藏
淘帖
踩
