二叉查找树删除与遍历冲突

Question

在删除前，遍历程序运行正常。单独运行删除程序也不报错。但是如果在删除后遍历，程序就会陷入无限循环，报错退出。是否在Delete函数的最后的delete使用不当？如果不用delete，直接把删除节点置空，就无法删除节点。应该怎么处理？可能这个问题有点简单，希望大家帮我解决一下。接触c语言时间不长，程序书写过程中有哪些问题，如果大家发现了也可以和我说一下，感谢。

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
}ST,*PST;
void InitTree(PST &T)
{
    T = NULL;
}
PST Insert(PST &T,int e)
{
    if (T==NULL)
    {
        T = (PST)malloc(sizeof(ST));
        if(T==NULL)
            {printf("Wrong!");return NULL;}
        else
        {
            T->data = e;
            T->left = T->right = NULL;
        }
    }
    else if (e<T->data)
        T->left = Insert(T->left,e);
    else
        T->right = Insert(T->right,e);
    return T;
}
void CreateTree(PST &T){
    int i,num,elem;
    printf("Please enter the number of the nodes in your tree:");
    scanf("%d",&num);
    for(i=0;i<num;i++)
    {
        scanf("%d",&elem);
        T = Insert(T,elem);
    }
}
PST Find(PST T,int e)
{
    if(T==NULL) return NULL;
    if (T->data == e)
        return T;
    else if (e<T->data)
        return Find(T->left,e);
    else if (e>T->data)
        return Find(T->right,e);
    return NULL;
}
PST FindMax(PST T)
{
    while(T->right != NULL)
        T = T->right;
    return T;
}
PST FindMin(PST T)
{
    while(T->left != NULL)
        T = T->left;
    return T;
}
PST Delete(PST &T,int e)
{
    PST new_one;
    if (T==NULL) return NULL;
    else if (e<T->data)
        T->left = Delete(T->left,e);
    else if (e>T->data)
        T->right = Delete(T->right,e);
    else if (T->left&&T->right)
    {
        new_one = FindMin(T->right);
        T->data = new_one->data;
        T->right = Delete(T->right,T->data);
    }
    else
    {
        new_one = T;
        if(T->left) T=T->left;
        else if (T->right) T = T->right;
        delete new_one;
        new_one = NULL;
    }
    return T;
}
void PrintT(PST T){
    if(T!=NULL)
    {
        printf("%-3d",T->data);
        PrintT(T->left);
        PrintT(T->right);
    }
}
int main()
{
    PST BigTree;
    InitTree(BigTree);
    CreateTree(BigTree);
    PrintT(BigTree);
    Find(BigTree,7);
    Delete(BigTree,7);
    PrintT(BigTree);
    return 0;
}

这样改也是无法删除节点，但能正常遍历：

PST Delete(PST &T,int e)
{
    PST new_one;
    if (T==NULL) return NULL;
    else if (e<T->data)
        T->left = Delete(T->left,e);
    else if (e>T->data)
        T->right = Delete(T->right,e);
    else if (T->left&&T->right)
    {
        new_one = FindMin(T->right);
        T->data = new_one->data;
        T->right = Delete(T->right,T->data);
    }
    else
    {
        new_one = T;
        if(T->left) T=T->left;
        else if (T->right) T = T->right;
        new_one = NULL;
        delete new_one;
    }
    return T;
}

Answer 1

上面的答案说的没错，没有考虑左右都是空的情况，可以参考下面的代码：

template<typename T>
bool BTree<T>::deleteNode(const T &value, Node *&node) {
    if (node == nullptr) {
        return false;
    } else if (value < node->value) {
        return deleteNode(value, node->left);
    } else if (value > node->value) {
        return deleteNode(value, node->right);        
    } else {
        if (node->left == nullptr && node->right == nullptr) {
            delete node;
            node = nullptr;
        } else if (node->left == nullptr) {
            Node *t = node;
            node = node->right;
            delete t;
        } else if (node->right == nullptr) {
            Node *t = node;
            node = node->left;
            delete t;
        } else {
            Node *to_del = node->left, *before = node;
            while (to_del->right != nullptr) {
                before = to_del;
                to_del = to_del->right;
            }
            if (before == node) {
                delete node;                
                node = to_del;
            } else {
                node->value = to_del->value;
                before->right = to_del->left;
                delete to_del;
            }
        }
        return true;
    }
}

这是我以前写的删除二叉树节点的的代码。

Answer 2

delete的else分句里没有考虑两个子节点都是空的情况