A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 霸宋号 初级黑马   /  2021-3-27 14:36  /  1428 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

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; //根节点
        };
}

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马