Tag二叉树

哈夫曼树的编码与解码

我又要开更一些比较低端的玩意了,作为自己学习的笔记 今天来说一下如何建立一棵哈夫曼树以及如何利用哈夫曼树对字符串进行编码和解码。 在这之前首先应该了解一下什么是哈夫曼树(最优二叉树):给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 带权路径长度:为所有叶子结点的带权路径长度之和。这么说或许还是有点抽象,带权路径长度简单可以这么理解: 一条路的路程长度为2,一条路的路程长度为6,那么从根节点到第一个叶子结点的带权路径长度为2+6=8,以此类推其他的带权路径长度也可以知道 哈夫曼树被称为最优二叉树,究其原因就是带权路径长度最短。所以它在一些编码方面使用的比较广泛。 在使用哈夫曼树进行编码解码的时候我们需要把这个问题拆解成几个小问题来处理 1...

二叉树的实现以及先中后序遍历

好久没有记录自己的数据结构的学习进度了,现在来写一下最近的二叉树的创建和先中后序遍历 首先来说一下二叉树的创建,二叉树的创建实际上很简单,原理是使用递归调用,递归调用的一个好处就是不用自己设计Stack,使用的系统的Stack,这样就省去了一些麻烦 这里就不解释递归的工作原理了,直接上代码 C++ BiTree createBtree(BiTree *root){ char temp; scanf("%c",&temp); if(temp == '$') return NULL; if(!(*root)){ *root = (BiTree)calloc(1,sizeof(struct BTNode)); } (*root)->data = temp; createBtree(&((*root)->lchild));...

Your sidebar area is currently empty. Hurry up and add some widgets.