数据结构OJ实验8-赫夫曼树编码及应用

2024-01-03 13:31:22

A. DS二叉树--赫夫曼树的构建与编码

题目描述

给定n个权值,根据这些权值构造huffman树,并进行huffman编码

大家参考课本算法6.12为主,注意数组访问是从位置1开始

要求:赫夫曼的构建中,默认左孩子权值不大于右孩子权值

输入

第一行先输入n,表示有n个权值,即有n个叶子

第二行输入n个权值,权值全是小于1万的正整数

输出

逐行输出每个权值对应的编码,格式如下:权值-编码
即每行先输出1个权值,再输出一个短划线,再输出对应编码

接着下一行输出下一个权值和编码,以此类推

样例查看模式?

正常显示查看格式

输入样例1?

5
15?4?4?3?2

输出样例1

15-1
4-010
4-011
3-001
2-000

AC代码
#include<iostream>
using namespace std;
struct Hatnode
{
    int parent, left, right, weight;
    string code;
    int data;
    Hatnode()
    {
        parent = 0;
        left = 0;
        right = 0;
    }
};
class Hatree
{
    Hatnode* root;
    int num;
public:
    Hatree(int n = 0)
    {
        num = n;
        root = new Hatnode[2 * n];
        for (int i = 1; i <= n; i++)
        {
            root[i].data = i;
            cin >> root[i].weight;
        }
    }
    void selectMin(int len, int& p1, int& p2)
    {
        int min1, min2;
        min1 = min2 = 10000;
        p1 = p2 = 0;
        for (int i = 1; i < len; i++)
        {
            if (root[i].parent == 0)
            {
                if (root[i].weight < min1)
                {
                    min2 = min1;
                    p2 = p1;
                    min1 = root[i].weight;
                    p1 = i;
                }
                else if (root[i].weight < min2)
                {
                    min2 = root[i].weight;
                    p2 = i;
                }
            }
        }
    }
    void createtree()
    {
        int p1 = 0, p2 = 0;
        for (int i = num + 1; i < 2 * num; i++)
        {
            selectMin(i, p1, p2);
            root[i].left = p1;
            root[i].right = p2;
            root[p1].parent = root[p2].parent = i;
            root[i].weight = root[p1].weight + root[p2].weight;
        }
    }
    void hacode()
    {
        for (int i = 1; i <= num; i++)
        {
            for (int c = i, f = root[i].parent; f != 0; c = f, f = root[f].parent)
            {
                if (root[f].left == c)
                {
                    (root + i)->code = '0' + (root + i)->code;
                }
                else
                {
                    (root + i)->code = '1' + (root + i)->code;
                }
            }
        }
    }
    void Code()
    {
        for (int i = 1; i <= num; i++)
        {
            cout << (root + i)->weight << "-" << (root + i)->code << endl;
        }
    }
};
int main()
{
    int n;
    cin >> n;
    Hatree tree(n);
    tree.createtree();
    tree.hacode();
    tree.Code();
    return 0;
}

B. DS二叉树--赫夫曼树解码

题目描述

已知赫夫曼编码算法和程序,在此基础上进行赫夫曼解码

可以增加一个函数:int ?Decode(const string codestr, char txtstr[]);//输入编码串codestr,输出解码串txtstr

该方法如果解码成功则返回1,解码失败则返回-1,本程序增加宏定义ok表示1,error表示-1

赫夫曼解码算法如下:

定义指针p指向赫夫曼树结点,指针i指向编码串,定义ch逐个读取编码串的字符

初始操作包括读入编码串str,设置p指向根结点,i为0表示指向串首,执行以下循环:

1)取编码串的第i个字符放入ch

2)如果ch是字符0,则p跳转到左孩子;如果ch是字符1,则p跳转到右孩子;如果ch非0非1,表示编码串有错误,报错退出

3)如果p指的结点是叶子,输出解码字符,p跳回根结点,i++,跳步骤1

4)如果p指的结点不是叶子且i未到编码串末尾,i++,跳步骤1

5)如果p指的结点不是叶子且i到达编码串末尾,报错退出

当i到达编码串末尾,解码结束。

输入

第一行先输入n,表示有n个叶子

第二行输入n个权值,权值全是小于1万的正整数
第三行输入n个字母,表示与权值对应的字符
第四行输入k,表示要输入k个编码串
第五行起输入k个编码串

输出

每行输出解码后的字符串,如果解码失败直接输出字符串“error”,不要输出部分解码结果

样例查看模式?

正常显示查看格式

输入样例1?

5
15?4?4?3?2
A?B?C?D?E
3
11111
10100001001
00000101100

输出样例1

AAAAA
ABEAD
error

AC代码
#include<iostream>
using namespace std;
struct Hatnode
{
    int parent, left, right, weight;
    string code;
    char data;
    Hatnode()
    {
        parent = 0;
        left = 0;
        right = 0;
    }
};
class Hatree
{
    Hatnode* root;
    int num;
public:
    Hatree(int n = 0)
    {
        num = n;
        root = new Hatnode[2 * n];
        for (int i = 1; i <= n; i++)
        {
            cin >> root[i].weight;
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> root[i].data;
        }
    }
    void selectMin(int len, int& p1, int& p2)
    {
        int min1, min2;
        min1 = min2 = 10000;
        p1 = p2 = 0;
        for (int i = 1; i < len; i++)
        {
            if (root[i].parent == 0)
            {
                if (root[i].weight < min1)
                {
                    min2 = min1;
                    p2 = p1;
                    min1 = root[i].weight;
                    p1 = i;
                }
                else if (root[i].weight < min2)
                {
                    min2 = root[i].weight;
                    p2 = i;
                }
            }
        }
    }
    void createtree()
    {
        int p1 = 0, p2 = 0;
        for (int i = num + 1; i < 2 * num; i++)
        {
            selectMin(i, p1, p2);
            root[i].left = p1;
            root[i].right = p2;
            root[p1].parent = root[p2].parent = i;
            root[i].weight = root[p1].weight + root[p2].weight;
        }
    }
    void hacode()
    {
        for (int i = 1; i <= num; i++)
        {
            for (int c = i, f = root[i].parent; f != 0; c = f, f = root[f].parent)
            {
                if (root[f].left == c)
                {
                    (root + i)->code = '0' + (root + i)->code;
                }
                else
                {
                    (root + i)->code = '1' + (root + i)->code;
                }
            }
        }
    }
    int  Decode(const string s, string& ans)
    {
        int ed = 2 * num - 1;
        int st = ed;
        bool flag = 1;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '0')
            {
                st = root[st].left;
            }
            else if (s[i] == '1')
            {
                st = root[st].right;
            }
            else
            {
                return -1;
            }
            if (root[st].left == 0 && root[st].right == 0)
            {
                ans += root[st].data;
                st = ed;
                flag = 1;
            }
            else
            {
                flag = 0;
            }
        }
        if (!flag)
        {
            return-1;
        }
        return 1;
    }
};
int main()
{
    int n;
    cin >> n;
    Hatree tree(n);
    tree.createtree();
    tree.hacode();
    cin >> n;
    while (n--)
    {
        string s;
        cin >> s;
        string res;
        if (tree.Decode(s, res) == -1)
        {
            cout << "error" << endl;
        }
        else
        {
            cout << res << endl;
        }
    }
    return 0;
}

C. DS树--带权路径和

题目描述

二叉树的创建使用含空树表示的先序遍历序列,计算一棵二叉树的带权路径总和,即求赫夫曼树的带权路径和。

已知一棵二叉树的叶子权值,该二叉树的带权路径和WPL等于叶子权值乘于根节点到叶子的分支数,然后求总和。

如下图中,叶子都用大写字母表示,权值对应为:A-7,B-6,C-2,D-3

树的带权路径和 = 7*1 + 6*2 + 2*3 + 3*3 = 34

输入

第一行输入一个整数t,表示有t个二叉树

第二行输入一棵二叉树的先序遍历结果,空树用字符‘0’表示,注意输入全是英文字母和0,其中大写字母表示叶子

第三行先输入n表示有n个叶子,接着输入n个数据表示n个叶子的权值,权值的顺序和前面输入的大写字母顺序对应

以此类推输入下一棵二叉树

输出

输出每一棵二叉树的带权路径和

样例查看模式?

正常显示查看格式

输入样例1?

2
xA00tB00zC00D00
4?7?6?2?3
ab0C00D00
2?10?20

输出样例1

34
40

AC代码
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	int weight;//权重
	int depth;//记录层数
	node(char d, node* ll = NULL, node* rr = NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	//再建树中赋值层数
	void Create(node*& n,int dep=0)
	{
		char ch;
		cin >> ch;
		if (ch == '0')
		{
			n = NULL;
			return;
		}
		n = new node(ch);
		n->depth = dep;
		Create(n->l,dep+1);
		Create(n->r,dep+1);//加一操作
	}
	void inweight(node* n)
	{
		if (!n)return;
		//只有叶子有权值
		if (!n->l && !n->r)
		{
			cin >> n->weight;
		}
		inweight(n->l);
		inweight(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
	void Child(node* n)
	{
		if (!n)return;
		if (!n->l && !n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
	int high(node* n)
	{
		if (!n)return 0;
		int lefth = high(n->l);
		int righth = high(n->r);
		return max(lefth, righth) + 1;
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
		cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
	void lerorder()
	{
		queue<node*>q;
		q.push(root);
		while (!q.empty())
		{
			auto t = q.front();
			q.pop();
			if (!t)continue;
			cout << t->data;
			q.push(t->l);
			q.push(t->r);
		}
		cout << endl;
	}
	void gethigh()
	{
		cout << high(root) << endl;
	}
	void input_weight()
	{
		int n;
		cin >> n;
		inweight(root);
	}
    //计算带权路径和
	int count_path()
	{
		//使用栈计算
		int ans = 0;
		stack<node*>s;//s存结点
		s.push(root);
		while (!s.empty())
		{
			node* cur = s.top();
			s.pop();
			if (!cur)continue;
			s.push(cur->l);
			s.push(cur->r);
			//到叶子了
			if (!cur->l && !cur->r)
			{
				ans += cur->depth * cur->weight;
			}
		}
		return ans;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.input_weight();
		cout << tt.count_path() << endl;
	}
	return 0;
}

D. DS树--二叉树之最大路径

题目描述

给定一颗二叉树的逻辑结构(先序遍历的结果,空树用字符‘0’表示,例如AB0C00D00),建立该二叉树的二叉链式存储结构

二叉树的每个结点都有一个权值,从根结点到每个叶子结点将形成一条路径,每条路径的权值等于路径上所有结点的权值和。编程求出二叉树的最大路径权值。如下图所示,共有4个叶子即有4条路径,

路径1权值=5 + 4 + 11 + 7 = 27路径2权值=5 + 4 + 11 + 2 = 22

路径3权值=5 + 8 + 13 = 26路径4权值=5 + 8 + 4 + 1 = 18

可计算出最大路径权值是27。

该树输入的先序遍历结果为ABCD00E000FG00H0I00,各结点权值为:

A-5,B-4,C-11,D-7,E-2,F-8,G-13,H-4,I-1

输入

第一行输入一个整数t,表示有t个测试数据

第二行输入一棵二叉树的先序遍历,每个结点用字母表示

第三行先输入n表示二叉树的结点数量,然后输入每个结点的权值,权值顺序与前面结点输入顺序对应

以此类推输入下一棵二叉树

输出

每行输出每棵二叉树的最大路径权值,如果最大路径权值有重复,只输出1个

样例查看模式?
正常显示

输入样例1?

AB0C00D00
4?5?3?2?6
ABCD00E000FG00H0I00
9?5?4?11?7?2?8?13?4?1

输出样例1

11
27
AC代码
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	int weight;//权重
	int depth;//记录层数
	node(char d, node* ll = NULL, node* rr = NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	//再建树中赋值层数
	void Create(node*& n,int dep=0)
	{
		char ch;
		cin >> ch;
		if (ch == '0')
		{
			n = NULL;
			return;
		}
		n = new node(ch);
		n->depth = dep;
		Create(n->l,dep+1);
		Create(n->r,dep+1);//加一操作
	}
	void inweight(node* n)
	{
		if (!n)return;
		//只要是结点都有权值
		cin >> n->weight;
		inweight(n->l);
		inweight(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
	void Child(node* n)
	{
		if (!n)return;
		if (!n->l && !n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
	int high(node* n)
	{
		if (!n)return 0;
		int lefth = high(n->l);
		int righth = high(n->r);
		return max(lefth, righth) + 1;
	}
	//最大路径为根节点到叶子的一条路径,路径的权值等于路径上所有结点的权值和
	int maxpath(node* n)
	{
		if (!n)return 0;
		int left_maxpath = maxpath(n->l);
		int right_maxpath = maxpath(n->r);
		return n->weight + max(left_maxpath, right_maxpath);
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
		cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
	void lerorder()
	{
		queue<node*>q;
		q.push(root);
		while (!q.empty())
		{
			auto t = q.front();
			q.pop();
			if (!t)continue;
			cout << t->data;
			q.push(t->l);
			q.push(t->r);
		}
		cout << endl;
	}
	void gethigh()
	{
		cout << high(root) << endl;
	}
	void input_weight()
	{
		int n;
		cin >> n;
		inweight(root);
	}
    //计算带权路径和
	int count_path()
	{
		//使用栈计算
		int ans = 0;
		stack<node*>s;//s存结点
		s.push(root);
		while (!s.empty())
		{
			node* cur = s.top();
			s.pop();
			if (!cur)continue;
			s.push(cur->l);
			s.push(cur->r);
			//到叶子了
			if (!cur->l && !cur->r)
			{
				ans += cur->depth * cur->weight;
			}
		}
		return ans;
	}
	int max_path()
	{
		return maxpath(root);
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.input_weight();
		cout << tt.max_path() << endl;
	}
	return 0;
}

E. DS二叉树—二叉树镜面反转

题目描述

假设二叉树用二叉链表存储,用含空子树遍历的先序序列结果创建。空子树用字符#表示

输入二叉树的先序序列,请你先创建二叉树,并对树做个镜面反转,再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。

--程序要求--

程序中不允许使用STL库等第三方对象或函数实现本题的要求

输入

测试次数t

每组测试数据是一个二叉树的先序遍历序列,#表示空树

输出

对每棵二叉树,输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树,输出四个NULL(后面不加空格,每个NULL独自一行,中间没有空行)。如下:

NULL

NULL

NULL

NULL

样例查看模式?

正常显示查看格式

输入样例1?

3
41#32###65##7##
AB#C##D##
AB##C##

输出样例1

4?6?7?5?1?3?2?
7?6?5?4?3?2?1?
7?5?6?2?3?1?4?
4?6?1?7?5?3?2?
A?D?B?C?
D?A?C?B?
D?C?B?A?
A?D?B?C?
A?C?B?
C?A?B?
C?B?A?
A?C?B?

AC代码
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d, node* ll = NULL, node* rr = NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)
	{
		char ch;
		cin >> ch;
		if (ch == '#')
		{
			n = NULL;
			return;
		}
		n = new node(ch);
		//只需修改这里,交换左右孩子即可
		Create(n->r);
		Create(n->l);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data<<" ";
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data<<" ";
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data<<" ";
	}
	void Child(node* n)
	{
		if (!n)return;
		if (!n->l && !n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
	int high(node* n)
	{
		if (!n)return 0;
		int lefth = high(n->l);
		int righth = high(n->r);
		return max(lefth, righth) + 1;
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
		cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
	void lerorder()
	{
		queue<node*>q;
		q.push(root);
		while (!q.empty())
		{
			auto t = q.front();
			q.pop();
			if (!t)continue;
			cout << t->data<<" ";
			q.push(t->l);
			q.push(t->r);
		}
		cout << endl;
	}
	void gethigh()
	{
		cout << high(root) << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.preorder();
		tt.midorder();
		tt.posorder();
		tt.lerorder();
	}
	return 0;
}

文章来源:https://blog.csdn.net/gyeolhada/article/details/135325401
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。