二叉树构造、线索二叉树、哈夫曼树、并查集

绝地灬酷狼 2023-08-17 15:15 88阅读 0赞

中序先序构造

BTNode* CreateBT(char* pre, char* in, int n)
    {
    	char* p;
    	BTNode* b;
    	int k;
    	if (n <= 0)
    		return NULL;
    	b = (BTNode*)malloc(sizeof(BTNode));
    	b->data = *pre;
    	for (p = in; p < in + n; p++)
    	{
    		if (*p == *pre)
    			break;
    	}
    	k = p - in;
    	b->lchild = CreateBT(pre+1, in, k);
    	b->rchild = CreateBT(pre + k + 1, p+1, n - k - 1);
    	return b;
    }

中序后序构造

BTNode* CreateBT2(char* in, char* post, int n)
    {
    	int k;
    	char* p;
    	BTNode* b = (BTNode*)malloc(sizeof(BTNode));
    	if (n <= 0)
    		return NULL;
    	b->data = *(post + n - 1);
    	for (p = in; p < in + n; p++)
    	{
    		if (*p == *(post + n - 1))
    			break;
    	}
    	k = p - in;
    	b->lchild = CreateBT2(in, post, k);
    	b->rchild = CreateBT2(p + 1, post + k, n - k - 1);
    	return b;
    }

线索二叉树（中序）

typedef struct node {
    	ElemType data;
    	int ltag, rtag;
    	struct node* lchild;
    	struct node* rchild;
    }TBTNode;

TBTNode* pre;
    void Thread(TBTNode*& p)
    {
    	if (p != NULL)
    	{
    		Thread(p->lchild);
    		if (p->lchild == NULL)
    		{
    			p->lchild = pre;
    			p->ltag = 1;
    		}
    		else
    			p->ltag = 0;
    		if (pre->rchild == NULL)
    		{
    			pre->rchild = p;
    			pre->rtag = 1;
    		}
    		else
    			pre->rtag = 0;
    		pre = p;
    		Thread(p->rchild);
    		
    	}
    }
    TBTNode* CreateThread(TBTNode* b)
    {
    	TBTNode* root;
    	root = (TBTNode*)malloc(sizeof(TBTNode));
    	root->ltag = 0;
    	root->rtag = 1;
    	root->rchild = b;
    	if (b == NULL)
    	{
    		root->lchild = root;
    	}
    	else
    	{
    		root->lchild = b;
    		pre = root;
    		Thread(b);
    		root->rchild = pre;
    		pre->rtag = 1;
    		pre->rchild = root;
    	}
    	return root;
    }

遍历

void ThInOrder(TBTNode* b)
    {
    	TBTNode* p = b->lchild;
    	while (p != b)
    	{
    		
    		while (p->ltag == 0)
    			p = p->lchild;
    		printf("%c", p->data);
    		while (p->rtag == 1 && p->rchild != b)
    		{
    			p = p->rchild;
    			printf("%c", p->data);
    		}
    
    		p = p->rchild;
    	}
    }

哈夫曼树//未验证

构造

typedef struct {
    	char data;
    	double weight;
    	int parent;
    	int lchild;
    	int rchild;
    }HTNode;

void CreatHT(HTNode ht[], int n0)
    {
    	int lnode;
    	int rnode;
    	double min1, double min2;
    	int i, j;
    	for (i = 0; i < 2 * n0 - 1; i++)
    	{
    		ht[i].parent = ht[i].rchild = ht[i].lchild = -1;
    	}
    	for (i = n0; i < 2 * n0 - 1; i++)
    	{
    		min1 = min2 = 32767;
    		lnode = rnode = -1;
    		for (j = 0; j < i; j++)
    		{
    			if (ht[j].parent == -1)
    			{
    				if (ht[j].weight < min1)
    				{
    					min2 = min1;
    					rnode = lnode;
    					min1 = ht[j].weight;
    					lnode = j;
    				}
    				if (ht[j].weight < min2)
    				{
    					min2 = ht[j].weight;
    					rnode = j;
    				}
    			}
    		}
    		ht[i].weight = min1 + min2;
    		ht[i].lchild = lnode;
    		ht[i].rchild = rnode;
    		ht[lnode].parent = ht[rnode].parent = i;
    	}
    }

哈夫曼编码

void CreateHCode(HCode hcd[], HTNode ht[], int n0)
    {
    	int i, f, c;
    	HCode hc;
    	for (i = 0; i < n0; i++)
    	{
    		hc.start = n0;
    		f = ht[i].parent;
    		c = i;
    		while (f != -1)
    		{
    			if (ht[f].lchild == c)
    				hc.cd[hc.start--] = '0';
    			else
    				hc.cd[hc.start--] = '1';
    			c = f;
    			f = ht[f].parent;
    		}
    		hc.start++;
    		hcd[i] = hc;		
    	}
    }

并查集

typedef struct {
    	int data;
    	int rank;
    	int parent;
    }UFSTree;

初始化

void Make_set(UFSTree t[], int n)
    {
    	for (int i = 1; i <= n; i++)
    	{
    		t[i].data = i;
    		t[i].rank = 0;
    		t[i].parent = i;
    	}
    }

查找一个元素所属集合

int Find_set(UFSTree t[], int x)
    {
    	if (x != t[x].parent)
    		return Find_set(t, t[x].parent);
    	else
    		return x;
    }

两个元素各自所属的集合合并

void Union(UFSTree t[],int x, int y)
    {
    	int X = Find_set(t, x);
    	int Y = Find_set(t, y);
    	if (t[X].rank > t[Y].rank)
    		t[Y].parent = X;
    	else
    	{
    		t[X].parent = Y;
    		if (t[X].rank == t[Y].rank)
    			t[Y].rank++;
    	}
    }

转载于:https://www.cnblogs.com/KIROsola/p/11440002.html