c - 从二叉树中删除

Question

我有一个二叉树的问题。在我的代码中，我计划实现添加、删除和打印等功能。虽然添加和打印工作正常，但我在删除时遇到了麻烦。我的想法 - 问题出在指针上。我通过 2 个指针添加并用 1 个指针删除，但我不知道如何让它工作。请帮忙。

#include <stdio.h>
#include <stdlib.h>

#include "bintree.h"

void paste_node(Tree ** tr, int x)
{
    Tree *tree_bin;
    if ((*tr) == NULL) {
        tree_bin = (Tree *) malloc(sizeof(Tree));
        tree_bin->item = x;
        tree_bin->lchild = tree_bin->rchild = NULL;
        *tr = tree_bin;
        return;
    }

    if (x < (*tr)->item) {
        paste_node(&((*tr)->lchild), x);
    } else {
        paste_node(&((*tr)->rchild), x);
    }
}

Tree * minimum(Tree *tr)
{
    if (tr->lchild == NULL) return tr;
    return minimum(tr->lchild);
}

void delete_node(Tree ** tr, int num)
{ 
    if (tr == NULL) return;

    if (num < tr->item)
        tr->lchild = delete_node(tr->lchild, num);
    else if (num > tr->item)
        tr->rchild = delete_node(tr->rchild, num);
    else {
        if (tr->lchild == NULL) {
            Tree *tree_bin = tr->rchild;
            free(tr);
            return;
        }
        else if (tr->rchild == NULL) {
            Tree *tree_bin = tr->lchild;
            free(tr);
            return;
        }

        Tree *tree_bin = minimum(tr->rchild);
        tr->item = tree_bin->item;
        tr->rchild = delete_node(tr->rchild, tree_bin->item);
    }

    return;
}

void print_tree(Tree *tr, int depth)
{
    if (tr != NULL) {
        print_tree(tr->lchild, depth + 1);
        for(int i = 0; i < depth; ++i) printf("   ");
        printf("%d<\n", tr->item);
        print_tree(tr->rchild, depth + 1);
    }
}

int check_node(Tree **tr, int x) {
    if ((*tr) == NULL) {
        return 1;
    }

    if (x < (*tr)->item) {
        check_node(&((*tr)->lchild), x);
    } else if (x == (*tr)->item) {
        return -1;
    } else {
        check_node(&((*tr)->rchild), x);
    }
}

Answer 1

您不能简单地删除二叉树的一个节点。您可以很容易地删除叶子，只需将父级的 lchild 或 rchild 伙伴设置为 null。但是你不能在不删除它的所有子节点的情况下删除一个内部节点。您可以做的是旋转节点，使左 child (或右 child )成为子树的根，而根成为子树。将新的子树根重新附加到树。重复直到最后要删除的节点变成叶子，然后将其删除。