从C中的BST删除节点-Java 学习之路

我试图理解这个在线创建的功能，用于删除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）函数返回指向节点的指针，这是否意味着在main函数中我必须做这样的事情？

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

所以函数用一个没有带有val 24的节点的新树替换旧树？如果我想函数是void类型我应该使用双指针吗？

1 回答

2
对于你的第一个问题，你应该是： if(data < root->data) . 对于第二个问题并不完全正确 . 你显然应该定义一个指针头，它是树的头部，并创建一个向bst插入数据的函数，所以这个函数执行malloc . 你在main中的所有内容都是在开头初始化为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;
```
回复于 2024-04-29T06:09:02+08:00

从C中的BST删除节点

1 回答

相关问题