#include <stdio.h>
#include <alloc.h>
typedef struct stu
{
    char data;
    struct stu *left,*right;
}sn;
sn *Create(sn *A)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='*')
    {
    A=NULL;
    }
    else
    {
    A=(sn *)malloc(sizeof(sn));
    if (!A)
    {
        printf("内存分配失败!\n");
    }
        A->data=ch;
    A->left=Create(A->left);
        A->right=Create(A->right);
    }
    return(A);
}
void Prev(sn *b) /*先序遍历*/
{
    if(b)
    {
    printf("%c",b->data);
    Prev(b->left);
    Prev(b->right);
    }
}
void Midv(sn *b)   /*中序遍历*/
{
    if(b)
    {
    Midv(b->left);
    printf("%c",b->data);
        Midv(b->right);
    }
}
void Lastv(sn *b) /*后序遍历*/
{
    if(b)
    {
    Lastv(b->left);
    Lastv(b->right);
    printf("%c",b->data);
    }
}
char findparent(sn *T,char ch)
{
    if(T)
    {
        if (((T->left)&&(T->left->data==ch))||((T->right)&&(T->right->data==ch)))
        return(T->data);
        else
        {
        findparent(T->left,ch);
            findparent(T->right,ch);
        }
    }
}
sn *findchild(sn *T,char ch)
{
    if(T)
    {
        if (T->data==ch)
            return(T);
        else
        {
        findchild(T->left,ch);
        findchild(T->right,ch);
        }
    }
}
void main()
{
    int k;
    char s;
    sn *t,*q,*p;
    p=q=NULL;
    printf("Create a tree!\n");
    t=Create(q);/*测试数据abc**de*g**f***   */
    printf("----------------------------------------\n");
    printf("k=1,先序遍历\n");
    printf("k=2,中序遍历\n");
    printf("k=3,后序遍历\n");
    printf("k=4,求给定结点的双亲\n");
    printf("k=5,求给定结点的孩子\n");
    printf("k=6,退出程序\n");
    printf("----------------------------------------\n");
L1: printf("please choose k:\n");
    scanf("%d",&k);
    switch (k)
    {
        case 1:    Prev(t);break;
        case 2:    Midv(t);break;
        case 3:    Lastv(t);break;
    case 4:    printf("input the node:\n");
           getchar();
           scanf("%c",&s);
           if (s!=t->data)/*不是头结点输出其双亲*/
               printf("the %c's parent is:  %c",s,findparent(t,s));
           else
               printf("not find");
           break;
        case 5:    printf("input the node:\n");
                   getchar();
           scanf("%c",&s);
                   p=findchild(t,s);
           printf("%c\n",p->data);
           if (p->left)
                   printf("the %c's leftchild is:  %c\n",s,p->left->data);
                   else
                       printf("the %c haven't leftchild\n",s);
                   if (p->right)
                       printf("the %c's rightchild is:  %c\n",s,p->right->data);
                   else
                       printf("the %c haven't rightchild\n",s);

           break;
        case 6:    exit(0);
    }
    printf("\n");
    /*getchar();*/
    goto L1;
}