c - 从 C 二叉树中删除节点而不弄乱它

Question

我是一名致力于 C 二叉树库的初学者。我想知道如何从二叉树中删除节点而不弄乱整个事物。以下是我创建树的方法:

结构:

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

typedef struct Node TNode;
typedef struct Node *binary_tree;

树的创建:

binary_tree NewBinaryTree(int value_root) {
    binary_tree newRoot = malloc(sizeof(TNode));
    if (newRoot) {
        newRoot->value = value_root;
        newRoot->left = NULL;
        newRoot->right = NULL;
    }
    return newRoot;
}

向其中添加元素:

void Insert(binary_tree *tree, int val) {
    if (*tree == NULL) {
        *tree = (binary_tree)malloc(sizeof(TNode));
        (*tree)->value = val;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
    } else {
        if (val < (*tree)->value) {
            Insert(&(*tree)->left, val);
        } else {
            Insert(&(*tree)->right, val);
        }
    }
}

我的问题基本上是如何删除左节点，然后“链接”链接到该左节点的其他节点(或叶子)，以便树没有 NULL 叶子？例如:如果叶子 4 有 2 个子节点(left3 和 right8)，则删除叶子 4，它将子节点 left3 和 right8 链接到上节点(叶子 4 之上)。很难解释我试图尽力而为。

谢谢

Answer 1

从 BST 中删除的算法在概念上看起来像这样:

• 您使用节点的键来搜索该节点。

• 找到节点后，检查它是否只有一个子节点。

  • 如果是，则删除该节点并将刚刚找到的子节点放在其位置上。
  • 如果没有，则在右子树中搜索具有最小值键的节点。找到它后，将要删除的节点的键替换为该最小键，然后删除右子树中的最小节点。

这整个概念是如何工作的以及它在 C 代码中应该是什么样子，您可以阅读例如 here 。我的建议是首先看到这个diagram ，它说明了所有可能的情况。祝你好运!