09年自考《数据结构》各章要点二[3]

树的前序遍历与相对应的二叉树的前序遍历一致;树的后序遍历与相对应的二叉树的中序遍历一致

树的带权路径长度是树中所有叶结点的带权路径长度之和树的带权路径长度最小的二叉树就称为最优二叉树(即哈夫曼树)

在叶子的权值相同的二叉树中完全二叉树的路径长度最短

哈夫曼树有n个叶结点共有n个结点没有度为的结点这类树又称为严格二叉树

变长编码技术可以使频度高的字符编码短而频度低的字符编码长但是变长编码可能使解码产生二义性如这三个码无法在解码时确定是哪一个所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀这种码称为前缀码(其实是非前缀码)

哈夫曼树的应用最广泛地是在编码技术上它能够容易地求出给定字符集及其概率分布的最优前缀码哈夫曼编码的构造很容易只要画好了哈夫曼树按分支情况在左路径上写代码右路径上写代码然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码

第七章 图

图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的即任意两个结点之间之间都可能相关

图GraphG=(VE)V是顶点的有穷非空集合E是顶点偶对的有穷集

有向图Digraph每条边有方向

无向图Undigraph每条边没有方向

有向完全图具有n*(n)条边的有向图

无向完全图具有n*(n)/条边的无向图

有根图有一个顶点有路径到达其它顶点的有向图

简单路径是经过顶点不同的路径

简单回路是开始和终端重合的简单路径

网络是带权的图

[] [] [] [] [] [] [] [] [] [] [] []