从BST中删除节点C

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。所有你在你的主要NEAD是头指针初始化为NULL在起步阶段，所以它应该是这样的：

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

还要注意的是新的树并不需要有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;