从C二进制树中删除节点而不会弄乱它 [英] Delete node from a C binary tree without messing it up

问题描述

我是使用C二叉树库的初学者.我想知道如何在不弄乱整个事情的情况下从二叉树中删除节点.以下是我创建树的方法:

I am a beginner working on a C binary tree library.I am wondering on how could I delete a node from a binary tree without messing up the entire thing.Here is how I create the tree:

结构:

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链接到上节点(在leaf4之上).很难解释我如何尽力而为.

my question is basically how I could for example delete a left node,and then "link" the other nodes(or leaves) that were linked to that left node so the tree doesnt have a NULL leaf? Ex: if leaf 4 had 2 children(left3 and right8),then delete leaf 4, it link children left3 and right8 to the upper node(above leaf4).Its hard to explain im trying to do my best.

谢谢

推荐答案

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

The algorithm for deleting from a BST looks conceptually like this:

• 您使用其键搜索节点.

• You search for the node using its key.

找到节点后，检查其是否只有一个孩子.

Once you have found the node you check if it has only one child.

• 如果有，请删除该节点，然后将刚刚找到的子节点放在该节点上.
• 如果没有，则在右侧子树中使用最小值键搜索节点.找到它后，将您要删除的节点的键替换为此最小键，然后删除右侧子树中的最小节点.

您可以阅读整个概念的工作原理以及在C代码中的外观，例如此处.我的建议是首先看到此关系图，该图说明了所有可能的情况. 祝你好运！

How this whole concept works and how should it look in C code you can read for example here. My suggestion would be to first see this diagram, which illustrates all the possible scenarios. Good luck!

这篇关于从C二进制树中删除节点而不会弄乱它的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！