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行目のコードでも同じです）

2）関数はノードへのポインタを返します。これは主関数でこれを何かする必要があることを意味しますか？

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

ので機能は、私は関数はvoid型であるようにしたい場合、私は二重のポインタを使用する必要がありますか？valを24とノードなく、新しいツリーと古い木を置き換えますか？

Answer 1

あなたの最初の質問には、それが正しいとする必要があります：if(data < root->data)。 2番目の質問は正確ではありません。あなたは明らかに、ツリーの先頭であるポインタの頭を定義し、データを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定義の例は次のようになります。

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

typedef struct tree* treeptr; 

：我々は構造体を定義したと仮定し

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); 
    } 
}