c - 为什么我的代码在删除具有两个子节点的节点后无法显示 pre_order？

Question

这是我的代码：

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

struct node
{
    struct node *left;
    int data;
    struct node *right;
};
struct node *fnode = NULL;

void insert(int val)
{
    struct node *ptr = (struct node *) malloc(sizeof(struct node));
    struct node *parentptr, *nodeptr;
    ptr->data = val;
    ptr->left = NULL;
    ptr->right = NULL;
    if(fnode == NULL)
    {
        fnode = ptr;
    }
    else
    {
        parentptr = NULL;
        nodeptr = fnode;
        while(nodeptr!=NULL)
        {
            parentptr = nodeptr;
            if(val<nodeptr->data)
                nodeptr = nodeptr->left;
            else
                nodeptr = nodeptr->right;
        }
        if(val<parentptr->data)
            parentptr->left = ptr;
        else
            parentptr->right = ptr;
    }
}

void pre_order(struct node *tree)
{
    if(tree!=NULL)
    {
        printf("%i ",tree->data);
        if(tree->left)
            pre_order(tree->left);
        if(tree->right)
            pre_order(tree->right);
    }
}

void in_order(struct node *tree)
{
    if(tree)
    {
        in_order(tree->left);
        printf("%i ",tree->data);
        in_order(tree->right);
    }
}

void post_order(struct node *tree)
{
    if(tree)
    {
        post_order(tree->left);
        post_order(tree->right);
        printf("%i ",tree->data);
    }
}

struct node *smallest_element(struct node *tree)
{
    if(tree==NULL || tree->left == NULL)
        return tree;
    else
        return smallest_element(tree->left);
}
struct node *largest_element(struct node *tree)
{

    if(tree== NULL || tree->right==NULL)
        return tree;
    else
    {
        return largest_element(tree->right);
    }
}

struct node *delete_element(struct node *tree, int val)
{
    // some declarations
    struct node *parent, *child;
    child = parent = tree;
    bool doesnt_exist = false;

    // finding the node to be deleted and its corresponding parent
    while(child->data!=val)
    {
        parent = child;
        if(val < child->data)
            child = child->left;
        else
            child = child->right;

        if(child==NULL)
        {
            doesnt_exist = true;
            break;
        }
    }

    // if no node exists, print not found
    if(doesnt_exist)
    {
        printf("\nThe node does not exist in the BST.");
        return tree;
    }
    // if node exists
    else
    {
        //if parent node is to be deleted
        if(child==parent)
        {
            //if only parent node exists in the tree
            if(child->left == NULL && child->right == NULL)
            {
                free(child);
                tree = NULL;
                return tree;
            }
            // deleting the parent node and replacing it by left-subtree's highest element
            struct node *temp = tree->left;
            struct node *pre_temp = tree->left;
            //searching for left subtree's max element and its parent
            while(temp->right!=NULL)
            {
                pre_temp = temp;
                temp = temp->right;
            }

            //changing the deleted node's value with left subtree's highest element
            child->data = temp->data;

            //making the ex-position of changed element point to null
            if(pre_temp->right == temp)
            {
                pre_temp->right = NULL;
            }
            else
            {
                pre_temp->left = NULL;
            }
            //freeing the ex-position of changed element.
            free(temp);

        }
        else
        {
            // if the node to be deleted has 2 nodes
            if(child->left && child->right)
            {
                //some declarations
                struct node *temp = child->left;
                struct node *pretemp = child;

                //browsing to the maximum node on left subtree
                while(temp->right!=NULL)
                {
                    pretemp = temp;
                    temp = temp->right;
                }

                //exchanging left subtree's max with element to be deleted
                child->data = temp->data;

                //making the temp's parent point to null
                if(pretemp->left == temp)
                    pretemp->left = NULL;
                else
                    pretemp->right = NULL;
                //freeing temp;
                free(temp);
            }
            //if the node to be deleted has only right node
            else if(child->left == NULL && child->right)
            {
                if(parent->left==child)
                {
                    parent->left = child->right;
                }
                else
                {
                    parent->right = child->right;
                }
                free(child);
                return tree;
            }
            // if the node to be deleted has only left node
            else if(child->right==NULL && child->left)
            {
                if(parent->left==child)
                {
                    parent->left = child->left;
                }
                else
                {
                    parent->right = child->left;
                }
                free(child);
                return tree;
            }
            //if the node to be deleted has no children
            else
            {
                if(parent->left == child)
                    parent->left = NULL;
                else
                    parent->right = NULL;
                free(child);
                return tree;
            }
        }
    }
}
int main()
{
    int decision;
    struct node *ptr;
    int ip;
    do
    {
        printf("\n ********MAIN MENU********");
        printf("\n 1. Insert element");
        printf("\n 2. Pre-order Traversal");
        printf("\n 3. In-order Traversal");
        printf("\n 4. Post-order Traversal");
        printf("\n 5. Find smallest element");
        printf("\n 6. Find largest element");
        printf("\n 7. Delete an element");
        printf("\n 8. Exit");
        printf("\nEnter your choice:");
        scanf("%i",&decision);
        switch(decision)
        {
            case 1:
                printf("\nEnter the element to be inserted:");
                scanf("%i",&ip);
                insert(ip);
                break;
            case 2:
                if(fnode)
                {
                    printf("\nThe pre-order traversal is as follows:\n");
                    pre_order(fnode);
                }
                else
                {
                    printf("\nThe BST is empty!!!");
                }
                break;
            case 3:
                if(fnode)
                {
                    printf("\nThe in-order traversal is as follows:\n");
                    in_order(fnode);
                }
                else
                {
                    printf("\nThe BST is empty!!!");
                }
                break;
            case 4:
                if(fnode)
                {
                    printf("\nThe post-order traversal is as follows:\n");
                    post_order(fnode);
                }
                else
                {
                    printf("\nThe BST is empty!!!");
                }
                break;
            case 5:
                ptr = smallest_element(fnode);
                if(ptr)
                {
                    printf("\nThe smallest element is: %i",ptr->data);
                }
                else
                {
                    printf("\nThe BST is empty!!!");
                }
                break;
            case 6:
                ptr = largest_element(fnode);
                if(ptr)
                {
                    printf("\nThe largest element is: %i",ptr->data);
                }
                else
                {
                    printf("\nThe BST is empty!!!");
                }
                break;
            case 7:
                printf("\nEnter the element you want to delete:");
                scanf("%i",&ip);
                fnode = delete_element(fnode,ip);
                break;
        }
    }
    while(decision!=8);
    return 0;
}

删除具有两个子节点的节点后，生成的 BST 正确形成（我通过调试工具验证了它）。我已经添加了从 BST 删除节点的所有可能情况（有 0/1/2 个子节点，我已经处理了所有事情）。

但是当我让它打印前序/后序/中序遍历时，程序就退出了。你能建议我为什么会这样吗？

标签： cdata-structuresbinary-search-tree