二叉树数据结构及哈夫曼树(C++代码)

二叉树数据结构及哈夫曼树(C++代码),第1张

二叉树数据结构及哈夫曼树(C++代码)

二叉树作为非线性数据结构,是以分支关系定义层次结构,以下重点为二叉树的存储结构及基本操作,以及树与二叉树之间的转化,最后介绍特殊的树结构——哈夫曼树。

目录

 二叉树的定义及基本操作

树与二叉树之间的转化

哈夫曼树


满二叉树:深度为k且含有(2^k)-1个结点的二叉树

完全二叉树:深度为k,有n个结点的二叉树,利用层次遍历,二叉树每一个结点与编号一一对应,如下图(b):

 存储方式:顺序存储(适合完全二叉树)和链式存储(又叫二叉链表)

 

 二叉树的定义及基本操作
#pragma once
#include
using namespace std;

const int ERROR = 0;
const int OK = 1;
typedef char ElemType;

class BiTNode
{

public:
	ElemType data;
	BiTNode* lchild;
	BiTNode* rchild;
};

class BiTree
{
public:
	BiTree();
	BiTNode* CreateBiTree();//先序创建二叉树
	
	BiTNode* GetRoot();//获得根结点
	int GetBiTNum();//获得结点个数


	void PreOrderTraverse(BiTNode* node);//先序遍历
	void InOrderTraverse(BiTNode *node);//中序遍历
	void PosOrderTraverse(BiTNode* node);//后序遍历

	BiTNode* Copy(BiTNode* node);//二叉树复制
	int Depth(BiTNode* node);//计算二叉树的深度
	int NodeCount(BiTNode* node);//计算结点个数
	int LeadCount(BiTNode* node); //计算叶子节点个数
	
	bool IsSymmetric();//判断一棵二叉树是否是对称二叉树
	bool IsSymmetrical(BiTNode* node1, BiTNode* node2);//两步走

	void DestoryBiTree(BiTNode* node);//销毁二叉树

private:
	BiTNode* root;                      //二叉树的根节点
	int m_size;                         //二叉树的大小
                                        //二叉树的深度
};

BiTree::BiTree()
{
	this->root = nullptr;
	this->m_size = 0;
}

BiTNode* BiTree::CreateBiTree()
{
	BiTNode* T;
	T = new BiTNode;
	if (this->root == nullptr)
		cout << "请输入根节点(#代表空树):";
	else
		cout << "请输入节点(#代表空树):";
	ElemType ch; cin >> ch;
	if (ch == '#') T = nullptr;
	else
	{
		T->data = ch;
		this->m_size++;
		if (this->root == nullptr)
			root = T;
		T->lchild = this->CreateBiTree();
		T->rchild = this->CreateBiTree();
	}
	return T;
}

int BiTree::GetBiTNum()
{
	return this->m_size;
}

BiTNode* BiTree::GetRoot()
{
	return this->root;
}

void BiTree::PreOrderTraverse(BiTNode* node)
{
	if (node)
	{
		cout << node->data << "t";
		this->PreOrderTraverse(node->lchild);
		this->PreOrderTraverse(node->rchild);
	}
}

void BiTree::InOrderTraverse(BiTNode* node)
{
	if (node)
	{
		this->InOrderTraverse(node->lchild);
		cout << node->data << "t";
		this->InOrderTraverse(node->rchild);
	}
}

void BiTree::PosOrderTraverse(BiTNode* node)
{
	if (node)
	{
		this->PosOrderTraverse(node->lchild);
		this->PosOrderTraverse(node->rchild);
		cout << node->data << "t";
	}
}

BiTNode* BiTree::Copy(BiTNode* node)
{
	BiTNode* temp;
	temp = new BiTNode;
	if (!node)
		temp= nullptr;
	else
	{
		if (!this->root)
			this->root = temp;
		temp->data = node->data;
		this->m_size++;
		temp->lchild = this->Copy(node->lchild);
		temp->rchild = this->Copy(node->rchild);
	}
	return temp;
}

int BiTree::Depth(BiTNode* node)
{
	int m=0, n=0;
	if (!node)
		return 0;
	else
	{
		m = this->Depth(node->lchild);
		n = this->Depth(node->rchild);
		if (m > n)
			return m + 1;
		else
			return n + 1;
	}
}
int BiTree::NodeCount(BiTNode* node)
{
	if (!node)
		return 0;
	else
		return NodeCount(node->lchild) + NodeCount(node->rchild) + 1;
}

int BiTree::LeadCount(BiTNode* node)
{
	if (!node)
		return 0;
	if ((node->lchild == nullptr) && (node->rchild ==nullptr))
		return 1;
	else
		return NodeCount(node->lchild) + NodeCount(node->rchild);
}

bool BiTree::IsSymmetric()
{
	if (this->root == nullptr)
		return true;
	return this->IsSymmetrical(root->lchild, root->rchild);
}

bool BiTree::IsSymmetrical(BiTNode* node1, BiTNode* node2)
{
	if (node1 == nullptr && node2 == nullptr)
		return true;
	if (node1 == nullptr || node2 == nullptr)
		return false;
	if (node1->data != node2->data)
		return false;
	return this->IsSymmetrical(node1->lchild, node2->rchild) && this->IsSymmetrical(node2->lchild, node2->rchild);
}

void BiTree::DestoryBiTree(BiTNode* node)
{
	if (node == nullptr)
		return ;
	DestoryBiTree(node->lchild);
	DestoryBiTree(node->rchild);
	delete node;
}
树与二叉树之间的转化
#pragma once
#include 
#include
using namespace std;

typedef char ElemType;

class CSNode
{
public:
	ElemType data;
	CSNode* firstchild;
	CSNode* nextsibling;
};

class Tree
{
public:
	Tree() { this->root = nullptr; }
	CSNode* CreateTree();//创建树
	CSNode* GetRoot();
	
	void PreTree(const CSNode* T);//先根遍历
	void MidTree(const CSNode* T);//中根遍历


private:
	CSNode* root;
};



CSNode* Tree::CreateTree()
{

	CSNode* p;
	p = new CSNode;
	cout << "输入结点数据:" ;
	cin >> p->data;
	if (p->data == '#')
		p = nullptr;
	else
	{
		if (this->root == nullptr) 
			root = p;
		p->firstchild = this->CreateTree();
		p->nextsibling = this->CreateTree();
	}
	return p;
}
CSNode* Tree::GetRoot()
{
	return this->root;
}

void Tree::PreTree(const CSNode* T)
{
	if (T)
	{
		cout << T->data << "t";
		this->PreTree(T->firstchild);
		this->PreTree(T->nextsibling);
	}
}
void Tree::MidTree(const CSNode* T)//相当于二叉树的中序遍历
{
	if (T)
	{
		this->MidTree(T->firstchild);
		cout << T->data << "t";
		this->MidTree(T->nextsibling);
	}
}


int main()
{ 
	Tree K1;
	K1.CreateTree();
	K1.PreTree(K1.GetRoot());
	cout << endl;
	K1.MidTree(K1.GetRoot());
	system("pause");
	return 0;
}

哈夫曼树

哈夫曼树虽然也是二叉树,但是他加上约束条件,就是带权路径长度WPL最短,由于哈夫曼树中没有结点度为1的结点,即一棵有n个叶子结点的哈夫曼树,共有n+(n+1)个结点,将其存储在定长的数组中,即采用顺序存储结构,每一个数组单元存储结点信息。

 注意:如果想存储哈夫曼编码的信息,还需要附加一个node信息;

构造森林全是根,选择两小造新树,删除两小添新人,重复(2)(3)剩单根;

哈曼夫树的建立、存储及求出由哈夫曼树逆向的哈夫曼代码

哈夫曼编码的相关理论和原理可参考诸多数据结构与算法。 

#pragma once
#include
#include
using namespace std;

const int ERROR = 0;
const int OK = 1;
typedef char ElemType;

class HTNode
{
public:
	int weight;
	int parent;
	int lchild;
	int rchild;
	string code;
};

class HuffmanTree
{

public:
	HuffmanTree() { this->HT = nullptr; }
	void CreatHuffmanTree(int n);//构造哈夫曼树
	void Select(int value,int& s1, int& s2);
	
	//[合并]就是将s1和s2的权值作为新节点的权值存入到第n + 1之后的数组中
	//这个就是返回到构造哈夫曼树的函数里边了Select只完成[选择]和[删除]两步
	void Print(int n);//打印哈夫曼树

	//哈夫曼树的知识点函数
	//1.根据哈夫曼树求哈夫曼编码,形成哈夫曼编码表
	//2.在哈夫曼编码表的基础上,对数据文件进行编码
	//3.在哈夫曼编码表的基础上,对数据文件进行译码
	void CreatHuffmanCode(int n);//形成哈夫曼编码表存在HC中

private:
	HTNode* HT;
};

void HuffmanTree::CreatHuffmanTree(int n)
{
	if (n <= 1)return;
	int m = 2 * n - 1;
	HT = new HTNode[m+1];//开辟了2n个结点空间,但是我0位置不用,只用1~m个空间
	//这2n个空间的初始化工作
	for (int i = 0; i <= m; i++)
	{
		HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; HT[i].code = "";
	}
	for (int i = 1; i <= n; i++)
	{
		cout << "请输入第" << i << "个结点的权重:" ;
		cin >> HT[i].weight;
	}
	//通过n-1次选择,删除,合并来创建哈夫曼树
	for (int j = n + 1; j <= m; j++)
	{
		int s1, s2;
		this->Select(j, s1, s2);
		HT[s1].parent = j;//两个结点有了双亲
		HT[s2].parent = j;
		HT[j].lchild = s1;//双亲也有了自己的孩子和权重
		HT[j].rchild = s2;
		HT[j].weight = HT[s1].weight + HT[s2].weight;
	}

}

void HuffmanTree::Select(int value, int& s1, int& s2)
{
	for (int i = 1; i < value; i++)
	{
		if (this->HT[i].parent == 0)
		{
			s1 = i;
			break;//先找到一个双亲是0的结点,就跳出循环,甭管他的权重值,先找到一个,去进行下边的循环比较
		}
	}
	for (int i = 1; i < value; i++)
	{
		if (this->HT[i].parent == 0 && HT[i].weight < HT[s1].weight)
		{
			s1 = i;//这样的话就找到了权值最小的下标索引
		}
	}
	for (int j = 1; j < value; j++)
	{
		if (this->HT[j].parent == 0&&j!=s1)
		{
			s2 = j;
			break;//先找到一个双亲是0的结点,就跳出循环,甭管他的权重值,先找到一个,去进行下边的循环比较
		}
	}
	for (int j = 1; j < value; j++)
	{
		if (this->HT[j].parent == 0 && HT[j].weight < HT[s2].weight&&j!=s1)
		{
			s2 = j;//这样的话就找到了权值第二小的下标索引
		}
	}
}

void HuffmanTree::Print(int n)//给你的输出结果,顺序存储结构是一个数组,那么也就是数组中元素的打印
{
	//输出打印那个HT数组
	int m = 2 * n - 1;
	cout << "结点" << "t" << "weight" << "t"
		<< "parent" << "t" << "lchild" << "t" << "rchild" << "t" << "HuffmanCode"< 

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/zaji/5593922.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-12-15
下一篇2022-12-15

随机推荐

  • 科技布的优缺点 科技布的优缺点介绍

    导读:科技布的优缺点?下文是小编给大家带来的介绍。1、优点:科技布沙发的技术含量还是比较高的,而且是沙发市场上面的新秀,柔软程度比较好,而且拥有着和真皮沙发一样的手感1、优点:科技布沙发的技术含量还是比较高的,而且是沙发市场上面的新秀,柔软

    2022-12-29
    1400
  • 金钗之年是指我国古代女子多少岁

    金钗之年的说法最早见于南朝梁武帝所作的《河中之水歌》,不同的年龄段有不同的称谓,那么金钗之年是指我国古代女子多少岁呢?下面一起来看看。金钗之年是指我国古代女子多少岁 1、金钗之年是指我国古代女子12岁。2、金钗之年指古代女子12岁,女孩到了

    2022-12-29
    2500
  • 转化率公式算法(赚钱思维之转化率思维)

    我从事商业已经有十几年了,在这些日子里,我有一个最核心的思维就是“转化率”,我在和别人竞争的时候,我什么都不看,我只要自己的“转化率”高于别人就可以了,这样一定会战无不胜。所有的商业模式,所有的赚钱思维,其中最重要的一点就是“转化率”,没

    2022-12-29
    1900
  • 泰国水灯节是什么节日 泰国水灯节是哪时候

    导读:泰国水灯节是什么节日?下面小编为大家整理推荐。1、在泰国的传统节日中,每年的11月份都要举行“水灯节”,这是一个充分体现泰国青年男女旖旎恋情的节日。因为每逢水灯节1、在泰国的传统节日中,每年的11月份都要举行“水灯节”,这是一个充分体

    2022-12-29
    2000
  • 奢侈品包包品牌大全_轻奢侈品包包品牌排行

    首先,每个品牌侧重的领域与人群各不相同,其次,各品牌间的差异也会随着时代的发展而变化,并非一成不变。爱马仕(Hermès)爱马仕(Hermès)是1837年由Thierry Hermès创立于法国巴黎。爱马仕早年以制造高级马具起家,迄

    2022-12-29
    1500
  • 闲鱼小法庭谁比较吃亏

    闲鱼小法庭是买卖双方有争议的投诉平台,如果双方都认为自己占道理,卖家认为买家恶意退款,买家觉得卖家发货有问题,这种争论的确是需要上小法庭的。那么,闲鱼小法庭谁比较吃亏?一起来看看学百科带来的详细介绍吧!闲鱼小法庭谁比较吃亏闲鱼小法庭运行的原

    2022-12-29
    1400
  • 不食嗟来的意思_嗟来之食是什么意思解释

    趣爸爸分享的这个成语叫做嗟来之食,那么嗟来之食的意思是什么呢?小朋友不要被表面的意思迷惑了哦,不是搓来的米,而是比喻一种侮辱别人的施舍行为,下面就来看看吧!齐国大饥荒。有个人叫黔敖[qián至áo],他煮了一大锅粥,摆在大路边

    2022-12-29
    1800
  • 几月几日是圣诞节

    圣诞节作为西方的传统节日,与我国春节一样有着重要的意义,圣诞节虽然是西方的传统节日,但是国内也每年也会过这个节,非常的热闹和喜庆。那么几月几日是圣诞节呢?几月几日是圣诞节1、12月25日原是罗马帝国规定的太阳神诞辰。有人认为选择这天庆祝圣诞

    2022-12-29
    1700
  • 九阳豆浆机哪个好_九阳家用全自动多功能豆浆机

    相信大多数人都有吃早餐的习惯,但也有少部分人不吃早餐,那是因为做豆浆米糊之类的料理机清洗比较麻烦,并且在做米糊豆浆的同时还需要将包子或者鸡蛋蒸煮,所以少部分人像我一样觉得很麻烦不吃早饭。有时我就在想有没有一个机器,它既可以做豆浆米糊,同时

    2022-12-29
    1800

发表评论

登录后才能评论

评论列表(0条)

    保存