3.4-3.6树.pptxVIP

A B C E D F G;typedef struct TreeNode { elemtype data; struct TreeNode *son; struct TreeNode *next; } nodetype;; ;后（根）序遍历;A;3.5 树、森林与二叉树的转换;请作练习： 将如图所示的树转换成二叉树。;G;G;3.6 二叉树的应用;基本概念 路径：树中一个结点到另一个结点之间的分支构成了两个结点之间的路径。 路径长度：分支数目。 树的路径长度：根到每一个叶结点之间的路径长度之和。 结点的带权路径长度： 根到结点的路径长度×该结点的权值。 树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和。; 可见对于一组确定权值的叶结点可以构造出多个具有不同WPL的二叉树，其中具有最小WPL的二叉树称为哈夫曼树（或最优二叉树）。 ;1) 初始化：分别以这n个结点作为根，建立n棵树。每棵树只有一个根结点。将这些树组成一个集合F。 2) 在集合F中选择树根的权值最小和次小的两棵树，以它们分别作为左右子树，生成一个新的二叉树。新的二叉树的根的权值为左、右两个子树根的权值之和。 3) 在F中删除这两个树，同时加上新生成的树。 4) 重复2)、3)，直到F中只剩下一个树。 这棵树就是满足要求的最优二叉树。;哈夫曼树的构造过程;哈夫曼编码;设给出一段报文： CAST CAST SAT AT A TASA;哈夫曼编码是一种前缀编码，解码时不会混淆。