c - 删除函数二叉搜索树 BST，其父传递树指针作为参数

问题描述

我很难理解我的书想要我学习什么。我目前正在重新审视我多年前学习的一些算法和数据结构材料。其中一章是关于二叉搜索树及其应用等。这本书讨论了 BST（二叉搜索树）作为具有以下特性的节点的树：int data, node left, node right, node parent. 我明白这一点，我已经实现了搜索功能。

现在问题来了：当我拥有的参数是时，如何创建删除函数N* delete(Tree* tree, N* delete_node);？

有很多递归函数，但它们依赖于我们递归传递节点指针和键值这一事实。这不是本书中的练习所要寻找的。我尝试过并有效的一个方法示例是：C Program for Insertion and Deletion in Binary Search Tree 的源代码。未能满足这些标准的另外两个重要来源是codezclub和geeksforgeeks。他们解决了“删除”功能，但他们的功能在他们的功能中有其他参数。我的书指定

一个修改操作，给定一个指向 BST 树中元素的指针 delete_node，从 BST 树中删除 delete_node 并返回其指针。

函数声明：N* delete(Tree* tree, N* delete_node);

有人有什么想法吗？上面的源代码中还给出了最小可重复的示例，其中结构缺少“父”节点。以下是我对树和节点的定义：

typedef struct N {
    int data;
    struct N* left;
    struct N* right;
    struct N* parent;
} N;

typedef struct Tree {
    N* root;
} Tree;

标签： cbinary-search-tree

您可以使用CLRS作为了解Binary search tree数据结构和操作的参考。让我们先执行delete程序，然后解释必要的部分。
我们需要2程序，SUCCESSOR而transplant不是程序delete本身来完成它。要求的程序在执行之前delete。

为了在二叉搜索树中移动子树，我们定义了一个子程序移植，它将一个子树作为其父级的子树替换为另一棵子树。当移植用以节点 v 为根的子树替换以节点 u 为根的子树时，节点 u 的父节点成为节点 v 的父节点，并且 u 的父节点最终将 v 作为其适当的子节点。

void transplant(Tree** root, Tree* u, Tree* v) {
    if(u == NULL)
        return;
    else if(u->parent == NULL)
        *root = v;
    else if(u->parent->left == u)
        u->parent->left = v;
    else
        u->parent->right = v;
    if(v != NULL)
        v->parent = u->parent;
}

如果存在，我们需要实现Tree* SUCCESSOR(Tree* T)返回大于的下一个较大元素的node位置的过程。否则，返回。我们需要什么时候有 2 个孩子。它将被替换为.node->keyT->keyNULLSUCCESSORdelete_nodeSUCCESSOR(delete_node)

Tree* SUCCESSOR(Tree* T) {
    if(T == NULL)
        return T; // Since T==NULL, it's equivalent to return NULL
    else if(T->left != NULL) {
        while(T->left != NULL)
            T=T->left;
        return T;
    }
    else {
        while(T->parent != NULL && T->parent->right == T)
            T = T->parent;
        return T->parent;
    }
}

我们都可以执行所需的delete程序。

Tree* delete(Tree* root, Tree* delete_node) {
    if(delete_node == NULL)
        return root;
    
    if(delete_node->left== NULL)
        transplant(&root, delete_node, delete_node->right);

    else if(delete_node->right == NULL)
        transplant(&root, delete_node, delete_node->left);

    else {
        Tree* succ = SUCCESSOR(delete_node);
        if(delete_node->right != succ) {
            transplant(&root, succ , succ ->right);
            succ->right = delete_node->right;
            succ->right->parent = succ;
        }
        transplant(&root, delete_node, succ);
        succ->left = delete_node->left;
        succ->left->parent = succ;
    }
    return root;
}

以下是delete程序的工作原理：

delete_node从二叉搜索树中删除给定节点的过程root将指向root和的指针作为参数delete_node。它的案例组织方式与上述三个略有不同。

如果delete_node没有左孩子（第一个if语句做这部分），那么我们用delete_node它的右孩子替换，它可能是也可能不是NULL。当delete_node' 的右孩子为 NULL 时，这种情况处理delete_node没有孩子的情况。当delete_node' 的右孩子为非 NULL 时，这种情况处理delete_node只有一个孩子的情况，即它的右孩子。

如果delete_node只有一个孩子，也就是它的左孩子（else if部分处理这种情况），那么我们用delete_node它的左孩子替换。

否则，delete_node有一个左孩子和一个右孩子。我们找到delete_node' 的后继者succ，它位于delete_node' 的右子树并且没有左子树（如果它有左子树，那么它不是大于的最小数delete_node->key。我们得到矛盾）。我们想要拼接succ出它的当前位置并让它delete_node在树中替换。

如果succ是delete_node的右孩子，那么我们替换delete_node为succ。

否则，succ位于delete_node的右子树内但不是的右子树delete_node。在这种情况下，我们首先替换succ为它自己的右孩子，然后我们替换delete_node为succ。

由于这两个引用都来自CLRS，因此我鼓励您查看它，以防在理解它的工作原理时遇到问题。

c - 删除函数二叉搜索树 BST，其父传递树指针作为参数

问题描述

解决方案

推荐阅读