InsertNode(h,s);
    }
}

BiTree FormHuffman(LinkList h)
{
    LNode *p,*q;
    BiNode *b;
    if(h==NULL || h->data==0) return NULL;
    else
    {
        while(h->data>1)
        {
            p = h->next;
            q = p->next;
            h->next = q->next;
            (h->data) = h->data - 2;
            if(!(b=(BiNode *)malloc(sizeof(BiNode))))   exit(0);
            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）依次输入表（30，15，28，20，24，10，12，68，35，50，46，55）中的元素，生成
一棵二叉排序树。（本题20分）
①试画出生成之后的二叉排序树；
②若该二叉树排序树中作中序遍历，试写出遍历序列；
③假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。
参考答案：
(1)
----------------------------------
------------------30--------------
--------15------------------68----
--10----------28--||--35----------
------12--20------||------50------
------------24----||----46--55----
----------------------------------
                                              30
                                             ↙↘
                      15                                              68
                     ↙↘                                            ↙↘
          10                      28                      35                      ⊙
         ↙↘                    ↙↘                    ↙↘                    ↙↘
    ⊙          12          20          ⊙                      50          ⊙          ⊙
  ↙  ↘      ↙  ↘      ↙  ↘      ↙  ↘      ↙  ↘      ↙  ↘      ↙  ↘      ↙  ↘
                                24                           46    55
(2)MidOrder:10,12,15,20,24,28,30,35,46,50,55,68
南京师范大学2006年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）
（1）设计一个程序，将任何输入的字符串中的最长单词输出，并计算出其在字符串中的位置。
（本题15分）
参考解法：
#include<stdio.h>
void main()
{
    int i,count=0,pos=0,maxlen=0;
    char ch;
    char s[80] = "what are you doing";
    //printf("input a string:");
    //gets(s);
    i = -1;
    do
    {
        i++;
        ch = s[i];
        if((ch>='A' && ch<='Z') || (ch>='a' && ch<='z'))
        {
            count++;
        }
        else
        {
            if(count>maxlen)
            {
                maxlen = count;
                pos = i-maxlen;
            }
            count = 0;
        }
    } while(s[i]!='\0');

    printf("The max length word is \"");
    for(i=0;i<maxlen;i++)
    {
        printf("%c",s[pos+i]);
    }
    printf("\" and it's position is %d.\n",pos+1);
}

（2）试采用递归函数实现将任意位数的整数转换为字符串输出，要求在主函数中输入整数
并调用递归函数实现转换并输出结果，对于负数也能处理。（本题15分）

参考解法：
#include<stdio.h>

void numtostring(int n,char a[],int k)