算法

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

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

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

第 2 页,共 2 页12