一、哈夫曼树的概念 先来理解几个概念： 路径：树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路径长度：路径上的分支数目称作路径长度。 树的路径长度：从树根到每一个结点的路径长度之和。、 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。 通常记作：   公式中，Wk为第k个叶子结点的权值；Lk为该结点 […]

已知一棵二叉树的先序遍历为： ABDGCEFH 中序遍历为： DGBAECHF 求二叉树后序遍历。 分析：先序遍历序列的第一个字符为根结点。对于中序遍历，根结点在中序遍历序列的中间，左边部分是根结点的左子树的中序遍历序列，右边部分是根结点的右子树的中序遍历序列。   先序：ABDGCEFH  →  A   BDG   CEFH […]

字符串匹配是我们经常遇到的问题，就是在原字符串中查找子串在原字符串中首次出现的位置。 1. Brute force. 首先我们能想到的，也是最传统的做法就是暴力搜索。 利用计数指针i和j指示主串S和模式串T中当前正待比较的字符位置，从主串S的第pos个字符起和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较。直到模式T中的每个字符依次和主串S中的 […]