如何实现二进制搜索树的函数删除而不在C中递归？

Question

我尝试实现删除方法，但这对我不起作用。 I want to delete all nodes in the tree.函数有树型“结构树”作为参数，所以我不能使用递归;我想用循环来做。

那是我的结构

    typedef struct Node Node;
    struct Node{
        const void* data;
        const void* value; 
        Node* left;
        Node* right;
    };

    typedef struct Tree Tree;
    struct Tree{
        Node* root;
        size_t size;
        int (*comp)(const void *, const void *);
    };

功能删除

    void freeTree(Tree* tree, bool TreeContent){
        if(tree->root != NULL){

            // free(tree->root->left);
            // free(tree->root->right);
            // free(tree->root);
        }
    }              

功能插入

bool insertInTree(Tree* bst, const void* key, const void* value){
    if(bst->root == NULL){
            Node* newNode = (Node*) malloc(sizeof(Node));
            if(newNode == NULL){
                   printf("erreur d'allocation dynamique \n");
                   exit(1);
            }
            newNode->left =  newNode->right = NULL;
            newNode->value = value;
            newNode->data = key;
            return true;
    }
    else{
            int isLeft = 0 ;
            Node* Current = bst->root ;
            Node* precedant = NULL;
            while(Current != NULL){
                int compare = bst->comp(&Current->data , &key);
                precedant = Current;
            if(compare == 1){
                   isLeft = 1;
                   Current = Current->left;
            }
            else if(compare == 0){
                    isLeft = 0;
                    Current = Current->right;
            }

            }
            if(isLeft == 1){
                    Node* newNode = (Node*) malloc(sizeof(Node));
                    if(newNode == NULL){
                                       printf("erreur d'allocation dynamique \n");
                                       exit(1);
                    }
                    newNode->left =  newNode->right = NULL;
                    newNode->value = value;
                    newNode->data = key;
                    precedant->left = newNode;
                    bst->size++;
                    return true;
                    }
            else{
                    Node* newNode = (Node*) malloc(sizeof(Node));
                    if(newNode == NULL){
                                       printf("erreur d'allocation dynamique \n");
                                       exit(1);
                    }

                    newNode->left =  newNode->right = NULL;
                    newNode->value = value;
                    newNode->data = key;
                    precedant->right = newNode;
                    bst->size++;
                    return true;

            }

        }
        return false;
}

Answer 1

编辑您不想使用递归，因为freeTree函数不接受Node参数。在这种情况下，您可以通过创建另一个递归函数来删除该限制，该函数最初由freeTree调用。

void freeTree(Tree* tree, bool TreeContent){
    if(tree->root != NULL){
        freeNode(tree->root);
        tree->root = NULL;
    }
}            

新的freeNode可能看起来像

void freeNode(Node *node) {
    if (node->left) freeNode(node->left);
    if (node->right) freeNode(node->right);
    free(node);
}

请注意，freeNode意图是释放整个树（否则父元素的左或右[或根]必须设置为NULL）。

Answer 2

您的要求是您不想使用递归。

在没有使用堆栈/队列（隐式或显式）的情况下，在O(n)时间内无法进行任何类型的遍历。因此，我们将使用堆栈（使用数组）并使用它来删除所有节点。

我知道你已知BST的大小，所以你可以创建一个适当大小的数组 -

struct Node* stack[bst->size];
int top = -1;

该堆栈将包含要处理的所有元素。

我们将首先将根添加到堆栈中 -

if(bst->root)
    stack[++top] = bst->root;

现在我们需要使用循环处理树中的所有节点 -

while(top>=0){
    //Pop one node - 
    struct Node* node = stack[top--];
    //Add its children to the stack;
    if(node->left)
        stack[++top] = node->left;
    if(node->right)
        stack[++top] = node->right;
    // Now free the node as 
    free(node);
}

这就是全部，每个节点将逐个添加到堆栈中，并且当所有节点完成后，堆栈将变为空。

另外作为旁注，在插入函数中，您需要在bst->size++分支中执行if(bst->root == NULL)。否则，您的大小将比实际节点数少一个。