c - 从 C 中的 BST 中删除节点

Question

我试图理解这个在线创建的函数，用于从 BST 中删除节点。有些事情我无法理解

这是代码:

struct Node* Delete(struct Node *root, int data) {
  if (root == NULL) {
     return NULL;
  }
  if (data > root->data) {  // data is in the left sub tree.
      root->left = Delete(root->left, data);
  } else if (data > root->data) { // data is in the right sub tree.
      root->right = Delete(root->right, data);
  } else {
     // case 1: no children
     if (root->left == NULL && root->right == NULL) {
        delete(root); // wipe out the memory, in C, use free function
        root = NULL;
     }
     // case 2: one child (right)
     else if (root->left == NULL) {
        struct Node *temp = root; // save current node as a backup
        root = root->right;
        delete temp;
     }
     // case 3: one child (left)
     else if (root->right == NULL) {
        struct Node *temp = root; // save current node as a backup
        root = root->left;
        delete temp;
     }
     // case 4: two children
     else {
        struct Node *temp = FindMin(root->right); // find minimal value of right sub tree
        root->data = temp->data; // duplicate the node
        root->right = Delete(root->right, temp->data); // delete the duplicate node
     }
  }
  return root; // parent node can update reference
}

问题:

1)为什么会这样

if (data > root->data) {  // data is in the left sub tree.
          root->left = Delete(root->left, data);

不应该是if(data < root->data)吗？ ？ (后面两行代码也一样)

2) 函数返回一个指向节点的指针，这是否意味着在主函数中我必须做这样的事情？

int main(){
struct Node *tree=malloc(sizeof(Node));
...
struct Node *new_tree=malloc(sizeof(Node));
new_tree= Delete(tree,24);

所以函数用没有节点的新树替换了旧树 val 24？如果我希望函数是 void 类型，我应该使用双指针吗？

Answer 1

对于你的第一个问题，你是对的，它应该是:if(data < root->data) .对于第二个问题不完全是。您显然应该定义一个指针头，它是树的头部，并创建一个将数据插入 bst 的函数，因此该函数执行 malloc。您在 main 中只需要在开始时将头指针初始化为 NULL，因此它应该如下所示:

int main(){
struct Node *tree=NULL;
int number=...; 
...
input_to_bst(&tree,number);
...
new_tree= Delete(tree,24);

另请注意，new tree 不需要 malloc，因为您的函数返回一个指针，该指针已显示为一个结构，而您所做的是 new_tree 也将指向该结构。

对于你的最后一个问题，是的，你当然可以传递双指针(事实上我在 input_to_bst(&tree); 的定义中遵循了这种方式)。

函数 input_to_bst 定义的示例可以是:

void input_to_bst(treeptr* head,int number){
  if((*head)==NULL){
       (*head)=(treeptr)malloc(sizeof(struct tree));
       (*head)->data=number;
       (*head)->left=NULL;
       (*head)->right=NULL;
  }
  else{
      if(((*head)->data)>number) input_to_bst(&((*head)->left),number);
      else (((*head)->data)<number) input_to_bst(&((*head)->right),number);
  }
}

我们假设我们已经定义了结构:

struct tree{
    int data;
    struct tree* right;
    struct tree* left;
};

typedef struct tree* treeptr;