#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef char ElementType;
typedef struct BiTreeNode
{
    ElementType data;
    struct BiTreeNode *lchild;
    struct BiTreeNode *rchild;
}BiTreeNode,*BiTree;
BiTree Initate()
{
    BiTreeNode *p;
    p=NULL;
    return p;
}
void CreateBiTree(BiTree &T)
{
    ElementType data;
    printf("请输入相应的数据(*表示置空):");
    data=getchar();
    if(data=='*')
        T=NULL;
    else
    {
        T=(BiTreeNode *)malloc(sizeof(BiTreeNode));
        if(T==NULL)
            return;
        T->data=data;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
void InOrderTraverse(BiTree &T)
{
    if(T)
    {
        InOrderTraverse(T->lchild);
        printf("%c",T->data);
        InOrderTraverse(T->rchild);
    }
}
BiTree SearchNode(BiTree &T,ElementType data)
{
    BiTree p;
    if(T)
    {
        if(T->data==data)
            return T;
        if(T->lchild)
        {
            p=SearchNode(T->lchild,data);
            if(p)
                return p;
        }
        if(T->rchild)
        {
            p=SearchNode(T->rchild,data);
            if(p)
                return p;
        }
    }
    return NULL;
}
int InsertNode(BiTree &T,ElementType data)
{
    BiTree p,q;
    p=SearchNode(T,data);
    if(p)
        return 1;
    else
    {
        q=(BiTreeNode *)malloc(sizeof(BiTreeNode));
        if(q==NULL)
            return -1;
        q->data=data;
        q->lchild=NULL;
        q->rchild=NULL;
        if(p==NULL)
            T=q;
        else if(p->lchild==NULL)
            p->lchild=q;
        else
        {
            q->lchild=p->lchild;
            p->lchild=q->lchild;
        }
    }
}
int DeleteNode(BiTree &T,ElementType data)
{
    BiTree p,q;
    p=SearchNode(T,data);
    if(p==NULL)
        return -1;
    q=p;
    p=NULL;
    free(q);
}
void DestroyBiTree(BiTree &T)
{
    if(T)
    {
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        T=NULL;
    }
}
int main(void)
{
    BiTree T;
    T=Initate();
    int a;
    ElementType data;
    do
    {
        printf("二叉树的基本操作:\n");
        printf("1.建立二叉树\n2.输出二叉树\n3.查找结点\n4.插入结点\n5.删除结点\n6.销毁二叉树\n0.退出\n");
        printf("请选择对应的功能:\n");
        scanf("%d",&a);
        getchar();
        if(a==0)
            break;
        switch(a)
        {
            case 1:
                CreateBiTree(T);
                break;
            case 2:
                InOrderTraverse(T);
                break;
            case 3:
                printf("请输入结点的数据值:\n");
                scanf("%c",&data);
                SearchNode(T,data);
                break;
            case 4:
                printf("请输入结点的数据值:\n");
                scanf("%c",&data);
                InsertNode(T,data);
                break;
            case 5:
                printf("请输入结点的数据值:\n");
                scanf("%c:",&data);
                DeleteNode(T,data);
                break;
            case 6:
                DestroyBiTree(T);
                break;
        }
    }while(a!=0);
    return 0;
}
建立的时候总是错误，自己又发现不了错误。。。。。。