從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;