0

我正在尝试创建倾斜堆类，但是从堆中删除元素时遇到问题。删除函数位于代码的末尾。逻辑似乎正确。找到元素并合并其子元素。有什么建议吗？

struct node{
    int key;
    node* left;
    node* right;
};

class skewHeap{
public:
    skewHeap(int k);
    ~skewHeap();
    skewHeap& operator=(const skewHeap&);
    node* merge(node* a,node* b);
    void remove(node* a,int k);
    void add(int k);
    void print(node*) const;
    node* getRoot();
private:
    node* root;
    void del(node* n){
        if(n == NULL) return;
        else{
        del(n->left);
        del(n->right);
        delete n;
        }
    }

    node* copy(node* n){
        if(n == NULL) return NULL;
        node* tmp = new node;
        tmp->key = n ->key;
        tmp->left = copy(n->left);
        tmp->right = copy(n->right);
                 return tmp;
    }


};

skewHeap::skewHeap(int k){
    root = new node;
    root->key = k;
    root->left = NULL;
    root->right = NULL;
}

skewHeap::~skewHeap(){
    del(root);
}

skewHeap& skewHeap::operator=(const skewHeap& n){
    if( this != &n){
        del(root);
        root = n.root;
        copy(root);
    }
    return *this;
}

node* skewHeap::merge(node* a,node* b){
    if(a == NULL) return b;
    if(b == NULL) return a;
    else {
        if(a->key > b->key){
            node* tmp = a;
            a = b;
            b = tmp;
        }
        node* tmp = a->right;
        a->right = a->left;
        a->left = merge(b,tmp);
    }
    return a;
}



void skewHeap::add(int k){
    node* p = new node;
    p->key = k;
    p->left = NULL;
    p->right = NULL;
    root = merge(root,p);
}

void skewHeap::print(node* n) const{
    if(n == NULL) return;
    else{
        print(n->left);
        cout<<n->key<<" ";
        print(n->right);
    }
}

node* skewHeap::getRoot(){
    return root;
}

void skewHeap::remove(node* n,int k){
    if( n == NULL) return;
    if(n->key == k)  {
        n = merge(n->left,n->right);
        return;
        }
    remove(n->left,k);
    remove(n->right,k);
}
4

1 回答 1

0

这很好用（你用这种方法跳过根目录）

node* skewHeap::remove(node* n,int k){
    if( n == NULL) return NULL;

    if(n->left && n->left->key == k)  {
         n->left = merge(n->left->left,n->left->right);
         return n;
    }
    if(n->right && n->right->key == k) {
        n->right = merge(n->right->left,n->right->right);

        return n;
        }
    remove(n->left,k);
    remove(n->right,k);
}
于 2014-01-30T18:36:03.407 回答