5-1

#include <iostream>
using namespace std;

typedef char ElemType;  //¶¨Òå¶þ²æÊ÷½áµãÖµµÄÀàÐÍΪ×Ö·ûÐÍ
typedef struct BiTNode
{
//====²¹³ä´úÂë====
    ElemType data;
    BiTNode *left, *right;
}BiTNode, *BiTree;

int LEAFCOUNT=0;
int NODECOUNT=0;

//°´ÏÈÐò´ÎÐòÊäÈ룬ÒÔÌØÊâ×Ö·û±íʾ¿ÕÊ÷
void CreateBiTree(BiTree &T)
{
//====²¹³ä´úÂë====
    char ch;
    cin >> ch;
    if (ch != '#') {
    	T = new BiTNode;
    	T->data = ch;
    	CreateBiTree(T->left);
    	CreateBiTree(T->right);
	}
	else T = NULL;
}

//ÏÈÐò±éÀú 
void PreOrderTraverse(BiTree T)
{
//====²¹³ä´úÂë====
	if (T) {
		cout << T->data << " ";
		PreOrderTraverse(T->left);
		PreOrderTraverse(T->right);
	}
}

//ÖÐÐò±éÀú 
void InOrderTraverse(BiTree T)
{
//====²¹³ä´úÂë====
	if (T) {
		InOrderTraverse(T->left);
		cout << T->data << " ";
		InOrderTraverse(T->right);
	}
}

//ºóÐò±éÀú
void PostOrderTraverse(BiTree T)
{
//====²¹³ä´úÂë====
	if (T) {
		PostOrderTraverse(T->left);
		PostOrderTraverse(T->right);
		cout << T->data << " ";
	}
}

//Çó¶þ²æÊ÷µÄÉî¶È
int BTDepth(BiTree T)
{
//====²¹³ä´úÂë====
    if (T == NULL) return 0;
    int LeftDepth = BTDepth(T->left);
    int RightDepth = BTDepth(T->right);
    return max(LeftDepth, RightDepth) + 1;
}

//Çó¶þ²æÊ÷µÄÒ¶×ÓÊý, ʹÓÃÈ«¾Ö±äÁ¿
void Leaf(BiTree T)
{
//====²¹³ä´úÂë====
    if (T) {
    	if (!T->left && !T->right) {
    		LEAFCOUNT ++;
		}
		Leaf(T->left);
		Leaf(T->right);
	}
}
  
void NodeCount(BiTree T)//Çó¶þ²æÊ÷µÄ½áµã×ÜÊý, ʹÓÃÈ«¾Ö±äÁ¿
{
//====²¹³ä´úÂë====
    if (T) {
    	NODECOUNT ++;
    	NodeCount(T->left);
    	NodeCount(T->right);
	}
}

int main()
{
    BiTree T=NULL;
    int select;
    while(cin>>select)
    {
  
        switch(select)
        {
            case 0: 
                return 0;
            case 1:
                cin.clear();//Çå¿ÕÊäÈë
                CreateBiTree(T);
                break;
            case 2:
                if(T) {
                    PreOrderTraverse(T); 
                    cout<<endl;
                }
                break;
            case 3:
                if(T) {
                    InOrderTraverse(T);
                    cout<<endl;
                }
                break;
            case 4:
                if(T) {
                    PostOrderTraverse(T);
                    cout<<endl;
                }
                break;
            case 5:
		cout<<BTDepth(T)<<endl;
                break;
            case 6:
                LEAFCOUNT=0;
                Leaf(T);
                cout<<LEAFCOUNT<<endl;
                break;
            case 7:
                NODECOUNT=0;
                NodeCount(T);
                cout<<NODECOUNT<<endl;
                break;
          }
    }
    return 0; 
}

5-2

#include<iostream>
#include<string.h>
#define MAXSIZE 100
using namespace std;
typedef struct
{//¹þ·òÂüÊ÷½áµãµÄÐÎʽ
    int weight;               //½áµãµÄȨֵ
    int parent,lchild,rchild;  //½áµãµÄË«Çס¢×óº¢×Ó¡¢ÓÒº¢×ÓµÄϱê
}HTNode,*HuffmanTree;       //¶¯Ì¬·ÖÅäÊý×é´æ´¢¹þ·òÂüÊ÷
typedef char **HuffmanCode;   //¶¨Òå±àÂë±íÀàÐÍ
int Search(char a[],char ch)
{//²éÕÒÊý×éÖÐ×Ö·ûchËùÔÚµÄλÖ㬷µ»ØÊý×éϱ꣬·ñÔò·µ»Ø-1
    for(int i=0;a[i]!='\0';i++)
    {
        if(a[i]==ch) return i;
    }
    return -1;
}
void Sort(char a[],int b[],int len)
{//°´ASCIIÂëðÅÝÅÅÐò
	/**************begin************/
   for (int i = 0; i < len - 1; i ++) {
   		for (int j = 0; j < len - i - 1; j ++) {
   			if (a[j] > a[j + 1]) {
   				swap(a[j], a[j + 1]);
   				swap(b[j], b[j + 1]);
			}
		}
   }
    /**************end************/
}
void Select_min(HuffmanTree HT,int n,int &s1,int &s2)
{// ÔÚHT[k](1¡Ük¡Üi-1£©ÖÐÑ¡ÔñÁ½¸öÆäË«Ç×ÓòΪ0ÇÒȨֵ×îСµÄ½áµã£¬²¢·µ»ØËüÃÇÔÚHTÖеÄÐòºÅs1ºÍs2
	/**************begin************/
	s1 = s2 = 0;
	for (int i = 1; i <= n; i ++) {
		if (HT[i].parent == 0) {
			if (HT[i].weight < HT[s1].weight || s1 == 0) {
				s2 = s1;
				s1 = i;
			}
			else if (HT[i].weight < HT[s2].weight || s2 == 0) {
				s2 = i;
			}
		}
	}
    /**************end************/
}
int m;
void CreateHuffmanTree(HuffmanTree &HT,int n,int b[])
{//¹¹Ôì¹þ·òÂüÊ÷HT
	/**************begin************/
   int m = 2 * n - 1;
   HT = new HTNode[m + 1];
   for (int i = 1; i <= n; i ++) {
		HT[i].weight = b[i - 1];
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
   }
   for (int i = n + 1; i <= m; i ++) {
		HT[i].weight = 0;
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}
	for (int i = n + 1; i <= m; i ++) {
		int s1, s2;
		Select_min(HT, i - 1, s1, s2);
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
    /**************end************/
}
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{//´ÓÒ¶×Óµ½¸ùÄæÏòÇóÿ¸ö×Ö·ûµÄ¹þ·òÂü±àÂ룬´æ´¢ÔÚ±àÂë±íHCÖÐ
	/**************begin************/
	HC = new char*[n + 1];
	char* pwd = new char[n];
	pwd[n - 1] ='\0';
	for (int i = 1; i <= n; i ++) {
		int st = n - 1;
		int p = i;
		int f = HT[i].parent;
		while(f) {
			if (HT[f].lchild == p) {
				pwd[-- st] = '0';
			}
			else {
				pwd[-- st] = '1';
			}
			p = f;
			f = HT[f].parent;
		}
		HC[i] = new char[n - st];
		strcpy(HC[i], &pwd[st]);
	}
	delete[] pwd;
    /**************end************/
}
void CharFrequency(char ch[],char a[],int b[],int &j)
{//ͳ¼Æ´ÊƵ
	/**************begin************/
	for (int i = 0; i < strlen(ch); i ++) {
		int l = Search(a, ch[i]);
		if (l == -1) {
			a[j] = ch[i];
			b[j] = 1;
			j ++;
		}
		else b[l] ++;
	}
    /**************end************/
}
void PrintHT(HuffmanTree HT, int j)
{//Êä³ö¹þ·òÂüÊ÷µÄ´æ´¢½á¹¹µÄÖÕ̬
	/**************begin************/
	for (int i = 1; i <= 2 * j - 1; i ++) {
		cout << i << " " << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << "\n";
	}
    /**************end************/
}
void PrintHC(HuffmanCode HC,char a[],int j)
{//Êä³öÿ¸ö×Ö·ûµÄ¹þ·òÂü±àÂë
	/**************begin************/
	for (int i = 0; i < j; i ++) {
		cout << a[i] << ":" << HC[i + 1] << " ";
	}
	cout << "\n";
    /**************end************/
}
int main()
{
    char ch[MAXSIZE];
    int i,j;
    while(cin>>ch)
    {
        if(ch[0]=='0') break;
        HuffmanTree HT;
        char a[MAXSIZE]={'\0'};
        int b[MAXSIZE]={0};
        j=0;      //jͳ¼Æ²»Í¬×Ö·ûµÄÊýÁ¿
        CharFrequency(ch,a,b,j);   //ͳ¼Æ´ÊƵ
        Sort(a,b,j);     //°´ASCIIÂëðÅÝÅÅÐò
        for(i=0;a[i]!='\0';i++)   //Êä³öͳ¼Æ³öÀ´µÄ×Ö·ûºÍ³öÏÖƵÂÊ
        {
            if(a[i+1]!='\0')
                cout<<a[i]<<":"<<b[i]<<" ";
            else
                cout<<a[i]<<":"<<b[i]<<endl;
        }
        //¹¹Ôì¹þ·òÂüÊ÷
        CreateHuffmanTree(HT,i,b);    //¹¹Ôì¹þ·òÂüÊ÷HT
        PrintHT(HT, j);      //Êä³ö¹þ·òÂüÊ÷µÄ´æ´¢½á¹¹µÄÖÕ̬
        //¹þ·òÂü±àÂë
        HuffmanCode HC;    //±àÂë±íHC
        CreateHuffmanCode(HT,HC,j);
        PrintHC(HC,a,j);    //Êä³öÿ¸ö×Ö·ûµÄ¹þ·òÂü±àÂë
        int k;
        for(i=0;ch[i]!='\0';i++)    //Êä³ö±àÂëºóµÄ×Ö·û´®
        {
            for(k=0;k<j;k++)
            {
                if(ch[i]==a[k])
                    cout<<HC[k+1];
            }
        }
        cout<<endl;
        cout<<ch<<endl;//Êä³ö½âÂëºóµÄ×Ö·û´®£¨ÓëÊäÈëµÄ×Ö·û´®Ïàͬ£©
    }
    return 0;
}