C++ удалить узел из BST

У меня возникли проблемы с моей функцией удаления. Я не знаю, какая проблема. Пожалуйста, помогите мне исправить это. Большое спасибо.C++ удалить узел из BST

node* tree_minimum(node *x){ 

    while(x->left!=NULL){ 
     x=x->left; 
    } 
    return x; 
} 

node* tree_successor(node *x){ 

    if(x->right!=NULL) 
     return tree_minimum(x->right); 

    node *y; 
    y=new node; 
    y=x->parent; 

    while(y!=NULL&&x==y->right){ 
     x=y; 
     y=y->parent; 
    } 
    return y; 
} 

node* tree_search(node* x,int k){ 

    if(x==NULL||k==x->key) 
     return x; 

    if(k<x->key) 
     return tree_search(x->left,k); 
    else 
     return tree_search(x->right,k); 
} 

node* tree_delete(int b){ 

    node *y; 
    y=new node; 
    node *x; 
    x=new node; 
    node *z; 
    z=new node; 

    z=tree_search(root,b); 

    if(isempty()){ 
     cout<<"TREE is empty."; 
     return NULL; 
    } 

    if(z->left==NULL||z->right==NULL) 
     y=z; 
    else 
     y=tree_successor(z); 

    if(y->left!=NULL) 
     x=y->left; 
    else 
     x=y->right; 

    if(x!=NULL) 
     x->parent=y->parent; 
    if(y->parent==NULL) 
     root=x; 
    else{ 

    if(y=y->parent->left) 
     y->parent->left=x; 
    else 
     y->parent->right=x; 
    } 
    if(y!=z) 
     y->key=z->key; 

    return y; 
}

источник

2013-03-13 Alee Ciaral Policarpio

Что он должен делать ? Что это на самом деле? Что вы пытались исправить? –

есть. Я уже пытался это исправить. Я работаю над этим весь день. ну на самом деле просто нужно удалить узел из дерева. –

Все остальные функции прекрасны, за исключением tree_delete :(. –

К сожалению, у вас здесь много проблем; Я думаю, что вы непонятый выделение памяти:

node *y; 
y=new node; 
y=x->parent; // Holy Mackerel!

Выделяет память на второй линии возвращения адреса на вновь выделенной памяти; следующая строка меняет адрес y, указывающий на (!!) - потеря выделенного места памяти и создание утечки памяти. Поскольку они разбросаны по всему коду, и у вас нет main() или код, показывающий вызов, нет необходимости продолжать.

Если вы просто копируете указатели, вам не нужно выполнять динамическое распределение (т. Е. Оператор new).

int *x = new int; 
int y = 2; 
*x = 1; // Assigns the memory (int) pointed to by x to 1 
x = &y; // Reassigns x to point to y - but without delete the allocated memory's last reference is lost

Я действительно рекомендую вам взять книгу, прежде чем идти дальше.

EDIT: Кроме того, следить за условными, как:

if (y=y->parent->left)

, когда вы, скорее всего, имел в виду:

if (y == y->parent->left)

Логика нуждается конденсационные - проверить некоторые сообщения о BST на SO, как этот :

Binary Search Tree Implementation

источник

2013-03-13 13:22:23 assem

C++ удалить узел из BST

ответ

Смежные вопросы