c - 去除叶子不会影响 BST - C

Question

我编写了一个函数来取消 BST 的所有叶子。BST当然有一个左右指针和一个叫做data的char来存储节点的值。

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 语句有效并打印了无效的节点，但结果树是相同的。我有类似的东西：

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

知道发生了什么吗？谢谢。

Answer 1

您正在按值传递 T，因此将 T 设置为 null 不会执行任何操作（T 只是指针的本地副本）。

您需要某种方式将 T 的“所有者”（即 parent->left 或 parent->right）设置为 null。

（另外，通过将 T 设置为 null，您会冒内存泄漏的风险 - 您需要 free() 吗？）

Answer 2

T=NULL;将 null 分配给本地指针，而不是树中的任何内容。您需要使用 astruct 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);
    }
  }  
}

Answer 3

你有你需要的零件。这主要是重新排序它们的问题。

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.RO 的回答很有趣。我更喜欢我的，但你可以两个都试一下，看看哪个适合。

顺便说一句，请确保您不需要free()在某处调用，以防止内存泄漏。