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);
        }
    }
}

我写的删除子树右节点的函数是这样的:

void delrightsubtree(binary_tree *tree){


        if( (*tree)->value!=NULL )

        {
                free(&(*tree)->right);
                delrightsubtree( &(*tree)->right);
        }
        else
        {
            printf("end");
        }
    }

但是这个函数似乎不起作用，因为当我调用这个函数时它崩溃了(在向树添加多个元素之后)。我真的不知道该怎么做。

谢谢!

Answer 1

您可能想要实现递归删除方法(就像插入方法一样)。现在看起来您正在单个节点上调用free，这不会释放它附加的任何资源(即它的子节点)。相反，请考虑遍历要删除的树部分并将适当的值设置为 NULL。