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) 함수는 노드에 대한 포인터를 반환합니다.이 함수는 주 기능에서 이와 같은 작업을 수행해야합니까? 나는 이중 포인터를 사용한다 함수가 void 형이 될하려는 경우

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

그래서 함수는?를 발 (24)와 노드 않고 새 트리 오래 된 나무를 대체?

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 정의의 예는 수 :

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