树的代码实现

第一部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <stdlib.h>

typedef struct BiTree
{
    char data;
    struct BiTree *lchild;
    struct BiTree *rchild;
}BiTree, *BiNode;

BiNode CreatBiTree(BiNode T)
{
    char ch;
    scanf("%c", &ch);
    if(ch == '#')
    {
        T = NULL;
    }
    else
    {
        T = (BiNode)malloc(sizeof(BiTree));
        T->data = ch;
        T->lchild = CreatBiTree(T->lchild);
        T->rchild = CreatBiTree(T->rchild);
    }
    return T;
}


void PreBiTree(BiNode T)
{
    if(T)
    {
        printf("%c", T->data);
        PreBiTree(T->lchild);
        PreBiTree(T->rchild);
    }
}

BiNode Copy(BiNode T, BiNode P)
{
    if(T == NULL)
    {
        return NULL;
    }
    else
    {
        P = (BiNode)malloc(sizeof(BiTree));
        P->data = T->data;
        P->lchild = Copy(T->lchild, P->lchild);
        P->rchild = Copy(T->rchild, P->rchild);
    }
    return P;
}
int Depth(BiTree *T)
{
    int m, n;
    m = n = 0;
    if(T == NULL)
    {
        return 0;
    }
    else
    {
        m = Depth(T->lchild);
        n = Depth(T->rchild);
        if( m > n)
        {
            return (m+1);
        }
        else
        {
            return (n+1);
        }
    }
}

int BNumber(BiNode T)
{
    int m, n;
    if(T==NULL)
    {
        return 0;
    }
    else
    {
        m = BNumber(T->lchild);
        n = BNumber(T->rchild);
        return m+n + 1;
    }
}

int LeafCount(BiNode T)
{
    if(T == NULL)
    {
        return 0;
    }
    if( T->lchild == NULL && T->rchild == NULL)
    {
        return 1;
    }
    else
    {
        return LeafCount(T->lchild) + LeafCount(T->rchild);
    }
}

int main()
{
    int m;
    // ABC##DE#G##F###
    BiNode T;
    T = CreatBiTree(T);
    PreBiTree(T);

    m = Depth(T);
    printf("%d\n", m);

    m = BNumber(T);
    printf("%d\n", m);
    m = LeafCount(T);
    printf("%d\n", m);

}

第二部分—（哈夫曼树）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
    int weight;
    int parent, lch, rch;
}HTNode, *HuffmanTree;

HuffmanTree CreatHTree(HuffmanTree HT)
{
    int n, m, i, min1, min2; 
    printf("请输入初始结点数目:\t");
    scanf("%d", &n);
    
    if( n < 1)
    {
        return NULL;
    }
    
    HT = (HuffmanTree)malloc(sizeof(HTNode)*m+1);
    
    m = 2*n - 1;
    
    for( i = 1; i <= m; i++)
    {
        HT[i].lch = 0;
        HT[i].parent = 0;
        HT[i].rch = 0;
        HT[i].weight = 0;
    }
    
    for( i = 1; i <= n; i++)
    {
        scanf("%d", &HT[i].weight); 
    }
    // 5 29 7 8 14 23 3 11
    for( i = n + 1; i <= m; i++ )
    {
        min1 = 1;
        min2 = 1;
        search(HT, &min1 ,&min2, i-1);
        HT[i].weight = HT[min1].weight + HT[min2].weight;
        HT[min1].parent = i;
        HT[min2].parent = i;
        HT[i].lch = min1;
        HT[i].rch = min2;
    }
    for( i = 1; i <= m; i++ )
    {
        printf("%d个的权重为%d\n",i, HT[i].weight);
    }
    return HT;
}

void search(HuffmanTree HT, int *min1, int *min2, int i)
{
    int small1 = 10000000, small2 = 10000000, p1 = 0, p2 = 0, n;
    for(n = 1; n <= i; n++)
    {
        if( HT[n].parent == 0)
        {
            if(HT[n].weight < small1)
            {
                small2 = small1;
                small1 = HT[n].weight;
                p2 = p1;
                p1 = n;    
            } 
            else if( HT[n].weight < small2)
            {
                small2 = HT[n].weight;
                p2 = n;
            }
        }
    }
    *min1 = p1;
    *min2 = p2;
}

int main()
{
    HuffmanTree HT;
    HT = CreatHTree(HT);
}

第三部分—（哈夫曼树的应用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{ 
	float weight;
	int parent, lch,rch; 
	char data;
	char *num;
}HTree, *HuffmanTree;

HuffmanTree CreatHTree(HuffmanTree HT, int n)
{
	int i, m;
	m = 2*n-1;
	
	HT = (HuffmanTree)malloc(sizeof(HTree)*(m+1));
	for( i = 1; i <= m; i++)
	{
		HT[i].lch = 0;
		HT[i].parent = 0;
		HT[i].rch = 0;
		HT[i].weight = 0;
	}
	printf("请输入各个字母和字母的权重："); 
	for(i = 1; i <= n; i++)
	{
		getchar();
		scanf("%c", &HT[i].data);
		scanf("%f",&HT[i].weight);
	}
	
	for( i = n+1; i <= m; i++)
	{
		int min1, min2;
		search(HT, &min1,&min2, i-1);
		HT[min1].parent = i;
		HT[min2].parent = i;
		HT[i].lch = min1;
		HT[i].rch = min2;
		HT[i].weight = HT[min1].weight+HT[min2].weight;
	}
	for(i = 1; i <= m; i++)
	{
		printf("%f\n", HT[i].weight);
	}
	return HT;
}

void search(HuffmanTree HT, int *min1, int *min2, int i)
{
	int z, k = 0, p, q;
	float small1 = 1000000, small2 = 1000000;
	
	for( z = 1; z <= i; z++)
	{
		if( HT[z].parent == 0)
		{
			if( HT[z].weight <= small1 )
			{
				small2 = small1;
				small1 = HT[z].weight;
				p = q;
				q = z;
			}
			else if(HT[z].weight <= small2)
			{
				small2 = HT[z].weight;
				p = z;
			}
		}
	}
	*min1 = p;
	*min2 = q;
}


void  HtreeCode(HuffmanTree HT, int n)
{
	int m, p, start, k;
	char cd[n];
	cd[n-1] = '\0';
	for( m = 1; m <= n; m++ )
	{
		start = n-1;
		k = m;
		p = HT[k].parent;
		while( p )
		{
			start--;
			if( HT[p].lch == k)
			{
				cd[start] = '1';
			}
			else
			{
				cd[start] = '0';
			}
			k = p;
			p = HT[p].parent;
		}
		HT[m].num = (char *)malloc(sizeof(char)*(n-start));
		strcpy(HT[m].num, &cd[start]);
	}
}

int main()
{
	HuffmanTree HT;
	int n, m, i, k,p, q;
	printf("请输入要添加的个数: ");
	scanf("%d", &n);
	if( n < 1)
	{
		return NULL;
	}

	HT = CreatHTree(HT, n);
	HtreeCode(HT,  n);
	for(i = 1; i <= n; i++)
	{
		printf("%s\n", HT[i].num);
	}
	
	
}