資料結構與算法（四）樹C語言實作（帶源碼）

資料結構與算法（四）樹

1. 二叉樹的順序存儲及周遊

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

const int N = 100;

typedef struct node
{
	char data;
	struct node* lchild, * rchild;
}NODE, * PNODE;

PNODE q[N];
int hh, tt = -1;

PNODE initTree()
{
	//此處會造成記憶體洩漏，可以改為數組然後free，這樣寫會更清晰些。
	PNODE node0 = (PNODE)malloc(sizeof(NODE));
	PNODE node1 = (PNODE)malloc(sizeof(NODE));
	PNODE node2 = (PNODE)malloc(sizeof(NODE));
	PNODE node3 = (PNODE)malloc(sizeof(NODE));
	PNODE node4 = (PNODE)malloc(sizeof(NODE));
	PNODE node5 = (PNODE)malloc(sizeof(NODE));
	node0->data = 'A';
	node0->lchild = node1;
	node0->rchild = node2;
	node1->data = 'B';
	node1->lchild = node3;
	node1->rchild = NULL;
	node2->data = 'C';
	node2->lchild = node4;
	node2->rchild = node5;
	node3->data = 'D';
	node3->lchild = NULL;
	node3->rchild = NULL;
	node4->data = 'E';
	node4->lchild = NULL;
	node4->rchild = NULL;
	node5->data = 'F';
	node5->lchild = NULL;
	node5->rchild = NULL;

	return node0;
}

void PreOrder(PNODE bt)
{
	if (bt == NULL)
		return;
	printf("%c", bt->data);
	PreOrder(bt->lchild);
	PreOrder(bt->rchild);
}

void InOrder(PNODE bt)
{
	if (bt == NULL)
		return;
	InOrder(bt->lchild);
	printf("%c", bt->data);
	InOrder(bt->rchild);
}

void PostOrder(PNODE bt)
{
	if (bt == NULL)
		return;
	PostOrder(bt->lchild);
	PostOrder(bt->rchild);
	printf("%c", bt->data);
}

void LevelOrder(PNODE bt)
{
	q[++tt] = bt;
	while (tt >= hh)
	{
		PNODE Bt = q[hh];
		printf("%c",Bt->data);
		++hh;
		if (Bt->lchild != NULL) q[++tt] = Bt->lchild;
		if (Bt->rchild != NULL) q[++tt] = Bt->rchild;
	}
}

int Countleaf(PNODE bt)
{
	int n, m;
	if (!bt) return 0;
	if (!bt->lchild && !bt->rchild) return 1;
	else
	{
		n = Countleaf(bt->lchild);
		m = Countleaf(bt->rchild);
		return n + m;
	}
}

int Deptth(PNODE bt)
{
	int n, m;
	if (!bt) return 0;
	if (!bt->lchild && !bt->rchild) return 1;
	else
	{
		n = Countleaf(bt->lchild);
		m = Countleaf(bt->rchild);
		return 1 + (m > n ? m : n);
	}
}

int main()
{
	printf("前序周遊：");
	PreOrder(initTree());
	printf("\n");
	printf("中序周遊：");
	InOrder(initTree());
	printf("\n");
	printf("後序周遊：");
	PostOrder(initTree());
	printf("\n");
	printf("層序周遊：");
	LevelOrder(initTree());
	printf("\n");
	printf("葉子節點數：");
	printf("%d", Countleaf(initTree()));
	printf("\n");
	printf("深度：");
	printf("%d\n", Deptth(initTree()));
	return 0;
}
           

1. 哈夫曼樹的實作及哈夫曼編碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define MAX 100

typedef struct node
{
	int weight;
	int parent;
	int lchild;
	int rchild;
	char data;
}NODE, * HaffmanTree;

typedef struct codenode
{
	int bit[MAX];
	int start;
}Code;

NODE* ht;

void preOrder(int n)
{
	printf("%c", ht[n].data);
	if (ht[n].lchild != -1) preOrder(ht[n].lchild);
	if (ht[n].rchild != -1) preOrder(ht[n].rchild);
}

void select(int n, int* S1, int* S2)
{
	int min1 = 2 ^ 32;
	int min2 = 2 ^ 32;

	for (int i = 0; i < n; ++i)
	{
		if (ht[i].parent == 0 && ht[i].weight < min1)
		{
			min1 = ht[i].weight;
			*S1 = i;
		}
	}
	for (int i = 0; i < n; ++i)
	{
		if (ht[i].parent == 0 && ht[i].weight < min2 && i != *S1)
		{
			min2 = ht[i].weight;
			*S2 = i;
		}
	}
}

void init_Tree(int n)
{
	ht = (node*)malloc(sizeof(node) * (2 * n - 1));
	int S1, S2;
	if (n < 1) return;
	for (int i = 0; i < 2 * n - 1; ++i)
	{
		ht[i].parent = 0;
		ht[i].lchild = -1;
		ht[i].rchild = -1;
		ht[i].data = NULL;
	}

	for (int i = 0; i < n; ++i)
	{
		printf("請輸入第%d個數字的權值: ", i + 1);
		scanf_s("%d", &ht[i].weight);
	}


	for (int i = 0; i < n; ++i)
	{
		printf("元素:");
		scanf_s(" %c", &ht[i].data);
	}

	for (int i = n; i < 2 * n - 1; ++i)
	{
		select(i, &S1, &S2);
		ht[S1].parent = i;
		ht[S2].parent = i;
		ht[i].weight = ht[S1].weight + ht[S2].weight;
		ht[i].lchild = S1;
		ht[i].rchild = S2;
		ht[i].data = '#';
	}
}
void HaffmanCode(int n)  //沒有按照字元串去寫，是一個個數字
{
	int i, j;
	init_Tree(n);
	preOrder(2 * n - 2);
	printf("\n");
	Code Code[100], cd;
	for (i = 0; i < n; ++i)
	{
		cd.start = n - 1;
		int c = i;
		int f = ht[c].parent;
		while (f != 0)
		{
			if (ht[f].lchild == c)
				cd.bit[cd.start]= 0;
			if (ht[f].rchild == c)
				cd.bit[cd.start] = 1;
			--cd.start;
			c = f;
			f = ht[c].parent;
		}

		for (j = cd.start; j < n; j++)
			Code[i].bit[j] = cd.bit[j];
		Code[i].start = cd.start;
	}

	for (i = 0; i < n; i++)
	{
		for (j = Code[i].start+1 ; j < n; j++)
			printf("%ld",Code[i].bit[j]);
		printf("\n");
	}

}

int main()
{
	int n;
	printf("請輸入您需要的節點數：");
	scanf_s("%d", &n);
	HaffmanCode(n);
	//preOrder(2 * n - 2);
}