由文件建立二叉树的算法

由文件(广义表)建立二叉树的算法
1.广义表的定义
一个长度为n≥0 的广义表是一个数据结构,LS=(a1,a2,……,an-1,an)
其中，LS为广义表的名字, ai为表中元素；ai可以是原子元素，也可以是一个子表。n为表的长度，长度
为0的表称为空表。    
2.关于广义表形式表示二叉树的说明  
A.约定:表中的一个字母代表一个结点的数据信息。
B.每个根结点作为由子树构成的表的名字放在表的前面。
C.每个结点的左子树和右子树之间用逗号分开，若只有右子树而无左子树，则逗号不能省略。
D.在整个广义表的末尾加一个特殊符号(如@)作为结束标志。
3.算法思路
A.若取到的元素为字母，则如下建立一个新结点,若该结点为根结点， 则将该结点的地址送T。若该结点
不是二叉树的根结点， 则将该结点作为左孩子(若标志为1)或者右孩子(若标志为2)链接到其双亲结点上(
双亲结点的地址在栈顶)。
B.若取到的元素为左括号(, 则表明一个子表开始，将标志置为1，同时，将前面那个结点的地址进栈。
若取到的元素为右括号 ),则表明一个子表结束，将作退栈操作。
C.若取到的元素为逗号，则表明以左孩子为根的子树处理完毕，接着应处理以右孩子为根的子树，将标
志置为2。
如此处理广义表中每一个元素，
直到取到结束符号@或(EOF)为止。
================================================================================
源程序:
#include
#define M 100
typedef struct BTNode
{    char data;
    struct BTNode*lchild;
    struct BTNode*rchild;
}BTNode,*BTree;
BTree creat(BTree T)
{    BTree stack[M],p=NULL;
    int top=-1,flag;
    char ch;
    FILE*fp;
    if((fp=fopen("data","r"))==NULL)
    {    printf("can not open data file\n");
        exit(0);
    }
    ch=fgetc(fp);//从文件中读入一个字符
    while(ch!=EOF)//判定是否是文件结尾
    {    switch(ch) 
        {    case'(':top++;stack[top]=p;flag=1;break; 
            case')':   top--;break; 
            case',':flag=2;break; 
            default:p=(BTree)malloc(sizeof(BTNode)); 
            p->data=ch;p->lchild=p->rchild=NULL;
            if(T==NULL) 
                T=p; 
            else 
            {   switch(flag) 
                {    case 1:stack[top]->lchild=p;break;     
                    case 2:stack[top]->rchild=p;break; 
                } 
            }
        }
        ch=fgetc(fp);
    }
    fclose(fp);
    return T;
}
void preorder(BTree T)
{    if(T!=NULL)
    {    printf("%c",T->data);
        preorder(T->lchild);
        preorder(T->rchild);
    }
}
void inorder(BTree T)
{    if(T!=NULL)
    {    inorder(T->lchild);
        printf("%c",T->data);
        inorder(T->rchild);
    }
}
void postorder(BTree T)
{    if(T!=NULL)
    {    postorder(T->lchild);
        postorder(T->rchild);
        printf("%c",T->data);
    }
}
void main()
{    BTree T=NULL;
    T=creat(T);
    printf("前序遍历的结果是:");
    preorder(T);
    printf("\n");
    printf("中序遍历的结果是:");
    inorder(T);
    printf("\n");
    printf("后序遍历的结果是:");
    postorder(T);
    printf("\n");
}
================================================================================
程序测试:
data文件中输入:A(B(D),C(F(,E),G))
程序的运行结果为:
前序遍历的结果:ABCDEFG
中序遍历的结果:DBAFECG
后序遍历的结果:DBEFGCA
================================================================================
方法二:(由前序序列建立二叉树)
#include
typedef struct BTNode
{    char data;
    struct BTNode*lchild;
    struct BTNode*rchild;
}BTNode,*BTree;
BTree creat(void)
{    BTree T;
    char c;
    scanf("%c",&c);
    if(c=='#')
        T=NULL;
    else
    {   T=(BTree)malloc(sizeof(BTNode));
        T->data=c;
        T->lchild= creat();
        T->rchild= creat();
    }
    return T;
}
void preorder(BTree T)
{    if(T!=NULL)
    {    printf("%c",T->data);
        preorder(T->lchild);
        preorder(T->rchild);
    }
}
void inorder(BTree T)
{    if(T!=NULL)
    {    inorder(T->lchild);
        printf("%c",T->data);
        inorder(T->rchild);
    }
}
void postorder(BTree T)
{    if(T!=NULL)
    {    postorder(T->lchild);
        postorder(T->rchild);
        printf("%c",T->data);
    }
}
void main()
{    BTree T;
    T=creat();
    printf("前序遍历的结果是:");
    preorder(T);
    printf("\n");
    printf("中序遍历的结果是:");
    inorder(T);
    printf("\n");
    printf("后序遍历的结果是:");
    postorder(T);
    printf("\n");
}
==================================================================================
输入:ABC##DE#G##F###
前序遍历的结果是:ABCDEGF