c - C二叉树删除不起作用按顺序打印导致无限递归

Question

我正在学习二叉树，我正在尝试从二叉树中删除一个节点。在 print in order 函数中无限递归后出现分段错误。它仅在调用删除函数后执行此操作。我不明白为什么会这样。我认为只有在树中的最后一个左指针设置为 NULL 以外的值时才会发生这种情况，这将导致 if 语句返回永远不会被触发。在这种特殊情况下，删除功能是删除右侧的节点，因此它甚至不应该触及左侧的任何内容。帮助将不胜感激。

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

struct Node{
    //blueprint for node
    int data;
    struct Node *Left;
    struct Node *Right;
};

struct Node *CreateNode(int data){
    //utility function to create a new node
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->Left = NULL;
    newNode->Right = NULL;
    newNode->data = data;
    return newNode;
}

struct Node *insertNode(struct Node *root, int num){
    if(root == NULL){
        root = CreateNode(num);
        return root;
    }
    if(root->data >= num){
        if(root->Left != NULL){
            insertNode(root->Left, num);
        }
        else{
            //if the node on the left of root is equal to NULL
            //create a node
            root->Left = CreateNode(num);
        }
    }
    else{
        if(root->Right != NULL){
            insertNode(root->Right, num);
        }
        else{
            //if the node on the right of root is equal to NULL
            //create a node
            root->Right = CreateNode(num);
        }
    }
}

void inOrderPrint(struct Node *Head){
    //prints nodes in the binary tree in order
    if(Head == NULL){
        //if the head is null, stop doing recursion
        return;
    }
        //recursivly calls itself and passes in the left node as a parameter
    if(Head->Left != NULL){
       inOrderPrint(Head->Left);
    }
        //prints out the data at the current node
        printf("%d ", Head->data);
        //recusivly calls itself and pases in the right node as a peramater
    if(Head->Right != NULL){
        inOrderPrint(Head->Right);
    }
}

int getHeight(struct Node *Head){
    //gets the height of the binary tree
    if(Head == 0){
        return -1;
    }
    int left = getHeight(Head->Left)+1;
    int right = getHeight(Head->Right) + 1;
    if(left > right){
        return left;
    }
    else{
        return right;
    }
}

int childNum(struct Node *Head){
    //returns the number of children the binary search tree node has (directly below it, not counting grand children)
    if(Head->Left == NULL && Head->Right == NULL){
        //if there is no child
        return 0;
    }
    else if(Head->Left == NULL || Head->Right == NULL){
        //if there 1 child
        return 1;
    }
    else{
        //if there are two children
        return 2;
    }
}

int getMax(struct Node *root){
    if(root->Right == NULL){
        return root->data;
    }
    else{
        return getMax(root->Right);
    }
}

struct Node *DeleteNode(struct Node *root, int num){
    //function to delete a node from the binary search tree
    if(root == NULL){
        return root;
    }
    if(root->data == num){
        //if this is the node to be deleted
        int numberOfChildren = childNum(root);
        if(numberOfChildren == 0){
            printf("here??");
            free(root);
            return NULL;
        }
        else if(numberOfChildren == 1){
            if(root->Left == NULL){
                struct Node *temp = root->Right;
                free(root);
                return temp;
            }
            else{
                struct Node *temp = root->Left;
                free(root);
                return temp;
            }
        }
        else{
            int max = getMax(root->Left);
            root->data = max;
            DeleteNode(root->Left, max);
            return root;
        }
    }
    else if(root->data >= num){
        //if this node is greater than or equal to the node to be deleted, recur to the node on the left
        root->Left = DeleteNode(root->Left, num);
    }
    else{
        //if this node is less than the node to be deleted, recur to the node on rhe right
        root->Right = DeleteNode(root->Right, num);
    }
    return root;
}

int main()
{
    struct Node *root = NULL;
    root = insertNode(root, 5);
    insertNode(root, 10);
    insertNode(root, 3);
    insertNode(root, 14);
    insertNode(root, 7);
    insertNode(root, 16);
    inOrderPrint(root);
    printf("\nheight: %d", getHeight(root));
    DeleteNode(root, 10);
    printf("root left: %d", root->Left->data);
    printf("\n");
    inOrderPrint(root);
    //sprintf(result, "%d/%f ...", int);

}

标签： ctreebinary-tree