b->data = p->data + q->data;
            b->next = NULL;
            b->lchild = p;
            b->rchild = q;
            InsertNode(h,b);
        }
        return (h->next);
    }
}

int count(BiTree root)
{
    if(root == NULL)    return 0;
    else if(root->lchild==NULL && root->rchild==NULL)   return 1;
    else
        return(
        count(root->lchild) +
        count(root->rchild) + 1);
}

void InOrder(BiTree root)
{
    if(root)
    {
        InOrder(root->lchild);
        printf("%d ",root->data);
        InOrder(root->rchild);
    }
}

void printLinkList(LinkList h)
{
    h = h->next;
    while(h)
    {
        printf("%d ",h->data);
        h = h->next;
    }
    printf("\n");
}

void main()
{
    int i;
    int a[N] = {9,7,5,3,1,8,6,4,2,0};
    LinkList h;
    BiTree root;

    FormLinkList(h,a,N);
    printLinkList(h);

    root = FormHuffman(h);
    InOrder(root);

    i = count(root);
    printf("\nTotal Number of BiNodes is %d.\n",i);
}

（8）对于二叉树T的两个结点N1和N2，我们应该选择树T结点的前序、中序和后序中哪两个
序列来判定结点N1必定是结点N2的祖先，并给出判断的方法。要求给出详细的算法，然后再
写出程序。（本题20分）
参考答案：
有前中后三种序列，我们该选择哪一种呢？
我们先来做一个假设：N1是N2的祖先。此时N2有两种情况，一是N2在N1的左子树中，二是N2在
N1的右子树中。
情况    N2在N1的左子树      N2在N1的右子树      结果
前序        N1...N2             N1...N2         相同
中序        N2...N1             N1...N2         不同
后序        N2...N1             N2...N1         相同
在前序序列中N1稳定排列于N2的前面，则N1有可能是N2的祖先，但并不代表N1一定是N2的祖先。
在后序序列中N1稳定排列于N2的后面，则N1有可能是N2的祖先，但并不代表N1一定是N2的祖先。
在中序序列中N1可能在N2的前面，也可能在N2的后面，这一点对我们判断N1是否可能是N2的祖先没有多大帮助。
由于中序序列存在这种不稳定性，我们只好采取前序和后序。
假如说有一种情况如下：
前序：...N1...N2...
后序：...N2...N1...
这两个序列，能判定N1是N2的祖先吗？
思考两个问题：
<1>N1是N2的祖先，则N1和N2的相对位置关系是上面的两个序列表现的这种前后关系吗？
<2>两个数列中N1和N2有这种前后关系，那N1一定是N2的祖先吗？
第1个问题，N1是N2的祖先，则N1和N2满足上述两个序列的前后关系。
第2个问题，不容易回答，因为当N1不是N2的祖先时，是否也能满足这种前后关系呢？
N1不是N2的祖先，分为两种情况：一是N2是N1的祖先；二是N2是N1的兄弟树的结点，而第二种
情况又要分两种：①N1是在左，N2在右；②N1在右，N2在左。
情况    N1是N2的祖先        N2是N1的祖先        N1在左，N2在右      N2在左，N1在右
前序       N1...N2             N2...N1              N1...N2             N2...N1
后序       N2...N1             N1...N2              N1...N2             N2...N1
后三组结果与第一组结果都不能完全相同，也就是说除了N1是N2祖先的情况，没有其它任何
情况可以产生上面的二个序列了，也就回答了第二个问题。
通过以上这些情况，可以看出前序和后序可以确定N1是否为N2的祖先。
#include<stdio.h>
int judge(char pre[],char post[],char ch1,char ch2)
{//pre[]代表前序序列，post[]代表后序序列，函数用检验ch1是否为ch2的祖先
    int i,k1=0,k2=0,flag=0;         //k1、k2分别用来记录字符ch2在前序和后序中位置
    while(pre[k1]!=ch2)  k1++;      //flag用来标识进行判断ch1是否是ch2的祖先
    while(post[k2]!=ch2) k2++;
    for(i=0;i<k1;i++)
    {
        if(pre[i]==ch1)
        {
            flag = 1;               //如果ch1在ch2的前面找到，则先假设ch1是ch2的祖先
            break;
        }
    }
    if(!flag)   return flag;        //如果ch1不在ch2前面，则返回
    else
    {
        flag = 0;                       //将flag重新赋值为0
        for(i=k2+1;post[i]!='\0';i++)   //进一步进行判断
            if(post[i]==ch1)
            {
                flag = 1;
                break;
            }
        return flag;
    }
}

void main()
{
    int i=0;
    char ch1,ch2,pre[100] = {"abdecfg"},post[100] = {"debfgca"};
    printf("请输入前序序列:");
    //gets(pre);
    puts(pre);
    printf("请输入后序序列:");
    //gets(post);
    puts(post);
    printf("请输入要查询的字符N1和N2(形式:N1,N2):");
    scanf("%c,%c",&ch1,&ch2);
    i = judge(pre,post,ch1,ch2);
    if(i)
        printf("%c是%c的祖先\n",ch1,ch2);
    else
        printf("%c不是%c的祖先\n",ch1,ch2);

南京师范大学2008年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）
（1）一个数如果恰好等于它的因子之和，这个数就称为“完数”，6的因子为1、2、3，而
6＝1+2+3，因此6是“完数”。编程找出1000之内的所有“完数”。（本题15分）
参考解法：
#include<stdio.h>
void main()
{
    int i,n,s;
    for(n=1;n<1000;n++)
    {
         s = 0;
         for(i=1;i<n;i++)
         {
            if(n%i==0) s += i;
         }
         if(n==s)   printf("%d is a perfect number.\n",n);
    }
}

（2）采用顺序结构存储串，编写一个函数Substring(s1,s2)，用于判定s2是否s1的子串。
（本题15分）
参考解法：
#include<stdio.h>
int SubString(char *s1,char *s2)
{
    char *p,*q,*r;
    p = s1;
    while(*p)
    {
        q = p;