(二叉树)- 二叉搜索树

1.二叉树的性质:

  • 第i层最多有2^(i-1)个节点,当然i>=1的。
  • 深度为k的二叉树最多有2^k-1个节点。

  • 对任何一棵二叉树T,如果其终端的节点为n0,度为2的节点为n2,则n0=n2+1。也就是叶子结点的数量=有两个儿子的非叶子节点+1。总的分支线为(n-1)条。n-1=2*n2 + 1*n1。树T的节点总数为n=n0+n1+n2。可以推导出n0=n2+1。
  • 具有n个节点的完全二叉树的深度为floor( log2(n) )+1
  • 具有n个节点的完全二叉树,节点按照层的编号(从第一层到第floor(log2(n))+1层,每层从左到右),对于任意的节点i(1<=1<=n):1)如果i=1,则节点i时二叉树的根。2)如果2*i>n则节点没有左孩子;否则其左孩子节点为2*i。3)如果2*i+1>n,则节点没有有儿子,否则其左孩子节点为2*i+1。4)这个性质对于二叉堆的实现特别有用哦。(要注意一下:如果i从0开始,且<n,那么i的父亲为floor((i-1)/2),i的左孩子是2*i+1哦):)
  • 树的高度:从节点x向下到某一个叶节点的最大的简单路径的边条数。求任意的节点的深度就可以从左右儿子两边时,向上到达节点,那个最大高度就是他。
  • 树的深度:感觉就是所在的层数(待查证)
  • 最深叶节点的深度就是树的深度,树根节点的高度就是树的高度。

2.二叉树有哪些?

  • 满二叉树:所有的非叶子节点的度为2,且所有的叶子结点都在同一层上,就是满二叉树。
  • 完全二叉树:1)叶子只出现在最下两层。2)最下层的叶子一定集中在左部连续的位置。3)倒数二层,若有叶子结点,一定在右部的连续位置。4)如果节点度为1,则节点只有左孩子。5)同样节点的二叉树,完全二叉树的深度最小。如何判断?一颗深度为k二叉树,有n个节点,然后,也对这棵树进行按层从左向右编号,如果所有的编号都和满二叉树对应,那么这棵树是完全二叉树。如果出现编号空挡,就不是完全二叉树。

3.前序遍历、中序遍历和后续遍历:PLR、LPR和LRP,P表示根节点、L左子树或左儿子、R右子树或右儿子。

4.线索化:对于n个节点的二叉树,存在2*n-(n-1)=n+1空闲的个指针域。所以希望利用这些空闲的指针域。对于建立中序遍历的线索树:需要沿着他的遍历方向(所以建立的过程类似于中序遍历),但需要同时修改pre前驱。前驱和后继就是所谓的线索,一般而言空的左子树的指针域为前驱,右子树的为后继。访问呢的时候,和中序一样递归到最左的儿子,然后以此为起点进行遍历,但是需要注意的是,每次访问右子树的时候需要将以右子树为下一个循环的起点。这样可以极大的缩短遍历的时间。

5.二叉树以及三种便利、线索化的实现:

#include <stack>
#include <iostream>
#include <queue>
using namespace std; 
template<typename T>
class BinaryTreeNode
{
	typedef T DataType;
	typedef BinaryTreeNode<DataType> NodeType;
	typedef NodeType *Node;
public:
	BinaryTreeNode():leftchild(nullptr),rightchild(nullptr){}
	BinaryTreeNode(DataType da,Node l=nullptr,Node r=nullptr):leftchild(l),rightchild(r),data(da){}
	//获取
	DataType &getData()
	{
		return data;
	}
	//设置左儿子
	void setLeftchild(Node l) { leftchild = l; }
	//设置右儿子
	void setRightchild(Node r) { rightchild = r; }
	//获取左儿子
	Node getLeftchild() { return leftchild; }
	//获取右儿子
	Node getRightchild() { return rightchild; }
	//析构函数 Node由管理类释放
	~BinaryTreeNode(){}
	//获取左儿子的状态 是否是线索(前驱)
	bool getLeftchildStatus()
	{
		return leftThread;
	}
	//获取右儿子的状态 是否是线索(后继)
	bool getRightchildStatus()
	{
		return rightThread;
	}
	//设置左儿子的状态 是否是线索(前驱)
	void setLeftchildStatus(bool status)
	{
		leftThread = status;
	}
	//设置右儿子的状态 是否是线索(后继)
	void setRightchildStatus(bool status)
	{
		rightThread = status;
	}
private:
	Node leftchild;
	Node rightchild;
	DataType data;
	//这是用来线索化的二叉树标志
	bool leftThread=false;
	bool rightThread=false;
};

template<typename T> class BinaryTreeList
{
public:
	//类型别名
	typedef T DataType;
	typedef BinaryTreeNode<DataType> NodeType;
	typedef NodeType *Node;
	//构造函数
	BinaryTreeList(DataType init) :root(new NodeType) { root->getData() = init; }
	
	//各种操作
	//访问
	//获取根节点
	Node &getRoot() { return root; }
	DataType &Retrieve(Node node) { return node->getData(); }
	//更改
	//插入右子节点
	void insert_right(Node parent,DataType da)
	{
		Node nd = new NodeType(da);
		nd->setRightchild(parent->getRightchild());
		parent->setRightchild(nd);
	}
	//插入左子节点
	void insert_left(Node parent,DataType da)
	{
		Node nd = new NodeType(da);
		nd->setLeftchild(parent->getLeftchild());
		parent->setLeftchild(nd);
	}
	//删除节点
	//注意要判断删除的是叶子还是非叶子	
	void erase_left(Node node)
	{
		destroy(node->getLeftchild());
		node->setLeftchild(nullptr);
	}
	void erase_right(Node node) { destroy(node->getRightchild()); node->setRightchild(nullptr); }
	//释放所有节点
	void clear()
	{
		destroy(root);
		root = nullptr;
	}
	~BinaryTreeList() { clear(); }
	//遍历
	//前序遍历
	void PreOrder(Node p)
	{
		if (p != nullptr)
		{
			cout << p->getData() << " ";
			PreOrder(p->getLeftchild());
			PreOrder(p->getRightchild());
		}
	}
	void PreOrder_Stack(Node p)
	{
		std::stack<NodeType*> sta;
		Node root = p;
		while (sta.empty() == false || root != nullptr)//只要栈不为空 那么就要
		{
			while (root)
			{
				sta.push(root);
				cout << root->getData() << " ";
				root = root->getLeftchild();
			}
			root = sta.top();//此时的top是深度最大的左叶子
			sta.pop();//把那个将要访问的pop
			root = root->getRightchild();//将要访问的叶子节点的父节点的值 左儿子已经处理过了 所以这个root要被更新为父节点的右儿子然后在对右儿子进行处理
		}
		cout << endl;
	}
	//中序遍历
	void InOrderTraverse(Node root)
	{
		if (root != nullptr)
		{
			InOrderTraverse(root->getLeftchild());
			cout << root->getData() << " ";
			InOrderTraverse(root->getRightchild());
		}
	}
	void InOrderTraverse_Stack(Node root)
	{
		stack<Node> nodes;
		Node p = root;
		while (!nodes.empty() || p != nullptr)
		{
			while (p)
			{
				nodes.push(p);
				p = p->getLeftchild();
			}
			if (nodes.empty() == false)
			{
				p = nodes.top();
				cout << p->getData() << " ";
				nodes.pop();
				p = p->getRightchild();
			}
		}
		cout << endl;
	}
	//后续遍历
	void PostOrderTraverse(Node p)
	{
		if (p != nullptr)
		{
			PostOrderTraverse(p->getLeftchild());
			PostOrderTraverse(p->getRightchild());
			std::cout << p->getData() << " ";
		}
	}
	void PostOrderTraverse_Stack(Node root)
	{
		stack<Node> sta;
		Node p = root;
		Node prev = nullptr;
		while (!sta.empty() || p != nullptr)
		{
			while (p)
			{
				sta.push(p);
				p = p->getLeftchild();
			}
			p = sta.top();
			//分析当前的栈顶元素 此时是没有左儿子的
			if (p->getRightchild() ==nullptr /*叶子节点直接访问*/|| p->getRightchild() ==prev/*如果左儿子为null 而且右儿子先前被访问过(说明要访问该节点(LR的父亲))*/)
			{
				cout << p->getData() << " ";
				prev = p;
				sta.pop();//将这个节点从栈中pop
				p = nullptr;//将p设置为nullptr是为了不要又开始搜索左儿子 应该访问栈顶了
			}
			else
			{
				//sta.pop();
				p = p->getRightchild();//不满足条件 那么应该继续搜索右儿子
			}
		}
		cout << endl;
	}
	//层次遍历
	void LevelOrderTraverse(Node root)
	{
		queue<Node> que;
		Node p = root;
		if (p != nullptr)
		{
			que.push(p);//首元素入队
			while (!que.empty()) //只要队列不为空的话 
			{
				p = que.front();//获取对头元素 
				cout << p->getData() << " ";
				que.pop();//出对 将对头元素转移到与之同级的右节点上 然后该节点的左右子树分别入队
				if (p->getLeftchild())
					que.push(p->getLeftchild());
				if (p->getRightchild())
					que.push(p->getRightchild());

			}
		}
		cout << endl;
	}
	//线索化操作
	//建立前序搜索关联
	void InOrderThread(Node root)
	{
		Node pre = nullptr;//这个指针总是保存之前访问的位置
		InOrderThread_Process(root, pre);
	}
	//中序线索遍历
	void Display_InOrderThread(Node root)
	{
		for (Node p = InOrder_FindFirst(root); p != nullptr; p = InOrder_NextNode(p))
			cout << p->getData() << " ";
		cout << endl;
	}
	// 前序搜索建立
	//建立前序搜索关联
	void PreOrderThread(Node root)
	{
		Node pre = nullptr;//这个指针总是保存之前访问的位置
		PreOrderThread_Process(root, pre);
	}
	//前序线索树显示
	void Display_PreOrderThread(Node root)
	{
		Node d = root;
		while (d != nullptr)
		{
			cout << d->getData() << " ";
			d = PreOrder_NextNode(d);
		}
		cout << endl;
	}
	//后续线索化
	void PostOrderThread(Node root)
	{
		Node pre = nullptr;
		PostOrderThread_Process(root, pre);
	}
	//显示线索化
	void Display_PostOrderThread(Node root)
	{
		Node p = PostOrderThread_FindFirstNode(root);
		while (p != nullptr)
		{
			cout << p->getData() << " ";
			p = PostOrderThread_NextNode(p);
		}
		cout << endl;
	}
	//清除指定根节点以及他的子树的线索信息
	void clearAllThreads(Node r)
	{
		if (r != nullptr)
		{
			clearAllThreads(r->getLeftchild());
			clearAllThreads(r->getRightchild());
			if (r->getLeftchildStatus() == true)
			{
				r->setLeftchildStatus(false);
				r->setLeftchild(nullptr);
			}
			if (r->getLeftchildStatus() == true)
			{
				r->setRightchild(nullptr);
				r->setRightchildStatus(false);
			}
		}

	}
private:
	Node root;//保存根节点
	void destroy(Node r)
	{
		if (r != nullptr)
		{
			if (r->getLeftchildStatus() == false)//如果不是修改后的指针域才会释放他们 避免二次释放
			{
				destroy(r->getLeftchild());
			}
			if (r->getRightchildStatus() == false)
			{
				destroy(r->getRightchild());
			}
			delete r;
		}
	}
	//中序线索化 私有函数
	void InOrderThread_Process(Node root, Node &pre)
	{
		if (root != nullptr)
		{
			InOrderThread_Process(root->getLeftchild(), pre);//遍历左子树
			if (root->getLeftchild() == nullptr)
			{
				//没有左孩子
				root->setLeftchildStatus(true);
				root->setLeftchild(pre);//将左孩子的指正改为前驱 指向树的前驱节点(也就是pre)
			}
			if (pre!=nullptr /*这个要判断*/ &&pre->getRightchild() == nullptr)
			{
				//前一个节点没有右孩子
				pre->setRightchildStatus(true);
				pre->setRightchild(root);
			}
			pre = root;//这个pre是一个引用 所以能够保证指向的是root!=nullptr的前一个节点
			InOrderThread_Process(root->getRightchild(), pre);//如果没有右儿子 那么会自动结束当前的递归 从而可以把root定位到原root的父节点 pre已经更新到root
		}
	}
	
	//寻找中序遍历的起点 最左的左儿子
	Node InOrder_FindFirst(Node o)
	{
		
		if (o != nullptr)
		{
			Node first = o;
			while (first->getLeftchildStatus() == false)
				first = first->getLeftchild();
			return first;
		}
		else
		{
			return nullptr;
		}
	}
	//寻找中序遍历后续的节点 可能是右儿子(因为是中序遍历)或者是指定的后继
	Node InOrder_NextNode(Node p) {
		if (p == nullptr)
		{
			return nullptr;
		}
		else
		{
			if (p->getRightchildStatus() == false) return InOrder_FindFirst(p->getRightchild());//右子树的第一个结点(右子树的最左的儿子)
			else return p->getRightchild();//或后继
		}
	}

	//寻找前序线索遍历的下一个节点
	Node PreOrder_NextNode(Node p) {
		if (p == nullptr)
		{
			return nullptr;
		}
		else
		{
			if (p->getLeftchildStatus() == false)//如果左儿子不是空的话 返回的下一个节点就是左儿子
			{
				return p->getLeftchild();
			}
			else
			{
				return p->getRightchild();//如果左儿子为空的话(此时节点指的是前驱)那么就返回他的右儿子
			}
		}
	}
	//前序线索便利构造
	void PreOrderThread_Process(Node root, Node &pre)
	{
		if (root != nullptr)
		{
			if (root->getLeftchild() == nullptr)
			{
				//没有左儿子 那这个左儿子域就用来保存前驱节点的指针
				root->setLeftchildStatus(true);
				root->setLeftchild(pre);
			}
			if (pre && pre->getRightchild() == nullptr)//前一个结点没有指针的位置 那么就让他指向下一个节点
			{
				pre->setRightchildStatus(true);
				pre->setRightchild(root);
			}
			pre = root;
			if (root->getLeftchildStatus() == false)//如果还有左儿子 那么也需要对左儿子建立线索
			{
				PreOrderThread_Process(root->getLeftchild(), pre);
			}
			if (root->getRightchildStatus() == false)//如果还有左右儿子 那么也需要对右儿子建立线索
			{
				PreOrderThread_Process(root->getRightchild(), pre);
			}
		}
	}
	
	//后续线索遍历
	void PostOrderThread_Process(Node root, Node &pre)
	{
		if (root != nullptr)
		{
			if (root->getLeftchildStatus() == false)
				PostOrderThread_Process(root->getLeftchild(), pre);
			if (root->getRightchildStatus() == false)
				PostOrderThread_Process(root->getRightchild(), pre);
			if (root->getLeftchild() == nullptr)
			{
				root->setLeftchild(pre);
				root->setLeftchildStatus(true);
			}
			if (pre !=nullptr && pre->getRightchildStatus() == false)
			{
				pre->setRightchild(root);
				pre->setRightchildStatus(true);
			}
			pre = root;
		}
	}
	Node PostOrderThread_FindFirstNode(Node nd)
	{
		if (nd != nullptr)
		{
			//用来寻找最深层的节点
			while (nd->getLeftchild())
				nd = nd->getLeftchild();
			return nd;
		}
		else
		{
			return nullptr;
		}
	}
	//后续线索的下一个节点
	Node PostOrderThread_NextNode(Node root)
	{
		if (root != nullptr)
		{
			if (root->getRightchildStatus() == false)
			{
				//存在右儿子
				if (root->getLeftchildStatus() == false)//如果存在左儿子的话 也就是到达了第一个有两个儿子的节点 那么我们认为他是不需要遍历的节点
				{
					return nullptr;
				}
				else
				{
					return PostOrderThread_FindFirstNode(root->getLeftchild());//存在右儿子 左儿子是前驱 那么我们就搜索他的子树 从最低的左儿子开始遍历
				}
			}
			else
			{
				return root->getRightchild();//右儿子是后继 直接返回右儿子
			}
		}
		else
		{
			return nullptr;
		}
	}
};

6.哈夫曼树:最优二叉树,每次选取频数最小的两个子树或者节点,构建一颗二叉树,然后放入优先队列中。频数最大的节点就会出现在数离根节点最近的地方。所以他的字符映射的长度就会是最小的

#include <algorithm>
#include <map>
#include <vector>
#include <utility>
#include <unordered_map>
#include <queue>
#include <iostream>
#include <tchar.h>
#include <string>
using namespace std;
class HuffmanTreeNodeBase {
public:
	//构造函数必须提供频数或频数之和
	HuffmanTreeNodeBase(int f) :flag(f) {}
	//获取flag值 对于叶子节点派生类这个保存的是频数 对于节点保存的是两个flag的频数纸盒之和
	int getFlag() const {
		return flag;
	}
	//设置flag
	void setFlag(int w) {
		flag = w;
	}

	virtual ~HuffmanTreeNodeBase() {}
private:
	int flag;//表示这个节点的值
};

class HuffmanLeafTree :public HuffmanTreeNodeBase {
public:
	//必须提供叶子节点频数和代表的字符
	HuffmanLeafTree(int f, char c) :HuffmanTreeNodeBase(f), ch(c) {}
	//获取叶子节点代表的字符
	char getChar() {
		return ch;
	}
	//设置叶子节点代表的字符
	void setChar(char c) {
		ch = c;
	}
	~HuffmanLeafTree() {}
private:
	char ch;//这个表示叶子节点的被编码的符号
};
class HuffmanTreeNode : public HuffmanTreeNodeBase {
	typedef HuffmanTreeNodeBase *Node;
public:
	//提供频数和频数之和 左儿子节点指针 右儿子节点指针
	HuffmanTreeNode(int flag, Node l, Node r) :HuffmanTreeNodeBase(flag), left(l), right(r) {}
	~HuffmanTreeNode() {
		delete left; //析构函数
		delete right;
	}
	//获取左儿子节点指针
	Node getLeftchild() {
		return left;
	}
	//获取右儿子节点指针
	Node getRightchild() {
		return right;
	}
private:
	Node left;
	Node right;
};
class Huffman {

public:
	typedef std::map<char, int> Charfrenquent;//这个用来保存被编码的字符的出现的频数
	typedef std::vector<int> Encoding;//这个用来保存一组哈夫曼编码
	typedef std::map<char, Encoding> CharMap;//这个用来保存对应字符的编码表

											 //构造函数
	Huffman() {}
	//这个用来整理map 频率最小的排在前面 现在已经不使用
	void sortMap(std::unordered_map<char, int> &ma) {
		std::vector<std::pair<char, int>> res;
		for (auto iter = ma.begin(); iter != ma.end(); ++iter)
			res.push_back(std::make_pair(iter->first, iter->second));
		std::sort(res.begin(), res.end(),
			[](const std::pair<char, int> &c1, std::pair<char, int> &c2) {
			return c1.second < c2.second;
		}
		);
		//重新排序
		ma.clear();
		for (auto i = res.cbegin(); i != res.cend(); ++i)
			ma[i->first] = i->second;
	}
	//这个函数用来计算字符出现的频率 第三个参数是输出的保存字符对应平频率的映射表
	void calcFrenquentofChars(const char *c, int size, Charfrenquent &cf) {
		if (c != nullptr && size > 0) {

			for (int i = 0; i < size; ++i) {
				cf[c[i]]++;
			}
			//sortMap(cf);
		}
	}
	//这个用来生成哈夫曼树 需要获取已知的频率映射表 生成的树依据最优二叉树的规则
	HuffmanTreeNodeBase *buildHuffmanTree(Charfrenquent &cf) {
		auto j = [](const HuffmanTreeNodeBase *c1, const HuffmanTreeNodeBase *c2) {
			return c1->getFlag() > c2->getFlag();/*如果返回的是true表示后面的频数比前面的小 那么就需要吧后面的和前面的交换顺序*/
		};//这个用来设置优先队列最先出出对的佘顺序 依据的是频数 频数最小的先出来
		std::priority_queue < HuffmanTreeNodeBase*, std::vector<HuffmanTreeNodeBase*>, decltype(j)> trees(j);
		for (auto i = cf.begin(); i != cf.end(); ++i)
			trees.push(new HuffmanLeafTree(i->second, i->first));
		//优先队列
		while (trees.size() > 1) {
			//从优先队列出来是频数最小的字符
			HuffmanTreeNodeBase *le = trees.top();
			trees.pop();
			HuffmanTreeNodeBase *ri = trees.top();
			trees.pop();
			HuffmanTreeNode *nd = new HuffmanTreeNode(le->getFlag() + ri->getFlag(), le, ri);//新建的一个Node节点 由于是base的派生类 所以指针是可以插入的
			trees.push(nd);//把这个节点插入优先队列
		}
		return trees.top();
	}
	//这个用来生成哈夫曼编码 charmap输出的就是字符对应的编码 用vector保存 第三个参数用来验证是否只存在一个编码的情况
	void genrateCode(HuffmanTreeNodeBase *tree, CharMap &cm, Charfrenquent &fren) {
		Encoding enc;//这个是用于临时保存的vector
		if (fren.size() == 1) {
			enc.push_back(0);
		}
		else {
			if (fren.size() <= 0)
				return;
		}
		do_genrateCode(tree, enc, cm);
	}
	std::string deCoding(CharMap &cm, std::string &encodedstr) {
		std::string result;
		std::map<std::string, char> reverseMap;
		for (CharMap::const_iterator it = cm.cbegin(); it != cm.cend(); ++it) {
			std::string k;
			for (Encoding::const_iterator i = it->second.cbegin(); i != it->second.cend(); ++i)
				k.push_back(*i + '0');//将vector中的编码序列变成字符串的形式 注意int和char类型的互换
			reverseMap.insert(std::make_pair(k, it->first));//将键值对插入map
		}
		//反向映射表建立完成
		auto beg = encodedstr.cbegin();
		auto end = encodedstr.cend();
		auto range = ++encodedstr.cbegin();//这个表示范围的有开区间 我们将会从[Beg,range) 中构建查找的字符串 beg!=range 否则为空字符串
		int cnt = 0;//cnt计数用于吧beg递增到最近一次匹配位置的尾后
		while (beg != end) {
			char dest;
			bool changeres = match_str(reverseMap, beg, range, dest);//查找
			if (changeres == true) {
				result.push_back(dest);
				for (int i = 0; i <= cnt; ++i) {
					++beg;
				}
				if (range == end)//如果此时的匹配之后range的位置是尾后 那么表示这是最后一次成功的匹配 就结束while
					break;
				range = beg + 1;//range>beg
				cnt = 0;//cntc重新开始计数
			}
			else {
				++cnt;//如果匹配失败 那么一旦匹配成功那么bg会递增到beg+cnt+1的位置
				++range;//范围也要递增
			}
		}
		return result;
	}
	~Huffman() {}
private:
	void do_genrateCode(HuffmanTreeNodeBase *tree, Encoding &precode, CharMap &charmap) {
		if (tree == nullptr)
			return;

		HuffmanLeafTree *leaf = dynamic_cast<HuffmanLeafTree*>(tree);
		if (leaf) {
			//表示这个指针是叶子节点 那么就设置该字符的编码 编码保存在int的vector中
			charmap[leaf->getChar()] = precode;
		}
		else {
			HuffmanTreeNode *nd = dynamic_cast<HuffmanTreeNode*>(tree);
			if (nd) {
				//表示这是节点 所以还是必须把编码压入vector
				Encoding leftcode = precode;//这里定义一个新的vector他是用来防止不同的vector编码冲突的问题
				leftcode.push_back(0);//做儿子的话 路径上的权为0
				do_genrateCode(nd->getLeftchild(), leftcode, charmap);//从左儿子开始 递归
				Encoding rightcode = precode;//解释同上
				rightcode.push_back(1);
				do_genrateCode(nd->getRightchild(), rightcode, charmap);

			}
		}
	}
	//这个用来寻找哈夫曼序列对应的字符 第一个参数是映射表 [beg,end) 注意beg !=end 表示要匹配的迭代器范围
	bool match_str(std::map<std::string, char> reverseMap, string::const_iterator beg_match, std::string::const_iterator end_match, char &res) {
		std::string s(beg_match, end_match);//构建一个临时的字符串
		auto r = reverseMap.find(s);//根据字符串查找对应的哈夫曼字符映射
		if (r == reverseMap.end()) { //如果没有找到的话 返回的是end迭代器
			return false;
		}
		else {
			res = r->second;//找到了映射
			return true;
		}
	}
};
int main() {
	const char *c;
	int sz;
	cout << "请输入要编码的序列:";
	std::string s;
	cin >> s;
	c = s.c_str();
	sz = s.size();
	Huffman hmf;//哈夫曼对象
	Huffman::Charfrenquent hmf_freq;//字符出现的频数
	hmf.calcFrenquentofChars(c, sz, hmf_freq);
	HuffmanTreeNodeBase *tree = hmf.buildHuffmanTree(hmf_freq);//得到地哈夫曼树
	Huffman::CharMap hmf_map;//哈夫曼映射表
	hmf.genrateCode(tree, hmf_map, hmf_freq);
	delete tree;
	int orgsz = 0;
	int zipsz = 0;

	//计算应该的长度
	int cnt = 0;
	int weight = 1;
	int t = hmf_map.size();
	while (1) {
		if (t == 1) {
			cnt = 1;
			break;
		}
		if (t - weight <= 0) {
			break;
		}
		else {
			weight *= 2;
			++cnt;
		}
	}
	//cnt就应该要编码的二进制的位数
	orgsz = sz*cnt;
	cout << endl << "获得的哈夫曼编码映射为:" << endl;
	for (auto i = hmf_map.cbegin(); i != hmf_map.cend(); ++i) {
		cout << "[" << i->first << "]=";
		for (int j = 0; j < (i->second).size(); ++j) {
			cout << i->second[j];

		}
		cout << endl;
	}
	std::string  hfm_encodedstr;//这个表示哈夫曼编码后的二进制
	cout << "得到的哈夫曼字符编码为:";
	for (int i = 0; i < sz; ++i) {
		for (int j = 0; j < hmf_map[c[i]].size(); ++j) {
			cout << hmf_map[c[i]][j];
			hfm_encodedstr.push_back(hmf_map[c[i]][j] + '0');
			++zipsz;//压缩后大小计算
		}
		cout << " ";
	}
	cout << endl << "原始编码长度:" << orgsz << ",编码后长度:" << zipsz << " 压缩率为:" << (static_cast<float>(zipsz) / orgsz) << endl;
	cout << "解码后:" << hmf.deCoding(hmf_map, hfm_encodedstr) << endl;//重新解码
	return 0;
}

为什么需要二叉树呢?因为一个char类型字符可能需要8位来表示。而如果转换成0和1表示,就可以使用floor((log2(N))个0 1 序列表示。假设一共所有的字符可以用宽位4的二进制位表示,那么一个8位就可以用来表示两个字符,积少成多就可以省下很多的空间。有点让我想起了可以用int表示32个真假逻辑值。

7.平衡树:每当插入节点时,可能会使二叉树变成一个链表,这会严重降低二叉树的搜索性能,最坏的时间复杂度会达到O(N)。所以我们仍然需要做出一些调整,使得二叉树能够在floor(log2(N))的时间查找一个节点。所以就需要不断地调整。

  • AVL树:比较简单的平衡查找树。平衡因子就是左右子树高度之差的绝对值不超过1,就认为是平衡的。如果定义平衡因子=左子树高度-右子树高度。如果没有子树,对应的高度为-1。插入新元素后,不满足的平衡的四种情况:

参考: