二叉树、哈夫曼报文大全

1、泛型链树

#include <iostream>
#include<Windows.h>
#include<string>
#include<stack>
#include<queue>
using namespace std;
void menu()
{cout << "**********" << endl;cout << "-1.添加" << endl;cout << "-2.插入" << endl;cout << "-3.销毁" << endl;cout << "-4.修改" << endl;cout << "-5.查找" << endl;//*cout << "-6.删除" << endl;//*cout << "-7.统计" << endl;//*cout << "-8.打印" << endl;//*cout << "-X.线索化树" << endl;//*cout << "-0.退出  请选择：";
}
void LeadingTree_menu()
{cout << "**********" << endl;cout << "-7.打印" << endl;//*cout << "-0.退出  请选择：";
}
void LeadingChoice_menu()
{cout << "-1.先序线索化" << endl;cout << "-2.中序线索化" << endl;cout << "-3.后序线索化" << endl;cout << "-0.退出  请选择：";
}
void bianli_menu()
{cout << "-1.先序打印" << endl;cout << "-2.中序打印" << endl;cout << "-3.后序打印" << endl;cout << "-0.退出  请选择：";
}
void status_menu()
{cout << "-1.统计叶子个数" << endl;cout << "-2.统计节点个数" << endl;cout << "-3.测量树的高度" << endl;cout << "-4.度为1的个数" << endl;cout << "-5.度为2的个数" << endl;cout << "-0.退出  请选择：";
}
void delete_menu()
{cout << "-1.删除当前节点" << endl;cout << "-2.删除左子树" << endl;cout << "-3.删除右子树" << endl;cout << "-4.删除双亲  选择：" << endl;cout << "-0.退出  请选择：";
}
template<class T>
class Node
{
private:T data;Node<T>* left;//左子树Node<T>* right;//右子树int Ltag = 0;//线索int Rtag = 0;
public:Node() {left = NULL;right = NULL;}T getData() {return data;}void setData(T data) {this->data = data;}Node<T>* getLeft() {return left;}void setLeft(Node<T>* left) {this->left = left;}Node<T>* getRight() {return right;}void setRight(Node<T>* right) {this->right = right;}int getLtag() {return Ltag;}void setLtag(int Ltag) {this->Ltag = Ltag;}int getRtag() {return Rtag;}void setRtag(int Rtag) {this->Rtag = Rtag;}
};
template<class T>
class Tree
{
private:Node<T>* root;//树根Node<T>* Lroot;//线索化树int m = 0, n = 0;//计算深度
public:Tree() :root(NULL),Lroot(NULL) {}//构造~Tree();//析构//找到想要的数据,查重，修改，查找(递归实现),删除，插入Node<T>* GetNodePositon(Node<T>* node,T target_data);//增加数据void AddData();//插入数据void InsertData();//销毁二叉树void Desstroy();//三种遍历方式的点调用函数void Use_Traverse(int a);		//调用作用//统计功能的调用void Use_status(int n);//调用作用//修改void AlterNode_data();//查找void LookNode_data();//删除void Begin_DeleteNode();//线索化树void LeadingTree();
private://销毁树void DestroyBiTree(Node<T>* node);//递归增加数据void CreateBiTree(T data);//遍历方式void PreOrder(Node<T>* node);	// 前序遍历void InOrder(Node<T>* node);	// 中序遍历void PostOrder(Node<T>* node);	// 后序遍历//统计实现int TreeDepth(Node<T>* node);//计算树的高度int GetNodeNum(Node<T>* cur_node);//返回节点的个数int FindYezi(Node<T>* node);//返回叶子个数//删除void DeleteNode(Node<T>* curNode);Node<T>* FindParentNode(Node<T>* root,Node<T>* cur_node);//------------------------------------//复制二叉树,返回新二叉树的根指针Node<T>* Copy(Node<T>* root_tree);//线索化//指针作为函数参数时，如果涉及到指针值的改变，需要使用指向指针的指针或者指针的引用。void PreThreading(Node<T>* p, Node<T>*& pre);void InThreading(Node<T>* p, Node<T>*& pre);void PostThreading(Node<T>* p, Node<T>*& pre);//线索化遍历void PrePrint(Node<T>* p);void InPrint(Node<T>* p);void PostPrint(Node<T>* p);//销毁线索化树void DestroyCueTree(Node<T>* root);
};template<class T>
Tree<T>::~Tree()
{DestroyBiTree(root);delete root;root = NULL;
}template<class T>
Node<T>* Tree<T>::GetNodePositon(Node<T>* node, T target_data)
{//空树，返回NULLif (node == NULL) { return NULL; }//遍历指针与目标数据相同则返回遍历指针if (node->getData() == target_data) { return node; }//在左子树中查找Node<T>* leftTree = GetNodePositon(node->getLeft(), target_data);if (leftTree != NULL) { return leftTree; }//在右子树中查找Node<T>* rightTree = GetNodePositon(node->getRight(),target_data);if (rightTree != NULL) { return rightTree; }return NULL;
}template<class T>
void Tree<T>::Use_status(int n)
{if (root){cout << endl;switch (n){case 1:cout << "这棵树的叶子有：" << FindYezi(root) << "个" << endl;break;case 2:cout << "该二叉树的节点个数：" << GetNodeNum(root) << endl;break;case 3:cout << "该二叉树的高度：" << TreeDepth(root) << endl;break;case 4://n0=n2+1cout << "该树度为1的节点个数：" << GetNodeNum(root) - 2 * FindYezi(root) + 1 << endl;break;case 5://n=n2+n1+n0cout << "该树度为2的节点个数：" << FindYezi(root) - 1 << endl;break;default:break;}}else {cout << "这是空树。" << endl;}system("pause");
}template<class T>
void Tree<T>::AlterNode_data()
{if (root != NULL) {cout << "请输入你想修改的数据：";T data;cin >> data;Node<T>* q = GetNodePositon(root,data);//确定此数据的节点if (q != NULL){cout << "+------------------------------+" << endl;cout << "请输入你要修改的数据：";while (1){T alter_data;cin >> alter_data;//判断输入的数据是否重复,Node<T>* alter_node = GetNodePositon(root, alter_data);//确保修改的数据不重复，且能修改为自身if (alter_node == NULL || q->getData() == alter_data){q->setData(alter_data);}else {cout << "修改的数据重复，重新修改：";}if (q->getData() == alter_data) { cout << "修改成功。" << endl; break; }}}else {cout << "未找到此数据。" << endl;}}else {cout << "这是空树。" << endl;}system("pause");
}template<class T>
void Tree<T>::LookNode_data()
{if (root != NULL) {cout << "请输入你想查找的数据：";T data;cin >> data;Node<T>* q = GetNodePositon(root, data);//确定此数据的节点if (q != NULL){cout << "+------------------------------+" << endl;cout << "成功查找到此数据：" << q->getData() << endl;}else {cout << "未找到此数据。" << endl;}}else {cout << "这是空树。" << endl;}system("pause");
}template<class T>
void Tree<T>::Begin_DeleteNode()
{if (root != NULL) {cout << "中序遍历：" << endl;cout << "请输入要删除的结点：";T data;cin >> data;Node<T>* q = GetNodePositon(root, data);//确定此数据的节点if (q != NULL){cout << "+------------------------------+" << endl;cout << "成功查找到此数据：" << q->getData() << endl;DeleteNode(q);}else {cout << "未找到此数据。" << endl;}}else {cout << "这是空树。" << endl;}system("pause");
}template<class T>
int Tree<T>::TreeDepth(Node<T>* node)
{int h1, h2;if (node){h1 = TreeDepth(node->getLeft());//递归计算左子树的高度为mh2 = TreeDepth(node->getRight());//递归计算右子树的高度为nreturn h1 > h2 ? h1 + 1 : h2 + 1;}else {return 0;}
}template<class T>
int Tree<T>::GetNodeNum(Node<T>* cur_node)
{// 递归计算以给定节点为根的子树中节点的数量if (cur_node == NULL) {return 0;//如果是空树，则节点个数为0，递归结束}return 1 + GetNodeNum(cur_node->getLeft()) + GetNodeNum(cur_node->getRight());//递归计算个数//否则节点个数为左子树的节点个数+右子树的节点个数
}template<class T>
int Tree<T>::FindYezi(Node<T>* node)
{if (node == NULL) {return 0;//无叶子节点}if (node->getLeft() == NULL && node->getRight() == NULL) {return 1;//叶子节点}return FindYezi(node->getLeft()) + FindYezi(node->getRight());//递归求叶子节点}template<class T>
void Tree<T>::DeleteNode(Node<T>* curNode)
{if (!root) return; // 如果根节点为空，直接返回Node<T>* parent = NULL;Node<T>* p = curNode;// 找到要删除节点并记录父节点parent = FindParentNode(root, p);//要删除的节点没有子节点if (!p->getLeft() && !p->getRight()) {if (!parent) { //删除根节点delete p;root = NULL;}else {if (p == parent->getLeft()) { parent->setLeft(NULL); }else { parent->setRight(NULL); }delete p;}}//要删除的节点只有一个子节点else if (!p->getLeft() || !p->getRight()) { Node<T>* child = p->getLeft() ? p->getLeft() : p->getRight(); // 找到要保留的子节点if (!parent) { // 要删除的节点为根节点root = child;delete p;}else {if (p == parent->getLeft()) {parent->setLeft(child);}else {parent->setRight(child);}delete p;}}else { //要删除的节点有两个子节点Node<T>* q = p->getLeft();Node<T>* r = p;while (q->getRight()) { // 找到p的前驱节点q和其父节点rr = q;q = q->getRight();}p->setData(q->getData()); // 用q的值覆盖p的值if (r == p) { //q没有右子节点，直接将其左子节点替换到r的右边r->setLeft(q->getLeft()); } else { //将q的左子节点替换到q的父节点r的右边r->setRight(q->getLeft()); } delete q;}
}template<class T>
Node<T>* Tree<T>::FindParentNode(Node<T>* root,Node<T>* cur_node)
{if (root == NULL || cur_node == NULL) {return NULL;}if (root->getLeft() == cur_node || root->getRight() == cur_node) {return root;}Node<T>* left = FindParentNode(root->getLeft(), cur_node);if (left != NULL) {return left;}Node<T>* right = FindParentNode(root->getRight(), cur_node);if (right != NULL) {return right;}return NULL;
}template<class T>
Node<T>* Tree<T>::Copy(Node<T>* root_tree)
{if (root_tree == NULL) { return NULL; }//开辟新的根指针，复制Node<T>* newRoot = new Node<T>;newRoot->setData(root_tree->getData());//左子树遍历newRoot->setLeft(Copy(root_tree->getLeft()));//右子树遍历newRoot->setRight(Copy(root_tree->getRight()));return newRoot;//返回根指针
}template<class T>
void Tree<T>::PreThreading(Node<T>* p, Node<T>*& pre)
{if (p == NULL) { return; }// 左孩子为空，建立前驱线索if (p->getLeft() == NULL) {p->setLeft(pre); //将当前结点的左孩子指向前驱结点p->setLtag(1);//将当前结点的左孩子标记线索1}// 前驱的右孩子为空，建立后继线索if (pre != NULL && pre->getRight() == NULL) {pre->setRight(p);// 将前驱结点的右孩子指向当前结点pre->setRtag(1); // 将前驱结点的右孩子标记线索1}pre = p;//更新前驱// 还有左孩子，继续遍历“根左右”if (p->getLtag() == 0) {PreThreading(p->getLeft(), pre);}// 当前的根有右子树，则遍历右子树上的内容if (p->getRtag() == 0) {PreThreading(p->getRight(), pre);}
}template<class T>
void Tree<T>::InThreading(Node<T>* p,Node<T>*& pre)
{if (p == NULL) { return; }//左子树递归线索化InThreading(p->getLeft(), pre);// p 的左子树为空if (p->getLeft() == NULL) {p->setLeft(pre); //将当前结点的左孩子指向前驱结点p->setLtag(1);//将当前结点的左孩子标记线索1}// 线索化当前结点if (pre != NULL && pre->getRight() == NULL) {pre->setRight(p);// 将前驱结点的右孩子指向当前结点pre->setRtag(1); // 将前驱结点的右孩子标记线索1}pre = p;//更新前驱//右子树递归线索化InThreading(p->getRight(), pre);
}template<class T>
void Tree<T>::PostThreading(Node<T>* p, Node<T>*& pre)
{if (p == NULL) { return; }PostThreading(p->getLeft(), pre);PostThreading(p->getRight(), pre);// 左孩子为空，建立前驱线索if (p->getLeft() == NULL) {p->setLeft(pre); //将当前结点的左孩子指向前驱结点p->setLtag(1);//将当前结点的左孩子标记线索1}// 前驱的右孩子为空，建立后继线索if (pre != NULL && pre->getRight() == NULL) {pre->setRight(p);// 将前驱结点的右孩子指向当前结点pre->setRtag(1); // 将前驱结点的右孩子标记线索1}pre = p;//更新前驱
}template<class T>
void Tree<T>::PrePrint(Node<T>* p)
{//遍历先序线索二叉树while (p != NULL){cout << p->getData() << endl;if (p->getLtag() == 0)//指向后继{p = p->getLeft();}else{p = p->getRight();}}
}template<class T>
void Tree<T>::InPrint(Node<T>* RooT)
{Node<T>* p = RooT->getLeft();while (p != NULL) {while (p->getLtag() == 0) {p = p->getLeft();//最左侧}cout << p->getData() << endl;while (p->getRtag()== 1 && p->getRight() != NULL) {p = p->getRight();cout << p->getData() << endl;}p = p->getRight();}
}template<class T>
void Tree<T>::PostPrint(Node<T>* p)
{//栈的思想实现线索后序遍历stack<Node<T>*> s;stack<T> Sinput;Node<T>* cur = p;s.push(cur);//存放根节点while (!s.empty()) {//按“根右左”的思想压入栈，然后出栈即为“左右根”cur = s.top();s.pop();//删掉双亲节点if (cur->getLtag() && cur->getRtag()) {Sinput.push(cur->getData());}else {if (cur->getLtag()) {s.push(cur->getLeft());}if (cur->getRtag()) {s.push(cur->getRight());}else {s.push(cur->getLeft());s.push(cur->getRight());}cur->setLtag(1);cur->setRtag(1);s.push(cur);//返回双亲节点}}while (!Sinput.empty()) {cout << Sinput.top() << endl;Sinput.pop();}
}template<class T>
void Tree<T>::DestroyCueTree(Node<T>* root)
{if (root != NULL) {// 如果左子树指向的不是前驱，则先销毁左子树if (root->getLtag() == 0) { DestroyCueTree(root->getLeft());}// 如果右子树指向的不是后继，则最后才销毁右子树if (root->getRtag() == 0) { DestroyCueTree(root->getRight());}delete root;root = NULL;}
}template<class T>
void Tree<T>::AddData()
{int n;cout << "添加数据个数：";cin >> n;for (int i = 1; i <= n; i++) {cout << "第" << i << "个：";while (1){T data;cin >> data;Node<T>* temp = GetNodePositon(root,data);//接受返回的指针if (!temp)//如果没有重复，返回NULL{if (!root) {//若根节点为空则输入数据root = new Node<T>;root->setData(data);root->setLeft(NULL);root->setRight(NULL);}else {CreateBiTree(data);//递归添加数据}break;//跳出while循环，开始输入下一个数据}else {cout << "你输入的第"<< i <<"个数据已经重复，请重新输入数据:";}}}cout << "添加完成" << endl;system("pause");
}template<class T>
void Tree<T>::InsertData()
{if (root != NULL) {cout << "请输入双亲结点查找是否插入：";T data;cin >> data;Node<T>* q = GetNodePositon(root, data);//确定此数据的节点if (q != NULL){cout << "+------------------------------+" << endl;cout << "成功查找到此数据：" << q->getData() << endl;Node<T>* tmp = NULL;T tmp_data;if (q->getLeft() == NULL && q->getRight() == NULL) {cout << "此节点的左右子树都可以插入数据。" << endl;while (1){cout << "请输入插入的数据:";cin >> tmp_data;tmp = GetNodePositon(root, tmp_data);if (tmp) {cout << "此数据重复。再次";}else {//开辟空间Node<T>* newSpace = new Node<T>;newSpace->setData(tmp_data);string ch = "";cout << "请选择输入的分支(L/R)：";cin >> ch;if (ch == "L") {q->setLeft(newSpace); }else {q->setRight(newSpace); }cout << "插入完成！" << endl;break;}}}else if (q->getLeft() == NULL && q->getRight() != NULL){cout << "此节点的左子树可以插入数据。" << endl;while (1){cout << "请输入插入的数据:";cin >> tmp_data;tmp = GetNodePositon(root, tmp_data);if (tmp) {cout << "此数据重复。再次";}else {//开辟空间Node<T>* newSpace = new Node<T>;newSpace->setData(tmp_data);q->setLeft(newSpace);cout << "插入完成！" << endl;break;}}}else if (q->getLeft() != NULL && q->getRight() == NULL){cout << "此节点的右子树可以插入数据。" << endl;while (1){cout << "请输入插入的数据:";cin >> tmp_data;tmp = GetNodePositon(root, tmp_data);if (tmp) {cout << "此数据重复。再次";}else {//开辟空间Node<T>* newSpace = new Node<T>;newSpace->setData(tmp_data);q->setRight(newSpace);cout << "插入完成！" << endl;break;}}}else{cout << "此节点的左右子树都不可以插入数据。" << endl;}}else {cout << "未找到此数据。" << endl;}}else {cout << "这是空树。" << endl;}system("pause");
}template<class T>
void Tree<T>::Desstroy()
{if (root){cout << "销毁" << GetNodeNum(root) << "个数据。" << endl;DestroyBiTree(root);//由于root的数据并未删除，需特殊处理delete root;root = NULL;cout << "完成销毁。" << endl;}else {cout << "这是空树，不能完成销毁这个操作。" << endl;}system("pause");
}template<class T>
void Tree<T>::CreateBiTree(T data)
{queue<Node<T>*> q;// 创建队列，用于按照层次遍历链表q.push(root);while (!q.empty()) {Node<T>* currNode = q.front();// 取出队首节点q.pop();//出队// 如果该节点的左子树为空，则将要添加的值创建成一个新节点，并作为该节点的左子树if (currNode->getLeft() == NULL) {Node<T>* L = new Node<T>;L->setData(data);currNode->setLeft(L);return;}// 如果该节点的左右子树都不为空，则将下一层的节点加入队列中，暂时存放节点else {q.push(currNode->getLeft());}// 如果该节点的右子树为空，则将要添加的值创建成一个新节点，并作为该节点的右子树if (currNode->getRight() == NULL) {Node<T>* R = new Node<T>;R->setData(data);currNode->setRight(R);return;}else {q.push(currNode->getRight());}}
}template<class T>
void Tree<T>::LeadingTree()
{while (1){//线索化树的菜单选择system("cls");//复制二叉树Lroot = Copy(root);if (Lroot == NULL) {cout << "这是空树。" << endl;system("pause"); return;}LeadingChoice_menu();//前驱Node<T>* pre = NULL;string f1 = "";cin >> f1;cout << endl;system("cls");if (f1 == "1") {PreThreading(Lroot, pre);//遍历线索化二叉树cout << "这是先序线索二叉树。-》" << endl;PrePrint(Lroot);}else if (f1 == "2") {InThreading(Lroot,pre);//遍历线索化二叉树cout << "这是中序线索二叉树。-》" << endl;InPrint(Lroot);}else if (f1 == "3") {PostThreading(Lroot, pre);//遍历线索化二叉树cout << "这是后序线索二叉树。-》" << endl;PostPrint(Lroot);}else if (f1 == "0") {break;}DestroyCueTree(Lroot);//销毁这棵树//cout << "线索二叉树销毁完成。" << endl;system("pause");}
}template<class T>
void Tree<T>::DestroyBiTree(Node<T>* node)
{//未删除根节点，先序遍历销毁节点if (node != NULL) {//当左子树为空时，返回DestroyBiTree(node->getLeft());delete node->getLeft();//删除左子树node->setLeft(NULL);//左子树返回后，进行右子树的递归删除DestroyBiTree(node->getRight());delete node->getRight();//删除右子树node->setRight(NULL);}
}template<class T>
void Tree<T>::Use_Traverse(int a)
{if (root) {cout << "数据如下：" << endl;switch (a){case 1:PreOrder(root); break;case 2:InOrder(root); break;case 3:PostOrder(root); break;default:break;}}else {cout << "这是空树。" << endl;}system("pause");
}template<class T>
void Tree<T>::PreOrder(Node<T>* node)
{if (!node) {return;}cout << node->getData() << endl;PreOrder(node->getLeft());PreOrder(node->getRight());
}template<class T>
void Tree<T>::InOrder(Node<T>* node)
{if (!node) {return;}InOrder(node->getLeft());cout << node->getData() << endl;InOrder(node->getRight());
}template<class T>
void Tree<T>::PostOrder(Node<T>* node)
{if (!node) {return;}PostOrder(node->getLeft());PostOrder(node->getRight());cout << node->getData() << endl;
}void run()
{Tree<char> arr;while (1){system("cls");menu();string f1 = "";cin >> f1;cout << endl;if (f1 == "1") {arr.AddData();}if (f1 == "2") {arr.InsertData();}else if (f1 == "3") {arr.Desstroy();}else if (f1 == "4") {arr.AlterNode_data();}else if (f1 == "5") {arr.LookNode_data();}else if (f1 == "6") {arr.Begin_DeleteNode();}else if (f1 == "7") {while (1) {system("cls");status_menu();int n;cin >> n;if (n == 0) {break;}arr.Use_status(n);}}else if (f1 == "8") {while (1) {system("cls");bianli_menu();int n;cin >> n;if (n == 0) {break;}arr.Use_Traverse(n);}}else if (f1 == "X") {cout << "进入线索化界面。" << endl;for (int i = 0; i < 17; i++) {cout << "*";Sleep(100);}arr.LeadingTree();}else if (f1 == "0") {system("cls");cout << "\n\t\t期待您的再次使用！" << endl;break;}}
}int main()
{run();return 0;
}

2、泛型数组树

#include <iostream>
#include <cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<Windows.h>
using namespace std;
template<typename T>
class Tree
{
private:T* arr; // 存储所有节点的数组int size; // 当前节点数量int capacity = 3; // 数组容量初始化为3int root = 0; // 根节点下标int count = 3;//第3层开始扩容
public:// 构造函数Tree();// 析构函数，释放节点数组内存~Tree();//层序添加数据void AddData();//遍历方式void Use_Show(int a);//清空void Clear();//删除void Delete();int getEnd(int i);//深度void LengthTree();
private://查找节点索引int GetNodeIndex(int index, T data);//扩容void Expansion();//增加数据void Add(int index, T data);//遍历的三种方式void PreOrder(int n);	// 前序遍历void InOrder(int n);	// 中序遍历void PostOrder(int n);	// 后序遍历//删除void Delete_Data(int index);
};
template<typename T>
Tree<T>::Tree()
{//数组分配空间并初始化为0，节点数量为0
//int* arr = new int[capacity](); //创建一个大小为 capacity 的动态数组，并将其元素初始化为零arr = new T[capacity];for (int i = 0; i < capacity; i++) {arr[i] = "#";}size = 0;
}
template<typename T>
Tree<T>::~Tree()
{if (arr != NULL) {delete[] arr;}arr = NULL;
}
template<typename T>
void Tree<T>::Use_Show(int a)
{if (size != 0) {cout << "数据如下：" << endl;switch (a){case 1:PreOrder(root); break;case 2:InOrder(root); break;case 3:PostOrder(root); break;default:break;}}else {cout << "这是空树。" << endl;}system("pause");
}
template<typename T>
void Tree<T>::Clear()
{if (size == 0) {cout << "这是空树。" << endl;}else {cout << "开始清空。" << endl;for (int i = 0; i < capacity; i++) {arr[i] = "#";//表示空}cout << "清空" << size << "个数据。" << endl;size = 0;}system("pause");
}
template<typename T>
void Tree<T>::Delete()
{if (arr[root] != "#") {cout << "请输入你想删除的数据：";T data;cin >> data;int i = GetNodeIndex(root, data);//确定此数据的节点if (i != -1){Delete_Data(i);//从根节点开始搜索要删除的节点}else {cout << "未找到此数据。" << endl;}}else {cout << "这是空树。" << endl;}system("pause");
}
template<typename T>
void Tree<T>::LengthTree()
{if (size != 0) {cout << "树的节点个数：" << size << endl;cout << "树的深度是：" << floor(log2(size)) + 1 << endl;}else {cout << "没有树。" << endl;}system("pause");
}
template<class T>
void Tree<T>::PreOrder(int n)
{if (n >= capacity || arr[n] == "#") {return;}cout << arr[n] << endl;PreOrder(2 * n + 1);PreOrder(2 * n + 2);
}
template<class T>
void Tree<T>::InOrder(int n)
{if (n >= capacity || arr[n] == "#") {return;}InOrder(2 * n + 1);cout << arr[n] << endl;InOrder(2 * n + 2);
}
template<class T>
void Tree<T>::PostOrder(int n)
{if (n >= capacity || arr[n] == "#") {return;}PostOrder(2 * n + 1);PostOrder(2 * n + 2);cout << arr[n] << endl;
}template<typename T>
void Tree<T>::Delete_Data(int index)
{int left = 2 * index + 1;int right = 2 * index + 2;//叶子节点直接删除if (arr[left] == "#" && arr[right] == "#") {arr[index] = "#";cout << "删除完成！" << endl;return;}//因为是完全二叉树，只有一个子节点时只可能是左边的else if (arr[right] == "#") {arr[index] = arr[left];arr[left] = "#";cout << "删除完成！" << endl;return;}else {cout << "左右孩子都存在，不能删除。" << endl;}size--;
}
template<typename T>
void Tree<T>::AddData()
{int n;cout << "添加数据个数：";cin >> n;for (int i = 1; i <= n; i++) {cout << "第" << i << "个：";while (1){T data;cin >> data;int c = GetNodeIndex(root, data);//查重函数if (c == -1){if (size >= capacity) {Expansion();//如果节点数大于容量则扩容}if (arr[0] == "#") {arr[0] = data;size++;}else {Add(root, data);}break;}else {cout << "你输入的第" << i << "个数据已经重复，请重新输入数据:";}}}cout << "添加完成" << endl;system("pause");
}
template<typename T>
void Tree<T>::Add(int index, T data)
{queue<int> q;// 创建队列，用于按照层次遍历链表q.push(index);while (!q.empty()){int curIndex = q.front();// 取出队首节点q.pop();//出队int left = curIndex * 2 + 1;int right = curIndex * 2 + 2;// 如果该节点的左子树为空，则将要添加的值创建成一个新节点，并作为该节点的左子树if (arr[left] == "#") {arr[left] = data;size++;return;}// 如果该节点的左右子树都不为空，则将下一层的节点加入队列中，暂时存放节点else {q.push(left);}// 如果该节点的右子树为空，则将要添加的值创建成一个新节点，并作为该节点的右子树if (arr[right] == "#") {arr[right] = data;size++;return;}else {q.push(right);}}
}
template<typename T>
int Tree<T>::GetNodeIndex(int index, T data)
{if (index >= capacity) {return -1;}//递归求下标索引if (arr[index] == data) {return index;  //找到并返回当前节点索引}int left = GetNodeIndex(index * 2 + 1, data); // 在左子树中查找if (left != -1) {return left;  //返回左子树中的节点索引,继续查找}int right = GetNodeIndex(index * 2 + 2, data); // 在右子树中查找if (right != -1) {return right;  //返回右子树中的节点索引}return -1;//未找到目标数据，返回-1/递归，也就是左右子树判断终止的条件
}
template<typename T>
void Tree<T>::Expansion()
{int space = capacity;capacity = capacity + pow(2, count - 1);//扩充的空间T* newArr = new T[capacity]; //创建新数组for (int i = 0; i < capacity; i++) {newArr[i] = "#";}//将原数组数据复制到新数组中if (arr != NULL){for (int i = 0; i < space; i++) {newArr[i] = arr[i];}delete[] arr; //释放旧数组arr = NULL;}arr = newArr;//更新数组
}
void bianli_menu()
{cout << "-1.先序打印" << endl;cout << "-2.中序打印" << endl;cout << "-3.后序打印" << endl;cout << "-0.退出  请选择：";
}
void menu()
{cout << "**********" << endl;cout << "-1.添加" << endl;cout << "-2.清空" << endl;cout << "-3.深度" << endl;cout << "-4.打印" << endl;//*cout << "-5.删除" << endl;//*cout << "-0.退出  请选择：";
}
void run()
{Tree<string> arr;while (1){system("cls");menu();string f1 = "";cin >> f1;cout << endl;if (f1 == "1") {arr.AddData();}else if (f1 == "2") {arr.Clear();}else if (f1 == "3") {arr.LengthTree();}else if (f1 == "5") {arr.Delete();}else if (f1 == "4") {while (1) {system("cls");bianli_menu();int n;cin >> n;if (n == 0) {break;}arr.Use_Show(n);}}else if (f1 == "0") {system("cls");cout << "\n\t\t期待您的再次使用！" << endl;break;}}
}int main()
{run();return 0;
}

3、哈夫曼报文

3.1哈夫曼

#include<iostream>
#include<string>
#include<iomanip>
using namespace std;//struct Node
//{
//    string code, ch;
//    string lchild, rchild, parent, weight;
//    Node(){//结构体构造函数的初始化
//        weight = lchild = rchild = parent = -1;
//        ch = code = "";
//    }
//};class Node
{
public:string code, ch;int lchild, rchild, parent, weight;Node() {//构造函数的初始化weight = lchild = rchild = parent = -1;ch = code = "";}
};void Select(Node HT[], int* a, int* b, int n)//找权值最小的两个a和b
{int w = 0, i; //找最小的数for (i = 0; i < n; i++){if (HT[i].parent != -1)     //判断节点是否已经选过continue;else{if (w == 0)//开始遍历{w = HT[i].weight;//将第一个权值赋给2*a = i;//*a记录w的下标}else{if (HT[i].weight < w)//找到第一个最小的权值{w = HT[i].weight;//转换*a = i;//****找到第一个权值的下标}}}}w = 0; //找第二小的数for (i = 0; i < n; i++){if (HT[i].parent != -1 || (i == *a))//排除已选过的数continue;else{if (w == 0){w = HT[i].weight;*b = i;}else{if (HT[i].weight < w){w = HT[i].weight;*b = i;//找到第二个最小权值的下标}}}}int temp;if (HT[*a].lchild < HT[*b].lchild)//左小右大{temp = *a;*a = *b;*b = temp;}
}void Huff_Tree(Node HT[], int w[], string ch[], int n)
{for (int i = 0; i < 2 * n - 1; i++) //初始过程{//初始化结构体数组的数据HT[i].parent = -1;HT[i].lchild = -1;HT[i].rchild = -1;HT[i].code = "";}for (int i = 0; i < n; i++){//将字符和权值保存HT[i].weight = w[i];HT[i].ch = ch[i];}for (int k = n; k < 2 * n - 1; k++){//找到i1,i2两个最小的权值的下标int i1 = 0, i2 = 0;Select(HT, &i1, &i2, k); //将i1，i2节点合成节点kHT[i1].parent = HT[i2].parent = k;//i1,i2的双亲的下标是kHT[k].weight = HT[i1].weight + HT[i2].weight;//k的权值是i1+i2HT[k].lchild = i1;//k的左右孩子是i1，i2HT[k].rchild = i2;}
}void Huff_Code(Node HT[], int n, int cih)
{int i, j, k;string s = "";for (i = 0; i < n; i++)//共有n个字符的编码{s = "";//存储叶子到根的二进制编码j = i;while (HT[j].parent != -1) //从叶子往上找到根节点{k = HT[j].parent;//k是j的双亲下标if (j == HT[k].lchild) //如果是根的左孩子，则记为0{s = s + "0";//左0右1}else{s = s + "1";}j = HT[j].parent;//更新j的下标，指向双亲}for (int l = s.size() - 1; l >= 0; l--){HT[i].code += s[l]; //保存编码}if (cih == 1) {cout << right << "编码 " <<setw(8) << HT[i].code <<setw(5) << " 的字符："  << HT[i].ch;}else if (cih == 2) {cout << "字符 " << HT[i].ch << " 的编码：" << HT[i].code ;}cout << endl;}
}string Huff_Decode(Node HT[], int n, string s)
{cout << "解码后为：";string temp = "", str = "";//保存解码后的字符串for (int i = 0; i < s.size(); i++)//读取输入的字符串s直至读取结束{temp = temp + s[i];for (int j = 0; j < n; j++)//开始遍历现有 编码{//HT[j].code是所有字符的二进制码if (temp == HT[j].code){str = str + HT[j].ch;//str存放二进制码对应的字符temp = "";//如果找到第一个字符，则清空tempbreak;}else if (i == s.size() - 1 && j == n - 1 && temp != "")//全部遍历后没有{str = "解码错误！";}}}return str;
}string Huff_Char(Node HT[], int n, string s)
{int i = 0;string temp = "", str = "";for (i = 0; i < s.size(); i++) {for (int j = 0; j < n; j++) {if (HT[j].ch[0] == s[i]) {str = str + HT[j].code;break;}}}if (i = s.size() - 1 && str == "") {cout << "编码错误。" << endl;}return str;
}int main()
{while (1){      system("cls");const int n = 9;Node HT[2 * n];string str[] = { "A", "B", "C", "D", "E" ,"F","G"," ","a"};int w[] = { 11,22,22,33,4,5,123,222,34 };Huff_Tree(HT, w, str, n);cout << "1.解码：" << endl;cout << "2.编码" << endl;cout << "0.退出 choice:";int cci;cin >> cci;string s;if (cci == 1) { Huff_Code(HT, n ,cci);cout << "输入：";cin >> s;cout << Huff_Decode(HT, n, s) << endl;system("pause");}else if (cci == 2) {Huff_Code(HT, n, cci);cout << "输入：";char ch = '\0';for (int i = 0; ch != '\n'; i++) {ch = getchar();s[i] = ch;}//cin >> s;getline(cin, s);cout << Huff_Char(HT, n, s) << endl;system("pause");}else if(cci==0) {break;}}cout << "结束使用。" << endl;return 0;
}

3.2哈夫曼编码解码报文

我将头文件和cpp分开了，修改一下即可。

Node.h

#pragma once
class Node
{
private:char ch;//存放字符int weight;//权值Node* left, * right;//左右指针
public:Node():left(nullptr),right(nullptr),weight(0),ch(0){}Node(char c, int w) {ch = c;weight = w;left = right = nullptr;}void setLeft(Node* l) {this->left = l;}Node* getLeft(){return left;}void setRight(Node* r) {this->right = r;}Node* getRight() {return right;}void setWeight(int w) {this->weight = w;}int getWeight() {return weight;}void setCh(char ch) {this->ch = ch;}char getCh() {return ch;}
};

haffman.cpp

#include"Node.h"
#include<iostream>
#include<queue>
#include<string>
#include<fstream>
#include<sstream>
#include<iomanip>
using namespace std;
class bigsmall {
public:bool operator()(Node* a,Node* b){return a->getWeight() > b->getWeight();//比较两个指针所指向节点的权值的大小//表示为a的优先级比b高}
};
class HuffmanTree
{
public:HuffmanTree();      //构造函数~HuffmanTree();     //析构函数void Destroy(Node* root);     void BuildTree(string str);   //构造哈夫曼树void BuildCode(Node* node, string code,string codes[]); //递归函数，用于构建编码表和输出编码void PrintSign();   //现有字符和编码void PrintCode();   //输出哈夫曼编码void PrintChar();   //输出解码void LookCode();    //查看二进制编码string Read_txt(const char* file);//读取报文void Write_txt(const char* file, string str);
private:Node* root;//根节点priority_queue<Node*, vector<Node*>, bigsmall> pq;  //优先队列string charset;//字符集int freq[95] = { 0 };//int a = 0;//选择
};HuffmanTree::HuffmanTree()
{root = nullptr;
}HuffmanTree::~HuffmanTree()
{Destroy(root);cout << "退出成功。" << endl;
}void HuffmanTree::Destroy(Node* root)
{    if (root != NULL){Destroy(root->getLeft());Destroy(root->getRight());delete root;root = NULL;}
}void HuffmanTree::BuildTree(string str)//根据统计的字符集charset，建树
{//得到字符集charset = str;//统计字符出现频率,ascll是32到126for (char c : charset) {//这是增强型for循环字符串，等于 for (int i = 0; i < s.length(); i++)freq[(int)c - 32]++;}// 插入节点到优先队列，32--126的字符常见for (int i = 0; i < 95; i++) {if (freq[i] > 0) {//出现次数大于0，即存在pq.push(new Node(char(i + 32), freq[i]));//构造函数}}//贪心算法/堆/优先队列while (pq.size() > 1) {Node* left = pq.top();//权值最小的一个字符pq.pop();Node* right = pq.top();//权值第二小的一个字符pq.pop();Node* parent = new Node(0 , left->getWeight() + right->getWeight());//0是ascll第一个，双亲权值parent->setLeft(left);parent->setRight(right);//因为是优先队列，所以parent在压入队列是已经根据大小去插队了pq.push(parent);}root = pq.top();//最后一个数据(最大的)做根节点pq.pop();
}
//递归构建编码表
void HuffmanTree::BuildCode(Node* node, string code,string codes[])
{if (node == nullptr) {return;}if (node->getCh() != 0) {//因为存放0的节点都没放字符codes[int(node->getCh()) - 32] = code;//codes数组存放的是该字符ascll对应的编码}BuildCode(node->getLeft(), code + '0', codes);//左子树求编码BuildCode(node->getRight(), code + '1', codes);//右子树求编码
}
void HuffmanTree::PrintSign()
{if (root == nullptr) {return;}string codes[95];BuildCode(root, "", codes);string str = charset;//记录字符的二进制编码string s = "";for (int j = 0; j < str.size(); j++) {//外层循环遍历编码集for (int i = 0; i < 95; i++) {//内层循环遍历字符集对应的编码if (str[j] == char(i+32)) {s = s + codes[i];break;}}}Write_txt("binary.txt", s);//将该字符的二进制编码存入文件里cout << "现有字符的编码对应表：" << endl;cout << "+-------------------------------+" << endl;cout << "| 字符 |       编码      | 权值 |" << endl;cout << "+-------------------------------+" << endl;for (int i = 0; i < 95; i++) {//内层循环遍历字符集对应的编码if (freq[i] > 0) {cout << left << "|  " <<setw(4) <<  char(i+32) << "|  "<<setw(13) << codes[i] << "  | " <<setw(5)<<  freq[i] <<"|" << endl;cout << "+-------------------------------+" << endl;}}
}
//输出哈夫曼编码
void HuffmanTree::PrintCode()
{if (root == nullptr) {return;}string codes[95];BuildCode(root, "", codes);cout << "请输入你的数据：";string cha = "";char ch = getchar();//消灭缓存区的回车getline(cin, cha);//存取读到的字符串for (int i = 0; i < cha.size(); i++) {if (freq[int(cha[i]) - 32] == 0) {cout << "你输入的字符串里的字符在文件里不存在。" << endl;return;}}for (int j = 0; j < cha.size(); j++) {//外层循环遍历编码集for (int i = 0; i < 95; i++) {//内层循环遍历字符集对应的编码if (cha[j] == char(i+32)) {cout << codes[i] ;break;}}}cout << endl;
}
//根据二进制编码输出对应的数据
void HuffmanTree::PrintChar()
{if (root == nullptr) {return;}string codes[95];BuildCode(root, "", codes);cout << "请输入你的二进制编码：";string str = "";cin >> str; string arr = "";//存放字符数据string s = "";//s临时存放二进制编码string ps = "";//判断编码是否完全读取成功int max = 0;for (int j = 0; j < str.size(); j++) {if (str[j] == '0')continue;if (str[j] == '1')continue;cout << "输入二进制编码错误。" << endl; return;}//寻找最长的二进制编码for (int i = 0; i < 95; i++) {if (max < codes[i].size())max = codes[i].size();}for (int j = 0; j < str.size(); j++) {//外层循环遍历编码集s = s + str[j];//临时存放编码if (s.size() > max) {cout << "解析失败。" << endl;return;}for (int i = 0; i < 95; i++) {//内层循环遍历字符集对应的编码if (s==codes[i]) {arr += char(32 + i);ps += codes[i];s = "";break;}  }}//如果编码遍历完毕，则ps=str 否则是str最后几个字符无法识别if (ps == str) {cout << arr << endl;}else {cout << "你的二进制编码有误。" << endl;}
}void HuffmanTree::LookCode()
{string ssw = Read_txt("binary.txt");cout << "转换的二进制编码：";cout << ssw << endl;
}string HuffmanTree::Read_txt(const char* file)//从文件读入到string里
{ifstream ifile(file);//打开文件file//将文件读入到stringstream对象buf中，buf存储内容stringstream buf;char ch;while (buf && ifile.get(ch)) {buf.put(ch);}//使用str()函数将ostringstream的对象buf中的缓冲区内容转换成字符串返回return buf.str();
}void HuffmanTree::Write_txt(const char* file, string str)
{ofstream ofs(file);ofs << str;ofs.close();
}void run()
{while (1) {system("cls");HuffmanTree tree;string str = tree.Read_txt("ch.txt");//先统计字符tree.BuildTree(str);//构造哈夫曼树cout << "*******" << endl;cout << "1.编码" << endl;cout << "2.解码" << endl;cout << "3.查看编码表" << endl;cout << "4.查看编码" << endl;cout << "0.退出 选择：" << endl;string ch = "";cin >> ch;if (ch == "1") {//1是字符转编码tree.PrintCode();system("pause");}else if (ch == "2") {//2是编码转字符tree.PrintChar();system("pause");}else if (ch == "3") {tree.PrintSign();system("pause");}else if (ch == "4") {tree.LookCode();system("pause");}else if (ch == "0") {break;}}
}int main()
{run();return 0;
}