文档介绍：1 第5章树和二叉树( Tree & Binary Tree ) 树的基本概念 二叉树 遍历二叉树和线索二叉树 树和森林 哈夫曼树及其应用特点: 非线性结构,一个直接前驱,但可能有多个直接后继( 1:n)2回顾 1——二叉树的存储顺序、二叉链表、三叉链表、静态链表 ABCDFE root data parent leftChild rightChild 012345 A -1 1 -1 B 0 2 3 C 1 -1 -1 D 1 4 5 E 3 -1 -1 F 3 -1 -1 3回顾 2——最小值问题?求n个数的最小值算法(位置?) ?求n个数的最小值和次小值算法(位置?) (1)以 a[0] 作为最小值 min 和次小值 secondMin ; (2)对 a[1]~ a[n-1] 之间的每一个数 a[i], 判别< min <= secondMin < 4 void min1To2(int a[ ], int n, int & pos 1, int & pos 2){ // 求n个数的最小值和次小值算法 pos1 = pos2 = 0; //第一个作为最小值和次小值 for ( int j = 1 ; j < n; j++) //检测 if (T[j] < T[pos1]) { //选最小 pos2 = pos1 ; //更新次小 pos1 = j ; } else if (T[j] < T[pos2]) //选次小 pos2 = j ; }算法是否有缺陷?? 5 void min1To2(int a[ ], int n, int &pos1, int &pos2){ // 求n个数的最小值和次小值位置的算法 if(a[0]>a[1]) pos1 = 1,pos2 = 0; else pos1 = 0,pos2 = 1; for ( int j = 2; j < n; j++) //检测 if ( a[j ] < a[pos1]) { //选最小 pos2 = pos1; //更新次小 pos1 = j; } else if ( a[j ] < a[pos2]) //选次小 pos2 = j; } 6提前介绍:二叉树的应用平衡树——排序树——字典树——判定树——带权树——最优树——特点:左右子树深度差≤1 特点: “左小右大”由字符串构成的二叉排序树例如, 12个球只称 3次分出轻重特点:路径长度带权值带权路径长度最短的树,又称 Huffman 树,用途之一是通信中的压缩编码。 7 路径: 路径长度: 树的路径长度: 带权路径长度: 树的带权路径长度: 哈夫曼树: Huffman 树及其应用一、最优二叉树( 哈夫曼树) 由一结点到另一结点间的分支所构成路径上的分支数目从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积预备知识:若干术语 d e b ac f g 树中所有叶子结点的带权路径长度之和带权路径长度最小的树 a→e的路径长度= 树长度= 210 ( Weighted Path Length, WPL) 8 Huffman 树简介: 树的带权路径长度如何计算? WPL = ? w kl kk=1 n a b d c7 524 (a) cda b 2457 (b) bd ac 7524 (c) 经典之例: 经典之例: WPL= 36 WPL= 46 WPL= 35 哈夫曼树则是:WPL 最小的树。 Huffman 树 Weighted Path Length 9 ①①在在 F F 中中选取两棵根结点的权值最小选取两棵根结点的权值最小的扩充二叉树的扩充二叉树, , 做为左、做为左、右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的根结点的权根结点的权值为其左、右子树上根结点的权值之和值为其