二叉排序树，用顺序表（一维数组）作存储结构 1 以回车为输入结束标志，输入数列L，生成一棵二叉排序树T 2 对二叉树T作中序遍历，输出结果 3 计算二叉排序树T查找成功的平均查找长度，输出结果 4 输入元素X，查找二叉排序树T，若存在含X的结点，则删除该结点，并做中序遍历，执行操作2，否则输出信息”无X“用C语言来完成

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

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void InitList(SqList *L) {
    L->length = 0;
}

int ListInsert(SqList *L, int value) {
    if (L->length == MAXSIZE) {
        return 0;
    }
    L->data[L->length++] = value;
    return 1;
}

BiTNode *CreateBST(SqList *L) {
    BiTNode *T = NULL;
    for (int i = 0; i < L->length; i++) {
        BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
        p->data = L->data[i];
        p->lchild = NULL;
        p->rchild = NULL;
        if (T == NULL) {
            T = p;
        } else {
            BiTNode *q = T;
            while (q != NULL) {
                if (p->data < q->data) {
                    if (q->lchild == NULL) {
                        q->lchild = p;
                        break;
                    } else {
                        q = q->lchild;
                    }
                } else {
                    if (q->rchild == NULL) {
                        q->rchild = p;
                        break;
                    } else {
                        q = q->rchild;
                    }
                }
            }
        }
    }
    return T;
}

void InOrderTraverse(BiTree T) {
    if (T != NULL) {
        InOrderTraverse(T->lchild);
        printf("%d ", T->data);
        InOrderTraverse(T->rchild);
    }
}

int SearchBST(BiTree T, int key, int *count) {
    int flag = 0;
    *count = 0;
    BiTNode *p = T;
    while (p != NULL) {
        (*count)++;
        if (p->data == key) {
            flag = 1;
            break;
        } else if (p->data > key) {
            p = p->lchild;
        } else {
            p = p->rchild;
        }
    }
    return flag;
}

void DeleteNode(BiTree *T, int key) {
    if (*T == NULL) {
        return;
    }
    if ((*T)->data == key) {
        if ((*T)->lchild == NULL && (*T)->rchild == NULL) {
            free(*T);
            *T = NULL;
        } else if ((*T)->lchild == NULL) {
            BiTNode *p = *T;
            *T = (*T)->rchild;
            free(p);
            p = NULL;
        } else if ((*T)->rchild == NULL) {
            BiTNode *p = *T;
            *T = (*T)->lchild;
            free(p);
            p = NULL;
        } else {
            BiTNode *p = (*T)->rchild;
            while (p->lchild != NULL) {
                p = p->lchild;
            }
            (*T)->data = p->data;
            DeleteNode(&((*T)->rchild), p->data);
        }
    } else if ((*T)->data > key) {
        DeleteNode(&((*T)->lchild), key);
    } else {
        DeleteNode(&((*T)->rchild), key);
    }
}

float GetASL(BiTree T, SqList *L) {
    int count = 0;
    float sum = 0;
    for (int i = 0; i < L->length; i++) {
        if (SearchBST(T, L->data[i], &count)) {
            sum += count;
        }
    }
    return sum / L->length;
}

int main() {
    SqList L;
    InitList(&L);

    printf("请输入一些数字（以回车为结束标志）：\n");
    int num;
    while (scanf("%d", &num) != EOF) {
        if (!ListInsert(&L, num)) {
            printf("数组已满，无法插入！\n");
            break;
        }
    }

    BiTree T = CreateBST(&L);

    printf("中序遍历结果为：\n");
    InOrderTraverse(T);
    printf("\n");

    float asl = GetASL(T, &L);
    printf("查找成功的平均查找长度为：%.2f\n", asl);

    int key;
    printf("请输入要删除的数字：\n");
    scanf("%d", &key);
    if (SearchBST(T, key, &num)) {
        DeleteNode(&T, key);
        printf("删除成功！中序遍历结果为：\n");
        InOrderTraverse(T);
        printf("\n");
    } else {
        printf("无该数字！\n");
    }

    return 0;
}