从C中的BST删除节点 [英] Delete node from BST in C

问题描述

我试图理解此在线创建的功能，用于从BST删除节点.有些事情我听不懂

i was trying to understand this function founded online for deleting a node from a BST. There are some things i can't understand

这是代码:

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)吗? (与紧随其后的两行代码相同)

shouldn't it be if(data < root->data) ? (same for the two lines of code right after)

2)函数返回指向节点的指针，这是否意味着在主函数中我必须执行类似的操作?

2) the function return a pointer to node,does that mean that in the main function i have to do something like this?

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

因此，该函数用不带val 24的节点将新树替换为新树吗?如果我希望函数的类型为void，我是否应该使用双指针?

So the function replace the old tree with a new tree without the node with the val 24?if i want the function to be of type void should i use double pointers?

推荐答案

对于第一个问题，您应该正确:if(data < root->data). 对于第二个问题，不完全是.您显然应该定义一个指针头，它是树的头，并创建一个将数据插入到bst的函数，因此该函数执行malloc.您在主程序中需要做的所有事情就是在开始时将头指针初始化为NULL，因此它应类似于:

For your first question you have right it should be: if(data < root->data). For the second question not exactly. You obviously should define a pointer head which is the head of the tree and create an function which inserts data to bst, so this function does the malloc. All you nead in your main is the head pointer initialized to NULL in the beginning so it should look like:

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

还请注意，新树不需要malloc，因为您的函数返回的指针已经显示给结构，而您要做的是new_tree也将指向该结构.

Also note that new tree doesn't need to have malloc since your function returns a pointer that already shows to a struct and what you do is that new_tree will also point this struct.

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

For your final question yes of course you could pass double pointer (in fact I followed this way in the definition of input_to_bst(&tree);).

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

An example of function input_to_bst definition could be:

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

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

where we suppose that we have defined the structs:

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

typedef struct tree* treeptr;

这篇关于从C中的BST删除节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！