Удалить элемент из отсортированного индексированного списка ADT, представленного как BST с отношением - PullRequest
Новая
       55

Удалить элемент из отсортированного индексированного списка ADT, представленного как BST с отношением

0 голосов
/ 25 мая 2020

Мне нужно реализовать отсортированный индексированный список ADT, представленный как BST с отношением. Проверяются следующие варианты: «<=» и «> =». У меня есть проблемы с функцией удаления. Он должен удалить элемент из данной позиции, но ничего не удаляет. 

Node *SortedIndexedList::remove_value(Node *root, TComp e) {
    if (root == NULL)
        return root;
    if (rel(e,root->info)) {
        root->left = remove_value(root->left, e);
        return root;
    }
    else if(rel(root->info,e)) {
        root->right = remove_value(root->right, e);
        return root;
    }
    if (root->left == NULL) {
        Node* temp = root->right;
        delete root;
        return temp;
    }
    else if (root->right == NULL) {
        Node* temp = root->left;
        delete root;
        return temp;
    }
    else {
        Node* succParent = root;
        Node *succ = root->right;
        while (succ->left != NULL) {
            succParent = succ;
            succ = succ->left;
        }
        if (succParent != root)
            succParent->left = succ->right;
        else
            succParent->right = succ->right;
        root->info = succ->info;
        delete succ;
        return root;
    }
}

TComp SortedIndexedList::remove(int i) {
    //TODO - Implementation
    if(sizze<=i ||i<0)
        throw invalid_argument("invalid");
    if (sizze == 1) {
        TComp tmp = head->info;
        head = nullptr;
        sizze--;
        return tmp;
    }
    ListIterator it = iterator();
    it.first();
    while (it.valid()) {
        if (it.pos == i) {
            Node *tmp = it.iter;
            TComp e=remove_value(head, it.getCurrent())->info;
            sizze--;
            return tmp->info;
        }
        it.next();
    }
    return NULL_TCOMP;
}

// методы, используемые из друга ListIterator class; pos и iter являются атрибутами класса 

void ListIterator::first(){
    //TODO - Implementation
    pos=0;
    iter = list.head;
    while(iter->left!=nullptr)
        iter=iter->left;
}
Node * getNextNode (Node *node){
    if (node->right != NULL){
        node = node->right;
        while( node->left != NULL){
            node = node->left;
        }
        return node;
    }
    while( node->parent != NULL){
        if (node->parent->left == node)
            return node->parent;
        node = node->parent;
    }
    return NULL;
}

void ListIterator::next(){
    pos++;
    iter=getNextNode(iter);

}

bool ListIterator::valid() const{
    return pos<list.sizze;
}

TComp ListIterator::getCurrent() const{
    if(!valid())
        throw invalid_argument("invalid");
    else
        return iter->info;
}
...