удаление листьев не влияет на BST - C

Я написал функцию для обнуления всех листьев BST. Конечно, BST имеет левый и правый указатель и символ, называемый данными, для хранения значения узла.

void removeLeaves(struct Tree* T){
  if(T->left == NULL && T->right == NULL){
    printf("removing %c\n", T->data);
    T=NULL;
  }
  else{
    if(T->left!=NULL){
      removeLeaves(T->left);
    }
    if(T->right!=NULL){  
      removeLeaves(T->right);
    }
  }  
}

Я распечатываю дерево до и после вызова этой функции. И хотя приведенный выше оператор печати работает и печатает обнуленные узлы, результирующее дерево остается тем же. У меня есть что-то вроде:

print(BST);
removeLeaves(BST);
print(BST);

Есть идеи, что происходит? Спасибо.


c struct pointers binary-search-tree
person MinaHany    schedule 01.06.2012    source источник

Ответы (3)


arrow_upward
1
arrow_downward

T=NULL; присваивает значение null локальному указателю, а не чему-либо в вашем дереве. Вам нужно использовать struct Tree **, чтобы вы могли изменить struct Tree *:

void removeLeaves(struct Tree ** T){
  if((*T)->left == NULL && (*T)->right == NULL){
    printf("removing %c\n", (*T)->data);
    *T = NULL;
  }
  else{
    if((*T)->left!=NULL){
      pruneTree((*T)->left);
    }
    if((*T)->right!=NULL){  
      pruneTree((*T)->right);
    }
  }  
}
person Paul    schedule 01.06.2012
comment
Почему struct Tree ** T? Почему бы просто *T = NULL не работать? Я предполагаю, что когда у нас есть struct Tree* T, T будет указателем на дерево. Поэтому мы просто разыменовываем его и присваиваем ему значение null. - person Farid Nouri Neshat; 01.06.2012
comment
Спасибо за ответ! Я получаю сообщение об ошибке: передача аргумента 1 «removeLeaves» из несовместимого типа указателя в removeLeaves((*T)-›left); - person MinaHany; 01.06.2012
comment
@MinaHany Теперь вам нужно передать указатель на этот элемент: removeLeaves(&(*T)-›left); - person Paul; 01.06.2012

arrow_upward
1
arrow_downward

Вы передаете T по значению, поэтому установка T в null ничего не делает (T - это просто локальная копия указателя).

Вам нужен какой-то способ установить для «владельца» T (т.е. parent->left или parent->right) значение null.

(Кроме того, установив для T значение null, вы рискуете утечкой памяти — вам нужно использовать free()?)

person John3136    schedule 01.06.2012
comment
Я знал, что у меня где-то проблемы с указателями! Большое спасибо :) Да, мне нужно освободить, но я просто пока не буду этого делать. - person MinaHany; 01.06.2012

arrow_upward
0
arrow_downward

У вас есть нужные запчасти. В основном это вопрос их переупорядочения.

void removeLeaves(struct Tree* const T){
  if(T->left!=NULL){
    removeLeaves(T->left);
    T->left = NULL;
  }
  if(T->right!=NULL){  
    removeLeaves(T->right);
    T->right = NULL;
  }
}

Однако обратите внимание на const. Ваш код может работать и без него, но не должен, потому что установка T = NULL на самом деле ничего не делает, хотя можно подумать, что так и будет.

Обновление: ответ @PaulP.R.O., кстати, интересен. Я предпочитаю свой, но вы можете попробовать оба и посмотреть, какой подходит.

Кстати, убедитесь, что вам не нужен вызов free() где-то там, чтобы предотвратить утечку памяти.

person thb    schedule 01.06.2012
comment
на самом деле это удалит все листья, и в конце останется только корневой узел :) Да, мне нужно использовать free(), но я пока его опускаю. - person MinaHany; 01.06.2012
comment
Я неправильно понял. Я думал, что вы хотите, чтобы остался только корневой узел. Спасибо за обновления. - person thb; 01.06.2012
comment
Я прочитал свой вопрос и понял, почему вы его не поняли. Мой плохой, это очень вводит в заблуждение. - person MinaHany; 01.06.2012