二叉平衡树，程序有缺陷，缺陷在哪里？

这是我的源代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef int Infotype;
typedef long long int KeyType;
typedef struct
{
    KeyType key;
    Infotype otherinfo;
}Elemtype;
typedef struct BSTNode
{
    Elemtype data;//*数据结点
    int _depth;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
typedef struct LNode
{
    BSTree data;
    struct LNode *next,*prior;
}LNode,*LinkList;
BSTree _Data(BSTree a)
{
    if(!a)
    {
        return NULL;
    }
    else if((a->lchild)&&(a->rchild))
    {
        return a->lchild->_depth>a->rchild->_depth?a->lchild:a->rchild;
    }
    else
    {
        return a->lchild?a->lchild:a->rchild;
    }
}
void _Data2(BSTree *a,BSTree *b,BSTree *c,KeyType key)
{
    BSTree b1,c1=NULL;
    b1=*a;
    while(b1)
    {
        if(b1->data.key==key)
        {
            break;
        }
        c1=b1;
        if(key<b1->data.key)
        {
            b1=b1->lchild;
        }
        else
        {
            b1=b1->rchild;
        }
    }
    *b=c1;
    *c=b1;
}
void _Data3(BSTree *a)
{
    BSTree b=_Data(*a);
    if(b)
    {
        (*a)->_depth=b->_depth+1;
    }
    else if(*a)
    {
        (*a)->_depth=1;
    }
}
void _Data4(BSTree *a,KeyType key)
{
    BSTree b,c;
    _Data2(a,&b,&c,key);
    if((!c)||(!b))
    {
        return;
    }
    LinkList d,e;
    d=(LNode*)malloc(sizeof(LNode));
    d->data=NULL;
    d->next=d->prior=NULL;
    e=d;
    b=*a;
    while(b)
    {
        LinkList o;
        o=(LNode*)malloc(sizeof(LNode));
        o->data=b;
        o->prior=e;
        o->next=NULL;
        e->next=o;
        e=o;
        if(key<b->data.key)
        {
            b=b->lchild;
        }
        else if(key>b->data.key)
        {
            b=b->rchild;
        }
        else
        {
            break;
        }
    }
    while(e->prior)
    {
        _Data3(&e->data);
        LinkList r;
        r=e;
        e=e->prior;
        free(r);
    }
    free(d);
}
int datas3(BSTree a)
{
    if(!a)
    {
        return 0;
    }
    else if((a->lchild)&&(a->rchild))
    {
        if(a->lchild->_depth-a->rchild->_depth>1)
        {
            return 1;
        }
        else if(a->lchild->_depth-a->rchild->_depth<-1)
        {
            return 2;
        }
        return 0;
    }
    else if((!a->lchild)&&(a->rchild))
    {
        if(a->rchild->_depth>1)
        {
            return 2;
        }
        return 0;
    }
    else if((a->lchild)&&(!a->rchild))
    {
        if(a->lchild->_depth>1)
        {
            return 1;
        }
        return 0;
    }
    return 0;
}
void _Data6(BSTree *a,BSTree *b,KeyType key)
{
    BSTree b1,c1=NULL;
    b1=*a;
    while(b1)
    {
        if(datas3(b1))
        {
            c1=b1;
        }
        if(b1->data.key==key)
        {
            break;
        }
        else if(key<b1->data.key)
        {
            b1=b1->lchild;
        }
        else
        {
            b1=b1->rchild;
        }
    }
    *b=c1;
}
void _Data7(BSTree *a,BSTree *c1)
{
    BSTree b,c,d,e;
    b=*a;
    if(datas3(b)==1)
    {
        c=b->lchild;
        d=c->rchild;
        if(!d);
        else if(!((!d->lchild)&&(!d->rchild)))
        {
            if(d->lchild)
            {
                e=d->lchild;
                Elemtype data;
                data=e->data;
                e->data=d->data;
                d->data=data;
                d->rchild=e;
                d->lchild=NULL;
            }
            e=d->rchild;
            b->lchild=d;
            d->lchild=c;
            c->rchild=NULL;
            _Data4(a,c->data.key);
        }
        c=b->lchild;
        d=c->rchild;
        c->rchild=b;
        b->lchild=d;
    }
    else
    {
        c=b->rchild;
        d=c->lchild;
        if(!d);
        else if(!((!d->lchild)&&(!d->rchild)))
        {
            if(d->rchild)
            {
                e=d->rchild;
                Elemtype data;
                data=e->data;
                e->data=d->data;
                d->data=data;
                d->lchild=e;
                d->rchild=NULL;
            }
            e=d->lchild;
            b->rchild=d;
            d->rchild=c;
            c->lchild=NULL;
            _Data4(a,c->data.key);
        }
        c=b->rchild;
        d=c->lchild;
        c->lchild=b;
        b->rchild=d;
    }
    *c1=c;
    *a=b;
}
void _Data5(BSTree *a,KeyType key)
{
    BSTree b,c,f,g;
    _Data6(a,&b,key);
    if(!b)
    {
        return;
    }
    _Data2(a,&f,&g,b->data.key);
    _Data7(&b,&c);
    if(!f)
    {
        *a=c;
    }
    else if(f->lchild==g)
    {
        f->lchild=c;
    }
    else
    {
        f->rchild=c;
    }
    _Data4(a,b->data.key);
}
void Elemtype_data(Elemtype *a,KeyType key)
{
    a->key=key;
    a->otherinfo=rand();
}
void InsertBFS(BSTree *a,Elemtype b)
{
    if(!(*a))
    {
        BSTree c;
        c=(BSTree)malloc(sizeof(BSTNode));
        c->data=b;
        c->lchild=c->rchild=NULL;
        *a=c;
    }
    else if(b.key<(*a)->data.key)
    {
        InsertBFS(&(*a)->lchild,b);
    }
    else
    {
        InsertBFS(&(*a)->rchild,b);
    }
}
void Insert(BSTree *a,KeyType key)
{
    Elemtype b;
    Elemtype_data(&b,key);
    InsertBFS(a,b);
    _Data4(a,key);
    _Data5(a,key);
}
void CreateBFS(BSTree *a,KeyType end_flag)
{
    KeyType key;
    printf("请输入您要插入的信息：");
    scanf("%lld",&key);
    fflush(stdin);
    while(key!=end_flag)
    {
        Insert(a,key);
        printf("请输入您要插入的信息：");
        scanf("%lld",&key);
        fflush(stdin);
    }
}
void DeleteBFS(BSTree *a,KeyType key)
{
    BSTree b,c,d,e;
    _Data2(a,&c,&b,key);
    if(!b)
    {
        printf("NULL!\n");
        return;
    }
    d=b;
    if((d->lchild)&&(d->rchild))
    {
        e=b->lchild;
        while(e->rchild)
        {
            d=e;
            e=e->rchild;
        }
        b->data=e->data;
        if(d!=b)
        {
            d->rchild=e->lchild;
        }
        else
        {
            d->lchild=e->lchild;
        }
        free(e);
        return;
    }
    else if(!b->lchild)
    {
        b=b->rchild;
    }
    else if(!b->rchild)
    {
        b=b->lchild;
    }
    if(!c)
    {
        *a=b;
    }
    else if(c->lchild==d)
    {
        c->lchild=b;
    }
    else
    {
        c->rchild=b;
    }
    free(d);
}
void DeleteData(BSTree *a,KeyType key)
{
    BSTree b,c;
    DeleteBFS(a,key);
    _Data2(a,&b,&c,key);
    _Data5(a,key);
}
void Delete(BSTree *a,KeyType end_flag)
{
    KeyType key;
    printf("请输入您要删除的信息：");
    scanf("%lld",&key);
    fflush(stdin);
    while(key!=end_flag)
    {
        DeleteData(a,key);
        printf("请输入您要删除的信息：");
        scanf("%lld",&key);
        fflush(stdin);
    }
}
void Print_cha(BSTree a,KeyType key)
{
    BSTree b,c;
    _Data2(&a,&b,&c,key);
    if(c)
    {
        printf("key:%lld,Infotype:%d",c->data.key,c->data.otherinfo);
    }
    else
    {
        printf("NULL");
    }
    printf("\n");
}
void PrintBFS(BSTree a,KeyType end_flag)
{
    KeyType key;
    printf("请输入您要删除的信息：");
    scanf("%lld",&key);
    fflush(stdin);
    while(key!=end_flag)
    {
        Print_cha(a,key);
        printf("请输入您要删除的信息：");
        scanf("%lld",&key);
        fflush(stdin);
    }
}
void Depth_print(BSTree a)
{
    int Depth;
    if(!a)
    {
        Depth=0;
    }
    else
    {
        Depth=a->_depth;
    }
    printf("高度：%d\n",Depth);
}
void data_print(BSTree a)
{
    if(a)
    {
        data_print(a->lchild);
        printf("key:%lld,Infotype:%d\n",a->data.key,a->data.otherinfo);
        data_print(a->rchild);
    }
}
main()
{
    BSTree a=NULL;
    for(;;)
    {
        printf("1.定位查询\n2.插入\n3.删除\n4.查询深度\n5.查询所有\n按其他键退出\n");
        char b=getch();
        if((b=='4')||(b=='5'))
        {
            switch(b)
            {
                case '4':Depth_print(a);break;
                case '5':data_print(a);break;
            }
        }
        else if((b<'3')||(b>'1'))
        {
            KeyType end_flag;
            printf("请输入结束标志：");
            scanf("%lld",&end_flag);
            fflush(stdin);
            switch(b)
            {
                case '1':PrintBFS(a,end_flag);break;
                case '2':CreateBFS(&a,end_flag);break;
                case '3':Delete(&a,end_flag);break;
            }
        }
        else
        {
            return 0;
        }
        system("pause");
        system("cls");
    }
}

我输入的结果为：

1.定位查询
2.插入
3.删除
4.查询深度
5.查询所有
按其他键退出
请输入结束标志：21
请输入您要插入的信息：1
请输入您要插入的信息：2
请输入您要插入的信息：3
请输入您要插入的信息：4
请输入您要插入的信息：5
请输入您要插入的信息：6
请输入您要插入的信息：7
请输入您要插入的信息：8
请输入您要插入的信息：9
请输入您要插入的信息：10
请输入您要插入的信息：11
请输入您要插入的信息：12
请输入您要插入的信息：13
请输入您要插入的信息：14
请输入您要插入的信息：15
请输入您要插入的信息：16
请输入您要插入的信息：17
请输入您要插入的信息：18
请输入您要插入的信息：19
请输入您要插入的信息：20
请输入您要插入的信息：21
请按任意键继续. . .

但是按5输出的时候却是这样的

1.定位查询
2.插入
3.删除
4.查询深度
5.查询所有
按其他键退出
key:1,Infotype:41
key:2,Infotype:18467
key:3,Infotype:6334
key:4,Infotype:26500
key:6,Infotype:15724
key:7,Infotype:11478
key:8,Infotype:29358
key:10,Infotype:24464
key:11,Infotype:5705
key:12,Infotype:28145
key:14,Infotype:16827
key:15,Infotype:9961
key:16,Infotype:491
key:17,Infotype:2995
key:18,Infotype:11942
key:19,Infotype:4827
key:20,Infotype:5436
请按任意键继续. . .

为什么会缺9和13的信息？