数据结构PPT教学课件-第6章 树.ppt

第6章 树 6.2 二叉树 6.3 遍 历 二 叉 树 6.4 线 索 二 叉 树 6.5 二叉树、树和森林 6.6 树的应用 6.7 二叉树的建立和遍历C语言源程序示例 (1) p结点无右孩子, 则让p的左孩子s上移替代p结点， 如图6.20(a)、 (b)所示。  (2) p结点无左孩子, 则让p的右孩子s上移替代p结点， 如图6.20(c)、 (d)所示。  (3) p结点有左孩子和右孩子, 可用它的前趋（或后继）结点s代替p结点。现假定用它的后继结点来代替, 这个结点s应是p的右子树中数据域值最小的结点, 或者说是p的右子树中最左结点。 因其值域最小(在右子树中)， 所以它一定没有左孩子。 这时先让p结点取s结点的值, 然后可按第(2)种情况处理删除s结点, 这就等效删除了原p结点。 如图6.20(e)所示。  参见算法6.19, 其中t, f, p为已知条件, t指向根结点, f指向p的双亲, p指向被删除结点。 另设s, q指针, 分别指向替代结点及其双亲。  算法6.19 ?Void delet(struct node *t, struct node *p, struct node *f) ｛ bool＝1;  　 if(p-lch==NULL) s＝p-rch;  　 　 else if (p-rch==NULL) s＝p-lch;  　　　 　 else ｛ q=p; s＝p-rch; /* p左, 右孩子均 不空的情况 */ while(s-lch ! =NULL) ｛ q＝s; s＝s-lch; ｝ if (q==p) q-rch＝s-rch;  else q-lch＝s-rch;  p-data＝s-data;  free(s); bool＝0; /* 删除完成 */ ｝ if (bool==1) /* p不是有左, 右两个孩子的情况 */ ｛ if(f==NULL) t＝s; /* f==NULL即是p==t情况 */ 6.6.2 哈夫曼树及其应用 哈夫曼树（Huffman）, 又称最优二叉树, 是一类带权路径长度最短的树, 有着广泛的应用。  1. 哈夫曼树的基本概念 在讨论哈夫曼树之前首先需要弄清楚关于路径和路径长度的概念。 树中两个结点之间的路径由一个结点到另一结点的分支构成。 两结点之间的路径长度是路径上分支的数目。树的路径长度是从根结点到每一个结点的路径长度之和。  设一棵二叉树有n个叶子结点, 每个叶子结点拥有一个权值Ｗ1,Ｗ2, …,Ｗn, 从根结点到每个叶子结点的路径长度分别为L1, L2,…, Ln, 那么树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和， 通常记作: 为了直观起见, 在图中把带权的叶子结点画成方形, 其它非叶子结点仍为圆形。请看图6.21中的三棵二叉树以及它们的带权路径长。  请注意, 这三棵二叉树叶子结点数相同, 它们的权值也相同, 但是它们的WPL带权路径长各不相同。 图6.21(c)WPL最小。 它就是哈夫曼树, 最优树。哈夫曼树是在具有同一组权值的叶子结点的不同二叉树中, 带权路径长度最短的树也称最优树。  2. 哈夫曼树的构造及其算法 1) 构造哈夫曼树的方法 对于已知的一组叶子的权值Ｗ1,Ｗ2,…,Ｗn : (1) 首先把n个叶子结点看做n棵树（有一个结点的二叉树）, 把它们看做一个森林。  (2) 在森林中把权值最小和次小的两棵树合并成一棵树, 该树根结点的权值是两棵子树权值之和。这时森林中还有n-1棵树。  (3) 重复第(2)步直到森林中只有一棵为止。 此树就是哈夫曼树。  现给一组(n=4)具体的权值{2, 4, 5, 8}, 图 6.22是构造哈夫曼树的具体过程。 2) 哈夫曼算法实现 讨论算法实现需选择合适的存储结构, 这里选用的是顺序存储结构。 因为哈夫曼树中没有度为1的结点。 由二叉树性质可知n0 ＝ n2 ＋1, 而现在