电子元器件外贸网站建设,微网站获取访客手机,网站系统使用手册,wordpress漏洞 2014哈夫曼树
完整可编译运行代码见#xff1a;Github::Data-Structures-Algorithms-and-Applications/_29huffmanTree
定长编码与可变长编码
定长编码
每个字符都用固定长度的编码来表示。
例如假设一个文本是由字符 a、u、x 和 z 组成的字符串#xff0c;每个字符用2位二进…哈夫曼树
完整可编译运行代码见Github::Data-Structures-Algorithms-and-Applications/_29huffmanTree
定长编码与可变长编码
定长编码
每个字符都用固定长度的编码来表示。
例如假设一个文本是由字符 a、u、x 和 z 组成的字符串每个字符用2位二进制来编码00a01x10u11z。利用此编码方法字符串aaxuaxz的编码为00000110000111。解码时从左到右每次从编码中提取2位数字通过编码表翻译便可获得原字符串。
可变长编码
字符存在不同长度的编码。 哈夫曼编码是一种可变长编码。
在字符串 aaxuaxz 中a 出现 3 次。一个符号出现的次数称为频率frequency。符号 a、x、u、z在这个字符串中出现的频率分别是3、2、1、1。当不同字符出现的频率有很大差别时我们可以通过可变长编码来缩短编码串的长度。
例如如果使用编码0a10x110u111z则aaxuaxz的编码为0010110010111编码串长度是13位比原来的14位要稍短一些。当不同字符的出现频率相差更大时编码串的长度差别就会更明显。如果4个字符的频率分别为996211则每个字符用2位编码所得到编码串长度为2000位而用可变长编码所得到编码串长度仅为1006位。
为了保证正确解码要求编码时没有任何一个代码是另一个代码的前缀。
可以使用二叉树来实现可变长编码从根到外部节点的路径可用来编码用0表示向左子树移动一步用1表示向右子树移动一步。由于路径是从根节点到叶子节点因此没有一个路径编码是另一个路径编码的前缀。
编码位串长度
可以对字符ab…f编码。令S是由这些字符组成的字符串Fx是字符 x 的出现频率其中 x 属于集合{ascdef}。若利用这些代码对 S 进行编码则编码位串的长度 2 ∗ F ( a ) 3 ∗ F ( b ) 3 ∗ F ( c ) 3 ∗ F ( d ) 3 ∗ F ( e ) 2 ∗ F ( f ) 2*F(a)3*F(b)3*F(c)3*F(d)3*F(e)2*F(f) 2∗F(a)3∗F(b)3∗F(c)3∗F(d)3∗F(e)2∗F(f) 对于一颗有n个外部节点的二叉树且外部节点标记为1…, n则对应的位串长度为 W E P ∑ i 1 n L ( i ) ∗ F ( i ) WEP \sum_{i1}^nL(i) * F(i) WEPi1∑nL(i)∗F(i) 其中Li从根到外部节点i的路径长度即路径的边数WEP是二叉树的加权外部路径长度weighted external path length。为了缩短编码串的长度必须使用二叉树代码二叉树的外部节点与要编码的字符串的字符对应且WEP最小。一棵二叉树如果对一组给定的频率其 WEP 最小那么这棵二叉树称为霍夫曼树Huffman tree。
哈夫曼编码
哈夫曼编码的流程
1确定字符串的符号和它们出现的频率。 2建立霍夫曼树其中外部节点用字符串中的符号表示外部节点的权用相应符号的频率表示。 3沿着从根到外部节点的路径遍历取得每个符号的代码。 4用代码替代字符串中的符号。
为了便于解码需要保存从符号到代码的映射表或每个符号的频率表。
构造霍夫曼树的过程是首先建立一组二叉树集合每棵二叉树仅含一个外部节点每个外部节点代表字符串的一个符号其权等于该符号的频率。然后不断从集合中选择两棵权最小的二叉树把它们合并成一棵新的二叉树合并方法是增加一个根节点把这两棵二叉树分别作为左右子树。新二叉树的权是两棵子树的权之和。这个过程一直持续到仅剩下一棵树为止。
举例如图所示 构建哈夫曼树
main.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2023年12月15日21点59分
Last Version: V1.0
Descriptions: 哈夫曼树的构建函数与main函数
*/
#include _28binaryTreeChains.h
#include huffmanNode.htemplate class T
binaryTreeChainsint* huffmanTree(T weight[], int n)
{// 建立一个二叉树集合每个节点的weight为weight[i]tree为element为i左右子树为空的树vectorhuffmanNodeT hNode(n);binaryTreeChainsint emptyTree;for (int i 1; i n; i){hNode[i-1].weight weight[i-1];hNode[i-1].tree new binaryTreeChainsint;hNode[i-1].tree-makeTree(i, emptyTree, emptyTree);}// 将节点存储为一个小根堆std::priority_queuehuffmanNodeT, std::vectorhuffmanNodeT, std::greater heap(hNode.begin(),hNode.end());// 从小根堆里面不断合并树// 直到小根堆里只有一颗树huffmanNodeT w, x, y;binaryTreeChainsint *z;for (int i 1; i n; i){// 从小根堆取出两个元素x heap.top(); heap.pop();y heap.top(); heap.pop();// 将两棵树合并为一颗树z new binaryTreeChainsint;z-makeTree(0, *x.tree, *y.tree);w.weight x.weight y.weight;w.tree z;heap.push(w);delete x.tree;delete y.tree;}// 返回小根堆里的最后一颗树return heap.top().tree;
}int main()
{int a[5];int n 5;for (int i 1; i n; i)a[i-1] 2 * i;binaryTreeChainsint *x huffmanTree(a, n);x-postOrderOutput();x-preOrderOutput();x-inOrderOutput();return 0;
}huffmanNode.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2023年12月15日21点59分
Last Version: V1.0
Descriptions: 哈夫曼树的结点结构体
*/
#ifndef _29HUFFMANTREE_HUFFMANNODE_H
#define _29HUFFMANTREE_HUFFMANNODE_H
#include _28binaryTreeChains.h
templateclass T
struct huffmanNode
{binaryTreeChainsint *tree{};// 对于外部节点element域的值是它所表示的符号对于内部节点element域的值是0。T weight;// 表示符号出现的频率huffmanNode(){weight 0;}explicit huffmanNode(T pweight){weight pweight;}operator T () const {return weight;}bool operator(const huffmanNode a) const { return weight a.weight; }
};#endif //_29HUFFMANTREE_HUFFMANNODE_H_28binaryTreeChains.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月27日09点44分
Last Version: V1.0
Descriptions: 用链表表示的二叉树.h
笔记1.静态函数指针初始化格式void (*binaryTreeChainsE::visit)(binaryTreeNodeE*) 0;2.不能单独专门化成员模板函数只能针对整个类专门化。3.在模板函数中可以使用typeid()区别对待特定数据类型。
本程序注意事项1.所有关于前缀、后缀、中缀表达式的全部使用了char类型代表元素char类型数组存储整个表达式
*/
#pragma once
#ifndef _BINARYTREECHAINS_H_
#define _BINARYTREECHAINS_H_
#include iostream
#include vector
#include cstring
#include stack
#include queue
#include _1myExceptions.h
#include _28binaryTreeNode.h
#include _28binaryTree.h
using namespace std;templateclass E
class binaryTreeChains : public binaryTreebinaryTreeNodeE
{
public:/*二叉树的基础成员函数*//*构造函数函数*/binaryTreeChains() {root nullptr; treeSize 0;}/*练习44:编写类linkedBinaryTree的一个复制构造函数。测试代码。*//* 计算时间复杂性。复制构造函数*/binaryTreeChains(binaryTreeChainsE m) {root treeCreateTree(m.root);}/*练习题33和练习题35*//*构造函数---先序和中序遍历或后序和中序创建二叉树*//*flag false时是先序和中序遍历构建二叉树flag true时是后序和中序构建二叉树*/binaryTreeChains(E preOrPostOrder[], E inOrder[],int length,bool flag){if(flag false)root preInCreateTree(preOrPostOrder, inOrder, length);elseroot postInCreateTree(preOrPostOrder, inOrder, length);}/*构造函数---前缀或后缀或中缀表达式创建二叉树*//*练习37当flag 1时前缀表达式创建二叉树当flag 2时中缀表达式创建二叉树练习36当flag 3时后缀表达式创建二叉树*/binaryTreeChains(E expression[], int length,int flag){switch (flag){case 1:root preExprCreateTree(expression, length);break;case 2:root inExprCreateTree(expression, length);break;case 3:root postExprCreateTree(expression, length);break;}}/*析构函数*/~binaryTreeChains() { erase(); }/*当树为空时返回true否则返回false*/bool empty() const { return treeSize 0; }/*返回元素个数*/int size() const { return treeSize; }/*前序遍历二叉树使用函数指针的目的是是的本函数可以实现多种目的*/void preOrder(void(*theVisit)(binaryTreeNodeE*)){visit theVisit;/*是因为递归所以才要这样的*/preOrder(root);/*这里调用的是成员函数preOrder()*/}/*前序遍历---输出endl*/void preOrderOutput() { preOrder(output); cout endl; }/*前序遍历---不使用递归而使用迭代函数*/vectorE iterativePreOrder();/*中序遍历二叉树使用函数指针的目的是是的本函数可以实现多种目的*/void inOrder(void(*theVisit)(binaryTreeNodeE*)){visit theVisit;/*是因为递归所以才要这样的*/inOrder(root);/*这里调用的是静态成员函数inOrder()*/}/*中序遍历---输出endl*/void inOrderOutput() { inOrder(output); cout endl; }/*中序遍历---不使用递归而使用迭代函数*/vectorE iterativeInOrder();/*后续遍历二叉树使用函数指针的目的是是的本函数可以实现多种目的*/void postOrder(void(*theVisit)(binaryTreeNodeE*)){visit theVisit;/*是因为递归所以才要这样的*/postOrder(root);/*这里调用的是静态成员函数inOrder()*/}/*后序遍历---输出endl*/void postOrderOutput() { postOrder(output); cout endl; }/*后序遍历---不使用递归而使用迭代函数*/vectorE iterativePostOrder();/*层次遍历二叉树*/void levelOrder(void (*theVisit)(binaryTreeNodeE*));/*层次遍历---输出endl*/void levelOrderOutput() { levelOrder(output); cout endl; }/*清空二叉树 这里必须使用后序遍历 不然会出错*/void erase(){postOrder(dispose);root nullptr;treeSize 0;}/*输入时为了将root根节点传递给createBiTree()函数*/void input(void){createBiTree(root);}/*是一个手动创建二叉树的函数使用本函数得手动设置各节点之间的关系见信号放大器应用的使用*//*将左数和右数合并为一个树(也就是this树)*/void makeTree(const E element, binaryTreeChainsE, binaryTreeChainsE);/*练习45比较二叉树*this和二叉树m*/bool compare(binaryTreeChainsE m){return compareTree(root, m.root);}/*练习46交换每一个结点的左右子树*/void swapTrees(){swapTrees(root);}/*练习27计算二叉树高度*/int height() const { return height(root); }/*练习47计算二叉树的最大高度差*/int maxHeightDifference(){return maxHeightDifference(root);}/*练习29计算二叉树在那一层具有最多的结点---返回值为结点最多的层*/int layerMaxNumOfNode();/*计算二叉树在在哪一层具有最多的结点--返回值为结点最多的层的结点数量*/int maxNumOfNodeInLayer();/*二叉树表达式的成员函数*//*计算树的表达式的值*/int compulateTree(){return compulateTree(root);}
private:/*二叉树基础私有成员*/binaryTreeNodeE* root;//指向根的指针int treeSize;//树的结点个数static void (*visit)(binaryTreeNodeE*);//是一个函数指针,返回值为void 函数参数为binaryTreeNodeE*static void preOrder(binaryTreeNodeE* t);static void inOrder(binaryTreeNodeE* t);static void postOrder(binaryTreeNodeE* t);static void dispose(binaryTreeNodeE* t) { delete t; }static void output(binaryTreeNodeE* t) { cout t-element ; }/*创建二叉树---递归---作为私有成员只能被成员函数调用*/void createBiTree(binaryTreeNodeE* tree);/*复制构造函数调用的函数*/binaryTreeNodeE* treeCreateTree(binaryTreeNodeE* node);/*私有成员函数---用于比较二叉树compare()*/bool compareTree(binaryTreeNodeE* thisNode, binaryTreeNodeE* xNode);/*私有成员函数---交换树的每个结点的左右子树---递归*/void swapTrees(binaryTreeNodeE* node);/*私有成员函数---计算二叉树高度---返回根为node的树的高度*/int height(binaryTreeNodeE* node) const;/*私有成员函数---计算结点node的左右子树高度的差值*/int heightDifference(binaryTreeNodeE* node) const;/*私有成员函数---计算二叉树的最大高度差---返回值为二叉树的最大高度差*/int maxHeightDifference(binaryTreeNodeE* node) const;binaryTreeNodeE* preInCreateTree(E preOrder[], E inOrder[], int size);binaryTreeNodeE* postInCreateTree(E postOrder[], E inOrder[], int size);/*二叉树表达式的私有成员*//*计算树的表达式的值*//*本程序所有关于前缀、中缀、后缀表达式的处理全部是char类型并且只能进行个位数的计算*/int compulateTree(binaryTreeNodeE* node) const;binaryTreeNodeE* preExprCreateTree(E expression[], int length);binaryTreeNodeE* inExprCreateTree(E expression[], int length);binaryTreeNodeE* postExprCreateTree(E expression[], int length);
};/*私有静态成员初始化*/
/*这里是静态函数指针成员的初始化不初始化会引发LINK错误*/
templateclass E
void (*binaryTreeChainsE::visit)(binaryTreeNodeE*) 0; // visit function/*二叉树的普通成员函数*/
/*前序遍历 递归*/
templateclass E
void binaryTreeChainsE::preOrder(binaryTreeNodeE* t)
{if (t ! nullptr){visit(t);/*访问树根*/preOrder(t-leftChild);/*前序遍历左子树*/preOrder(t-rightChild);/*前序遍历右子树*/}
}
/*前序遍历---不使用递归而使用迭代函数*/
templateclass E
vectorE binaryTreeChainsE::iterativePreOrder()
{binaryTreeNodeE* currentNode root;stackbinaryTreeNodeE* st;vectorE result;/*写法1---前序中序后序遍历非递归统一版*//*首先将父节点入栈*/if (currentNode ! nullptr)st.push(currentNode);while (!st.empty()){currentNode st.top();st.pop();/*如果遇到nullptr,则输出当前栈顶元素*/if (currentNode nullptr){result.push_back(st.top()-element);st.pop();}/*如果没有遇到nullptr,则按照右左中的顺序入栈结点最后入栈nullptr*/else{if (currentNode-rightChild ! nullptr)st.push(currentNode-rightChild);if (currentNode-leftChild ! nullptr)st.push(currentNode-leftChild);st.push(currentNode);/*每次都在已遍历的根节点后入栈nullptr*/st.push(nullptr);}}///*写法2*////*当结点为nullptr并且栈为空时结束循环*///while (currentNode ! nullptr || !st.empty())//{// /*先将左边的左边的元素入栈*/// while (currentNode ! nullptr)// {// st.push(currentNode);// result.push_back(currentNode-element);// currentNode currentNode-leftChild;// }// /*然后一个一个遍历左边的元素并将该元素存储到vector中*/// currentNode st.top();// st.pop();// currentNode currentNode-rightChild;//}return result;
}/*中序遍历 递归*/
templateclass E
void binaryTreeChainsE::inOrder(binaryTreeNodeE* t)
{if (t ! nullptr){inOrder(t-leftChild);/*中序遍历左子树*/visit(t);/*访问树根*/inOrder(t-rightChild);/*中序遍历右子树*/}
}
/*中序遍历---不使用递归而使用迭代函数*/
templateclass E
vectorE binaryTreeChainsE::iterativeInOrder()
{binaryTreeNodeE* currentNode root;stackbinaryTreeNodeE* st;vectorE result;/*写法1---前序中序后序遍历非递归统一版*//*首先将父节点入栈*/if (currentNode ! nullptr)st.push(currentNode);while (!st.empty()){currentNode st.top();st.pop();/*如果遇到nullptr,则输出当前栈顶元素*/if (currentNode nullptr){result.push_back(st.top()-element);st.pop();}/*如果没有遇到nullptr,则按照右左中的顺序入栈结点最后入栈nullptr*/else{if (currentNode-rightChild ! nullptr)st.push(currentNode-rightChild);st.push(currentNode);/*每次都在已遍历的根节点后入栈nullptr*/st.push(nullptr);if (currentNode-leftChild ! nullptr)st.push(currentNode-leftChild);}}/*写法2*////*当结点为nullptr并且栈为空时结束循环*///while (currentNode ! nullptr || !st.empty())//{// /*先将左边的左边的元素入栈*/// while (currentNode ! nullptr)// {// st.push(currentNode);// currentNode currentNode-leftChild;// }// /*然后一个一个遍历左边的元素并将该元素存储到vector中*/// currentNode st.top();// st.pop();// result.push_back(currentNode-element);// currentNode currentNode-rightChild;//}return result;
}/*后序遍历 递归*/
templateclass E
void binaryTreeChainsE::postOrder(binaryTreeNodeE* t)
{if (t ! nullptr){postOrder(t-leftChild);/*后序遍历左子树*/postOrder(t-rightChild);/*后序遍历右子树*/visit(t);/*访问树根*/}
}
/*后序遍历---不使用递归而使用迭代函数*/
templateclass E
vectorE binaryTreeChainsE::iterativePostOrder()
{binaryTreeNodeE* currentNode root;stackbinaryTreeNodeE* st;vectorE result;/*前序中序后序遍历非递归统一版*//*首先将父节点入栈*/if (currentNode ! nullptr)st.push(currentNode);while (!st.empty()){currentNode st.top();st.pop();/*如果遇到nullptr,则输出当前栈顶元素*/if (currentNode nullptr){result.push_back(st.top()-element);st.pop();}/*如果没有遇到nullptr,则按照右左中的顺序入栈结点最后入栈nullptr*/else{st.push(currentNode);/*每次都在已遍历的根节点后入栈nullptr*/st.push(nullptr);if (currentNode-rightChild ! nullptr)st.push(currentNode-rightChild);if (currentNode-leftChild ! nullptr)st.push(currentNode-leftChild);}}return result;
}/*层次遍历二叉树 非递归*/
templateclass E
void binaryTreeChainsE::levelOrder(void (*theVisit)(binaryTreeNodeE*))
{visit theVisit;binaryTreeNodeE* temp;queuebinaryTreeNodeE* que;que.push(root);while (!que.empty()){temp que.front();que.pop();visit(temp);if (temp-leftChild ! nullptr)que.push(temp-leftChild);if (temp-rightChild ! nullptr)que.push(temp-rightChild);}
}
/*创建二叉树---递归---模板的实现*/
templateclass E
void binaryTreeChainsE::createBiTree(binaryTreeNodeE* tree)
{E data;cout Please enter the tree element:;while (!(cin data)){cin.clear();//清空标志位while (cin.get() ! \n)//删除无效的输入continue;cout Please enter the tree element:;}cin.get();/*针对char类型的特例*/if (typeid(data) typeid(char)) {if (data #)tree nullptr;else {treeSize;tree new binaryTreeNodeE(data);createBiTree(tree-leftChild);createBiTree(tree-rightChild);}/*关于二叉树对于设置信号放大器的应用我新定义了成员函数maketree()生成二叉树这里会报错C2228“.degradeFromParent”的左边必须有类/结构/联合我实在是不知道怎么改*///else if (typeid(data) typeid(booster))// if (data.degradeFromParent 999)// tree nullptr;// else// {// treeSize;// tree new binaryTreeNodeE(data);// createBiTree(tree-leftChild);// createBiTree(tree-rightChild);// }}else/*针对其他类型*/{if (data 999)tree nullptr;//当遇到999时令树的根节点为nullptr,从而结束该分支的递归else{treeSize;tree new binaryTreeNodeE(data);createBiTree(tree-leftChild);createBiTree(tree-rightChild);}}
}
/*是一个手动创建二叉树的函数使用本函数得手动设置各节点之间的关系见信号放大器应用的使用*/
/*将左树和右树合并为一个树*/
templateclass E
void binaryTreeChainsE::makeTree(const E element, binaryTreeChainsE left, binaryTreeChainsE right)
{// Combine left, right, and element to make new tree.// left, right, and this must be different trees.// create combined treeroot new binaryTreeNodeE(element, left.root, right.root);treeSize left.treeSize right.treeSize 1;// deny access from trees left and rightleft.root right.root NULL;left.treeSize right.treeSize 0;
}/*练习24根据二叉树创建二叉树---用于复制构造函数*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::treeCreateTree(binaryTreeNodeE* node)
{binaryTreeNodeE* head nullptr;if (node ! nullptr){treeSize;
// cout node-element node-element endl;head new binaryTreeNodeE(node-element);head-leftChild treeCreateTree(node-leftChild);head-rightChild treeCreateTree(node-rightChild);}return head;
}/*练习45私有成员函数---用于比较二叉树compare()*/
templateclass E
bool binaryTreeChainsE::compareTree(binaryTreeNodeE* thisNode, binaryTreeNodeE* xNode)
{/*两个结点都为空时二叉树相等*/if (thisNode nullptr xNode nullptr)return true;/*一个结点为空一个结点非空则二叉树不相等*/if ((thisNode nullptr xNode ! nullptr) || (thisNode ! nullptr xNode nullptr))return false;/*两个结点的元素不等则二叉树不相等*/if (thisNode-element ! xNode-element)return false;else/*两个结点相等则比较彼此的左子树和右子树*/return compareTree(thisNode-leftChild, xNode-leftChild) compareTree(thisNode-rightChild, xNode-rightChild);
}/*练习46私有成员函数---交换树的每个结点的左右子树---递归*/
templateclass E
void binaryTreeChainsE::swapTrees(binaryTreeNodeE* node)
{if (node ! nullptr){swapTrees(node-leftChild);swapTrees(node-rightChild);binaryTreeNodeE* temp node-leftChild;node-leftChild node-rightChild;node-rightChild temp;}
}/*练习27私有成员函数---计算二叉树高度---返回根为node的树的高度*/
templateclass E
int binaryTreeChainsE::height(binaryTreeNodeE* node) const
{if (node nullptr)return 0;int hl height(node-leftChild);int hr height(node -rightChild);if (hl hr)return hl;elsereturn hr;
}/*私有成员函数---计算结点node的左右子树高度的差值*/
templateclass E
int binaryTreeChainsE::heightDifference(binaryTreeNodeE* node) const
{if (node nullptr)return 0;int lh height(node-leftChild);int rh height(node-rightChild);
// cout node-element : lh endl;
// cout node-element : rh endl;if (lh rh)return lh - rh;elsereturn rh - lh;
}/*练习47私有成员函数---计算二叉树的最大高度差---返回值为二叉树的最大高度差*/
templateclass E
int binaryTreeChainsE::maxHeightDifference(binaryTreeNodeE* node) const
{if (node nullptr)return 0;int height heightDifference(node);//当前结点的左右子树的高度差int hl maxHeightDifference(node-leftChild);//当前结点的左子树的左右子树的高度差int hr maxHeightDifference(node-rightChild);//当前结点的右子树的左右子树的高度差if (height hl height hr)return height;else if (hl height hl hr)return hl;else if (hr height hr hl)return hr;
}/*练习29计算二叉树在那一层具有最多的结点---返回值为结点最多的层*/
/*当二叉树为空时返回0*/
templateclass E
int binaryTreeChainsE::layerMaxNumOfNode()
{if (root nullptr)return 0;int num 0;//累加每层的结点数int layer 0;//记录当前的层数int maxNum 0;//存储结点最多的层的结点个数int maxLayer 0;//存储结点最多的层的层数binaryTreeNodeE* lastNode root;//存储上一层最后一个结点的元素位置binaryTreeNodeE* nextNode nullptr;//存储当前层最后一个结点的元素位置binaryTreeNodeE* currentNode;queuebinaryTreeNodeE* que;que.push(root);while (!que.empty()){currentNode que.front();que.pop();num;if (currentNode-leftChild ! nullptr){que.push(currentNode-leftChild);nextNode currentNode-leftChild;}if (currentNode-rightChild ! nullptr){que.push(currentNode-rightChild);nextNode currentNode-rightChild;}if (currentNode lastNode){layer;//刚刚处理完第几层lastNode nextNode;nextNode nullptr;if (num maxNum){maxNum num;maxLayer layer;}num 0;}}return maxLayer;
}/*计算二叉树在在哪一层具有最多的结点--返回值为结点最多的层的结点数量*/
/*当二叉树为空时返回0*/
templateclass E
int binaryTreeChainsE::maxNumOfNodeInLayer()
{if (root nullptr)return 0;int num 0;//累加每层的结点数int layer 0;//记录当前的层数int maxNum 0;//存储结点最多的层的结点个数int maxLayer 0;//存储结点最多的层的层数binaryTreeNodeE* lastNode root;//存储上一层最后一个结点的元素位置binaryTreeNodeE* nextNode nullptr;//存储当前层最后一个结点的元素位置binaryTreeNodeE* currentNode nullptr;queuebinaryTreeNodeE* que;que.push(root);while (!que.empty()){currentNode que.front();que.pop();num;if (currentNode-leftChild ! nullptr){que.push(currentNode-leftChild);nextNode currentNode-leftChild;}if (currentNode-rightChild ! nullptr){que.push(currentNode-rightChild);nextNode currentNode-rightChild;}if (currentNode lastNode){layer;//刚刚处理完第几层lastNode nextNode;nextNode nullptr;if (num maxNum){maxNum num;maxLayer layer;}num 0;}}return maxNum;
}/*使用前序和中序遍历构建二叉树*/
/*关键点在于找到根节点在中序中的位置该位置之前为该根的左子树该位置之后为该根的右子树*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::preInCreateTree(E preOrder[], E inOrder[], int size)
{/*如果没有左右子树则返回nullptr*/if (size 0)return nullptr;binaryTreeNodeE* rootData new binaryTreeNodeE(preOrder[0]);/*找到根节点的位置中序中该位置左侧就是该根节点的左子树该位置右侧就是该根节点的右子树*/int rootLoc findRootLocE(inOrder, preOrder[0] ,size);/*创建左子树和右子树*/rootData-leftChild preInCreateTree(preOrder 1, inOrder, rootLoc);rootData-rightChild preInCreateTree(preOrder 1 rootLoc, inOrder rootLoc 1, size - 1 - rootLoc);return rootData;
}
/*使用后序和中序遍历构建二叉树*/
/*关键点在于找到根节点在中序中的位置该位置之前为该根的左子树该位置之后为该根的右子树*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::postInCreateTree(E postOrder[], E inOrder[], int size)
{/*如果没有左右子树则返回nullptr*/if (size 0)return nullptr;binaryTreeNodeE* rootData new binaryTreeNodeE(postOrder[size-1]);/*找到根节点的位置中序中该位置左侧就是该根节点的左子树该位置右侧就是该根节点的右子树*/int rootLoc findRootLocE(inOrder, postOrder[size-1], size);/*创建左子树和右子树*/rootData-leftChild postInCreateTree(postOrder, inOrder, rootLoc);rootData-rightChild postInCreateTree(postOrder rootLoc, inOrder rootLoc 1, size - 1 - rootLoc);return rootData;
}/*二叉树表达式的成员函数*/
/*计算树的表达式的值*/
/*用字符串记录表达式*/
/*这个函数需要使用char类型的树其他类型的二叉树不满足要求*/
templateclass E
int binaryTreeChainsE::compulateTree(binaryTreeNodeE* node) const
{if (node nullptr)return 0;if (node-leftChild nullptr node-rightChild nullptr) //左右子树都是nullptr时说明它是叶子节点而叶子结点就是数而非符号return node-element - 0;//就返回叶子结点int a compulateTree(node-leftChild);//先计算左子树int b compulateTree(node-rightChild);//再计算右子树switch (node-element)//当前结点不是叶子节点时说明他是符号结点{case :return a b;case -:return a - b;case *:return a * b;case /:if (b ! 0)return a / b;elsethrow illegalParameterValue(除数不能为0);}
}/*使用全部是二元操作符的前缀表达式创建二叉树*/
/*从尾元素开始遍历表达式的元素*/
/*如果是数据则生成binaryTreeNode并入栈*/
/*如果不是数据则生成binaryTreeNode从栈中弹出两个数据形成其子树,第一个弹出的是其左子树第二个弹出的是其右子树然后再将当前结点入栈*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::preExprCreateTree(E expression[],int length)
{stackbinaryTreeNodeE* st;//用于存储已经处理的数据生成的binaryTreeNodebinaryTreeNodeE* temp nullptr;for (int i length-1; i 0; i--){/*如果是数据则生成二叉树结点入栈*/if (expression[i] 0 expression[i] 9){temp new binaryTreeNodeE(expression[i]);st.push(temp);}else{temp new binaryTreeNodeE(expression[i]);temp-leftChild st.top();st.pop();temp-rightChild st.top();st.pop();st.push(temp);}}return temp;
}/*使用全部是二元操作符的中缀表达式(包含括号以表明优先级)创建二叉树*/
/*如果是数据则生成binaryTreeNode并入数据栈*/
/*
操作符处理规则如果当前操作符优先级大于操作符栈的顶部元素直接入操作符栈如果当前操作符优先级小于或等于操作符栈的顶部元素先将顶部元素出操作符栈再将当前操作符入操作符栈当前操作符为左括号时直接入栈当前操作符为右括号时让栈顶到左括号为止的操作符出操作符栈括号不出现在后缀表达式中
出操作符栈时生成当前符号的binaryTreeNode其右子树为数据栈的栈顶元素数据栈顶元素出栈其左子树为数据栈当前的栈顶元素数据栈顶元素出栈当前符号binaryTreeNode入数据栈。
*/
/*获取操作符优先级的getPriority()函数是一个非成员函数*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::inExprCreateTree(E expression[], int length)
{stackbinaryTreeNodeE* st;//用于存储已经处理的数据生成的binaryTreeNodestackE opStack;binaryTreeNodeE* temp nullptr;E data;for (int i 0; i length; i){data expression[i];/*如果是数据则生成二叉树结点入栈*/if (data 0 data 9){temp new binaryTreeNodeE(data);st.push(temp);}else{if (opStack.empty())opStack.push(data);elseswitch (data){case (:opStack.push(data); break;//当遇到左括号时直接将其入栈case )://当遇到右括号时让栈顶到左括号的操作符出栈while (opStack.top() ! (){temp new binaryTreeNodeE(opStack.top());opStack.pop();temp-rightChild st.top();st.pop();temp-leftChild st.top();st.pop();st.push(temp);}opStack.pop();//让(出栈break;/*当遇到 - * /时,当其优先级大于栈顶元素时入栈否则先将栈顶元素出栈再将当前元素入栈*/case :case -:case *:case /:if (getPriority(data) getPriority(opStack.top()))opStack.push(data);else{temp new binaryTreeNodeE(opStack.top());opStack.pop();temp-rightChild st.top();st.pop();temp-leftChild st.top();st.pop();st.push(temp);}break;default:break;}/*当检查到中缀表达式的最后一个元素且栈非空时将栈中的元素全部输出到后缀表达式*/if (!opStack.empty() i length - 1)while (!opStack.empty()){temp new binaryTreeNodeE(opStack.top());opStack.pop();temp-rightChild st.top();st.pop();temp-leftChild st.top();st.pop();st.push(temp);}}}return temp;
}/*使用全部是二元操作符的后缀表达式创建二叉树*/
/*从首元素开始遍历表达式的元素*/
/*如果是数据则生成binaryTreeNode并入栈*/
/*如果不是数据则生成binaryTreeNode从栈中弹出两个数据形成其子树,第一个弹出的是其右子树第二个弹出的是其左子树然后再将当前结点入栈*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::postExprCreateTree(E expression[], int length)
{stackbinaryTreeNodeE* st;//用于存储已经处理的数据生成的binaryTreeNodebinaryTreeNodeE* temp nullptr;for (int i 0; i length; i){/*如果是数据则生成二叉树结点入栈*/if (expression[i] 0 expression[i] 9){temp new binaryTreeNodeE(expression[i]);st.push(temp);}else{temp new binaryTreeNodeE(expression[i]);temp-rightChild st.top();st.pop();temp-leftChild st.top();st.pop();st.push(temp);}}return temp;
}#endif_28binaryTree.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月27日09点43分
Last Version: V1.0
Descriptions: 二叉树的抽象类
*/
#pragma once
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
templateclass T
class binaryTree
{
public:virtual ~binaryTree() {}virtual bool empty() const 0;virtual int size() const 0;virtual void preOrder(void (*)(T*)) 0;virtual void inOrder(void (*)(T*)) 0;virtual void postOrder(void (*)(T*)) 0;virtual void levelOrder(void (*)(T*)) 0;
};
#endif_28binaryTreeNode.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月27日09点44分
Last Version: V1.0
Descriptions: 二叉树的结点结构体
*/
#pragma once
#ifndef _BINARYTREENODE_H_
#define _BINARYTREENODE_H_
templateclass T
struct binaryTreeNode
{T element;binaryTreeNodeT* leftChild,//左子树*rightChild;//右子树/*默认构造函数*/binaryTreeNode() { leftChild rightChild nullptr; }/*只初始化element*/binaryTreeNode(T melement){element melement;leftChild rightChild nullptr;}/*三个元素都初始化*/binaryTreeNode(T melement, binaryTreeNodeT* mleftChild, binaryTreeNodeT* mrightChild){element melement;leftChild mleftChild;rightChild mrightChild;}
};#endif_1myExceptions.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include string
#includeiostreamusing namespace std;// illegal parameter value
class illegalParameterValue
{
public:illegalParameterValue(string theMessage Illegal parameter value){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// illegal input data
class illegalInputData
{
public:illegalInputData(string theMessage Illegal data input){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// illegal index
class illegalIndex
{
public:illegalIndex(string theMessage Illegal index){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// matrix index out of bounds
class matrixIndexOutOfBounds
{
public:matrixIndexOutOfBounds(string theMessage Matrix index out of bounds){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// matrix size mismatch
class matrixSizeMismatch
{
public:matrixSizeMismatch(string theMessage The size of the two matrics doesnt match){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// stack is empty
class stackEmpty
{
public:stackEmpty(string theMessage Invalid operation on empty stack){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// queue is empty
class queueEmpty
{
public:queueEmpty(string theMessage Invalid operation on empty queue){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// hash table is full
class hashTableFull
{
public:hashTableFull(string theMessage The hash table is full){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// edge weight undefined
class undefinedEdgeWeight
{
public:undefinedEdgeWeight(string theMessage No edge weights defined){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// method undefined
class undefinedMethod
{
public:undefinedMethod(string theMessage This method is undefined){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};
#endif运行结果
C:\Users\15495\Documents\Jasmine\prj\_Algorithm\Data Structures, Algorithms and Applications in C\_29huffmanTree\cmake-build-debug\_29huffmanTree.exe
3 1 2 0 0 4 5 0 0
0 0 3 0 1 2 0 4 5
3 0 1 0 2 0 4 0 5Process finished with exit code 0
