2022年数据结构课件可用 .pdf

《2022年数据结构课件可用 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课件可用 .pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第五章树和二叉树从本章开始，讨论更复杂的数据结构（非线性的数据结构）和其他问题树形结构是一种十分重要的数据结构。本章讨论的二叉树、树和树林都属于树形结构在树形结构中每个结点最多只有一个前驱，但可有多个后继的结构其共同之处是都表示某种具有层次性的分支关系25.1树与树林的概念5.2二叉树5.3二叉树的实现5.4二叉树的应用5.5树和树林的基本运算和实现35.1 树与树林5.1.1 树的定义5.1.2 一些基本概念5.1.3 树林45.1.1 树 (Tree) 的定义树的例子： 家族树，机构的结构假设 A 有子女 B, C；B 和 C 分别有子女D, E, F 和 G, H; E 有子女 I ,

2、 J。T = (N, R) ，其中：N = A, B, C, D, E, F, G, H, I, J R = , , , , , , , 关系有层次性，总是高层与低层相关，同层之间无关系，也没有低层到高层的关系。与不同元素相关的元素互不相交5树的表示方法：基本图形表示ABCDEFIJGH凹入表6(A (B (D ) (E (I) (J) (C (G) (H)嵌套括号表示法CDEIJFGHAB文氏图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 19 页 - - - - -

3、 - - - - 7树是 n (n 0) 个结点的有限集 T。T非空时满足：1. 有且仅有一个特殊的称为根的结点 r2. 除根结点外，其余结点可分为m（m 0）个互不相交的非空有限集T1, T2, , Tm，其中每个集合又是一棵非空树，称为r 的子树 (subtree)树的定义（递归定义）：? 结点数为 0 的树称为空树? 一棵树也可以没有子树（m = 0），此时这棵树只包含一个根结点? 如有子树，则子树非空（使子树的个数能够定义）85.1.2 基本术语(a) 树t(b) 树t 有序树 和无序树 ：树中子树的顺序是否重要9父结点 ，子结点，边兄弟结点祖先 ，子孙路径，路径长度结点的层数（根的层

4、为0）深度或高度（结点的最大层数）结点的度数 、树的度数树叶 、分支结点结点的顺序（最左，仅在考虑有序树时有意义）10树林 ：m（m0）棵互不相交的树的集合5.1.3 树林注意树与树林的关系：? 树由根和子树 树林 构成，树林由一集树组成一棵非空树是一个二元组Tree = (root, F) ，其中? root 是树根结点? F 是 m（m 0）棵子树构成的树林? F = (T1, T2, , Tm)。Ti 称为根 root 的第 i 棵子树（有序树的情况。对无序树：F = T1, T2, , Tm ）115.2 二叉树二叉树是另一种树形结构：元素也有层次性，只有从上层元素到下一层元素的关联，

5、与同一层的不同元素所关联的元素互不相交，每个元素只与下层的两个元素相关联5.2.1 二叉树的基本概念5.2.2 二叉树的性质5.2.3 二叉树的基本运算5.2.4 二叉树的周游12定义：二叉树 是结点的有限集合，该集合或为空集，或由一个根及两棵不相交的二叉树组成（递归定义）二叉树的两棵子树分别称作它的（其根的）“左子树”和“右子树”5.2.1 二叉树的基本概念二叉树的特点：? 一个结点至多有两棵子树? 子树有 左右 之分二叉树是与树不同的结构（并不是树的特殊情况）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

6、- - - - - - 第 2 页，共 19 页 - - - - - - - - - 13二叉树的基本形态：?左子树右子树右子树左子树空二叉树只有根结点左子树非空右子树空左子树空右子树非空左、右子树都不空14二叉树不是树的特殊情形，它们是两个不同概念。主要差别在于二叉树的子树分左子树和右子树，即使只有一棵子树也要明确指出是左子树还是右子树。下面是两棵不同的二叉树，但作为树是相同的：在二叉树中可定义与树中类似的各种概念：父/子结点，祖先/子孙，路径及其长度，结点的层数和度数，二叉树的高度，树叶和分支结点等等下面介绍另外一些概念15满二叉树 ：每个非叶结点都有两棵非空子树完全二叉树 ：只有最下两层

7、结点的度数可小于2，如果最下一层结点不满，则空位都集中在右边，左边没有空位16扩充二叉树扩充一些结点，使原树结点的度数都变成2扩充二叉树里新增的外部结点个数比原内部结点的个数多1。“ 外部路径长度 ”E：扩充二叉树里从根到各外部结点的路径长度之和。 “ 内部路径长度 ”I ：扩充二叉树里从根到各内部结点的路径长度之和。（n是内部结点的个数）E = I + 2n17性质 1.非空二叉树第i 层上至多有2i 个结点 (i 0)性质 2.高度为 k 的二叉树至多有2k+1-1 个结点 (k 0)性质 3.对任何非空二叉树T ，若叶结点个数为n0，度数为2 的结点个数为n2，则 n0 = n2 + 1

8、性质 4.n 个结点的完全二叉树的高度k 为log2n性质 5.满二叉树里的叶结点比分支结点多一个5.2.2 二叉树的一些性质这些性质都很容易从空树或者只有一个结点的二叉树出发，通过归纳法证明18性质 6.（完全二叉树）如果n 个结点的完全二叉树按层次按顺序从 1 开始编号，对任一结点i（1 i n) 都有：1.序号 1的结点是根；i 1时其双亲结点是i/22.若 2i n，其左子女结点序号为2i。否则无左子女3.若 2i+1 n，其右子女结点序号为2i+1; 否则无右子女A B C D E F G1 2 3 4 5 6 7A B C D E F G H1 2 3 4 5 6 7 8名师资料总

9、结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 19 页 - - - - - - - - - 19如果完全二叉树中的结点从0 开始编号，也有类似性质：1.序号 0 的结点为根；2.非根结点i 的父结点编号是(i 1)/2 ；3.结点的两个子结点（若存在）的编号分别为2i+1和2i+2。完全二叉树的特点：? 可以方便地存入一系列连续位置（存入一个数组）? 不需要另外保存其他信息，直接根据数组下标就可以找到一个结点的子结点或者父结点205.2.3 二叉树基本运算?创建空二叉树BinTr

10、ee createEmptyBinTree();?创建一棵二叉树，其根为r，左右子树分别是l 和 rBinTree consBinTree(BinTreeNoder, BinTree l, BinTreer);?判断二叉树是否为空int isEmpty(BinTree t);?求二叉树的根结点，若为空，则返回一特殊值BinTreeNode* root(BinTree t);?求二叉树中某个指定结点的父结点，当指定结点为根时，返回一特殊值BinTreeNode* parent (BinTreet , BinTreeNode p);21?求二叉树t 中某指定结点p 的左子女结点，当指定结点没有左子

11、女时，返回一特殊值BinTreeNode* leftChild( BinTree t ,BinTreeNode* p )?求二叉树t 中某个指定结点p 的右子女结点，当指定结点没有右子女时，返回一特殊值BinTreeNode* rightChild( BinTree t ,BinTreeNode* p )?二叉树的周游由于二叉树概念是递归定义的，二叉树中的每个结点可唯一标识以这个结点为根的二叉树，所以在具体实现时常常把二叉树类型和二叉树中结点类型看成是同一种类型采用这种观点可能使某些算法的描述更方便225.2.4 二叉树的周游二叉树的周游(Traversing ，遍历 )：按某种顺序访问二叉树

12、中所有结点 ，每个结点访问一次且仅一次任何遍历所有结点的过程都是“ 周游 ” 。由于是要实现算法，我们必须采取某种系统化的方式同样有 “ 深度优先方式 ” 和“ 广度优先方式 ”DLR三种基本的深度优先周游方式：先根序(DLR)对称序(LDR)后根序(LRD)23ABDCEFIHG二叉树在各种周游方法中，如果遇到树空都立即结束先根序（先访问根结点，而后以同样方式周游左右子树）A B D C E G F H I后根序（先以同样方式周游左右子树，而后访问根结点）D B G E H I F C A对称序（中根序）（先以同样方式周游左子树，而后访问根结点，最后再以同样方式周游右子树）D B A E G

13、 C H F I24周游序列：?把按先根次序对一棵二叉树周游得到的线性结点（数据）序列称为这棵二叉树的先根序列?将按后根次序周游一棵二叉树得到的线性结点（数据）称为这棵二叉树的后根序列?将按对称次序周游一棵二叉树得到的线性结点（数据）称为这棵二叉树的对称（中根）序列?对给定二叉树，可唯一确定其先根序列、后根序列和对称序列。反过来，给定一个二叉树的任一种周游序列，无法唯一确定这个二叉树?如果已知某二叉树的对称序列，又知另一周游序列（无论先根序列还是后根序列），都可唯一确定这个二叉树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

14、师精心整理 - - - - - - - 第 4 页，共 19 页 - - - - - - - - - 25广度优先方式的周游? 在二叉树中从0 到树的高度逐层访问各层的结点? 在每层里从左到右逐个访问结点? 二叉树的广度优先周游又称层次序周游? 按广度优先顺序访问形成的结点（数据）序列，称为相应二叉树的层次序列ABDCEFIHG二叉树A B C D E F G H I26-+abcd表达式 (a b) / (c + d)的二叉树表示表达式可以自然地用二叉树表示：运算符是根，运算对象是其左右子树对表达式树先根、后根和中根序周游得到的结点序列：先根： -a b + c d 前缀表示后根： a b

15、c d + 后缀表示 ( 波兰表示法 )对称序： a b c + d 中缀表示27二叉树的周游算法递归算法?先根序?中根序（对称序）?后根序非递归算法(自己用栈保存后面周游所需的信息)?先根序?中根序?后根序现在讨论抽象周游算法，它们只依赖于二叉树抽象数据类型。有了具体表示后，很容易把它们变成具体算法28递归周游算法周游操作的抽象规范：先根次序周游：void preOrder(BinTree t); 中根次序周游：void inOrder(BinTree t);后根次序周游：void postOrder(BinTree t);/* 二叉树的先根序（先序）周游*/void preOrder( B

16、inTreep) if (p=NULL) return;visit(root(p);preOrder(leftChild(p);preOrder(rightChild(p);29/* 二叉树的中根序（中序，对称序）周游*/void inOrder(BinTreep) if (p = NULL) return;inOrder(leftChild(p);visit(root(p);inOrder(rightChild(p);/* 二叉树的后根序（后序）周游*/void postOrder(BinTreep) if (p = NULL) return;postOrder(leftChild(p);p

17、ostOrder(rightChild(p);visit(root(p);30非递归的周游算法利用栈的帮助，可以写出各种深度优先周游的非递归算法利用队列的帮助，可以写出层次序的周游算法下面给出的算法中并不涉及具体的存储结构，其中对栈或队列的使用，也不依赖于具体表示方式在选择了具体的二叉树实现结构，可以对这里的算法做适当的改造，转变为针对具体二叉树实现的具体算法（还可能可以适当精化），就可以上机运行了具体的算法实现中可以选择适当的栈或者队列实现方式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

18、 - 第 5 页，共 19 页 - - - - - - - - - 31先根序周游的非递归算法采用非递归算法实现先根次序周游二叉树的主要思路：? 首先把根结点压入栈中? 从栈中取出栈顶元素（并退栈）? 取出的元素非空时访问该结点，然后顺序将其右子结点和左子结点（若非空）进栈，重复? 当栈为空时，周游结束。算法中每个二叉树结点恰好进/出栈一次，所以其时间代价为O(n) ，其中 n为二叉树中结点的个数32void norecPreOrder(BinTree t) Stack s;/* 栈元素类型为(BinTreeNode*) */BinTreeNode *c;if (t = = NULL) ret

19、urn;s =createEmptyStack();push(s, root(t);while (!isEmptyStack(s) /* 栈不空则继续*/c = top(s); pop(s);/*取栈顶，退栈 */visit(c);/* 访问 */if (!isEmpty(rightChild(c) push(s,rightChild(c); if (!isEmpty(leftChild(c) push(s,leftChild(c);也可以在入栈时不检查，出栈时检查是否为空33中根序（对称序）周游的非递归算法采用非递归算法实现对称序周游二叉树的主要思路：? 当前二叉树不空或者栈不空时继续? 若

20、二叉树不空时则沿其左子树前进，在前进过程中把所经过的结点逐个压入栈中? 当左子树为空时，弹出栈顶元素并访问这个结点? 如果这个结点有右子树，再进入它的右子树并从头执行上述过程；如果它没有右子树，则弹出栈顶元素，回到前面继续执行? 到当前二叉树为空并且栈也为空时周游结束。34void norecInOrder(BinTree t) Stack s = createEmptyStack(); /* 栈元素为 (BinTreeNode*) */BinTreeNode* c = root(t);while ( !isEmpty(c) | !isEmptyStack(s) while ( !isEmpt

21、y(c) ) push(s, c); c = leftChild(c);c = top(s); pop(s);visit(c);c = rightChild(c);35后根序周游的非递归算法每个问题都可能有多种不同的算法，下面介绍本问题的一种算法（是比较简短的算法）不变关系：?栈中结点是对二叉树的划分，左边是已周游部分?栈中每个结点的父结点总是它下面那个结点?当前结点的父结点是栈顶?根据本结点是其父结点的左子结点或右子结点，可以决定下一步怎么做算法里的主要技术是“ 下行循环 ” ：找到下一个应访问的结点36void norecPostOrder( PBinTreet ) Stack st =

22、createEmptyStack( );BinTreeNode * p = root(t);while ( !isEmpty(p) | !isEmptyStack(st) ) while (!isEmpty(p) /* 循环到栈顶结点的两子树都空*/push( st, p ); p = leftChild(p);if (isEmpty(p) p = rightChild(top(st);p = top(st); pop(st); /* 栈顶是应访问结点*/visit(p); /* 当前结点已访问*/if ( !isEmptyStack(st) & leftChild(top(st) = p )

23、/* 栈不空且当前结点是栈顶的左子结点*/p = rightChild(top(st) ; else p = NULL; /* 从右子树返回则强迫退栈*/名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 19 页 - - - - - - - - - 37书上另给出了两个算法，一个标记各结点访问到左子树还是右子树，第三个先把全部结点按后序的逆序压栈（压入根，后按同样方式压入右子树和左子树）。在弹出过程中逐个访问三个算法的时间复杂性都是O(n) ，n 为二叉树结点数第三个算法的

24、空间复杂性（栈）与二叉树结点数成正比，另外两个算法空间复杂性与最长路径的长度成正比最坏情况下两者具有同样数量级（有些二叉树里存在特别长的路径）。一般而言不是这样通过对二叉树的计数分析（“ 图论” 的工作），可知二叉树的平均结点个数n 与最长路径的长度L 的关系是：n = O(2L)第三个算法（第一版）在空间复杂性方面有缺陷38层次序周游的非递归算法根据广度优先周游的思想比较简单：? 利用一个队列实现? 首先把二叉树送入队列? 其后，每当从队首取出一个二叉树访问之后，马上把它的子二叉树按从左到右的次序送入队列尾端? 重复此过程直到队列为空39void levelOrder(BinTree t)

25、BinTreeNode *c, *cc;Queue q = createEmptyQueue();/*元素为 (BinTreeNode*)*/if ( t= NULL) return; /*空二叉树返回 */c = root(t); enQueue(q,c); /*将二叉树送入队列*/while ( !isEmptyQueue(q) ) c = frontQueue(q);deQueue(q);visit( root( c ) ); /*从队列取结点并访问*/if ( !isEmpty(leftChild(c) ) enQueue(q, leftChild(c); if ( !isEmpty(

26、rightChild(c) ) enQueue(q, rightChild(c);405.3 二叉树的存储表示5.3.1 顺序表示5.3.2 链接表示5.3.3 二叉树的生成5.3.4 线索二叉树41用一组连续存储单元按层次序存储完全二叉树的结点。可以方便地从子结点找父结点，从父结点找子结点。5.3.1 顺序表示ABCGFEDHIJA B C D E F G H I J下标 0 1 2 3 4 5 6 7 8 942一般二叉树可扩充到完全二叉树后存储入一维数组。一般二叉树及其顺序表示用顺序方式存储非完全二叉树时，数组里可能出现大量空位，因此可能浪费大量存储空间名师资料总结 - - -精品资料欢

27、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 19 页 - - - - - - - - - 43二叉树顺序表示的类型声明：typedef struct SeqBTree /* 顺序树类型定义*/int n; /* 改造成完全二叉树后的结点个数*/DataType nodelistMAXNODE; SeqBTree, *PSeqBTree;nodelist 数组元素表示结点。二叉树抽象数据类型的操作都可以映射到这里如果用动态顺序表的实现方式，最大结点数可作为参数提供给二叉树的创建函数，数组溢出时可以通过程

28、序扩充空间445.3.2 链接表示用链接表示来存储二叉树? 每个树结点对应链接结构中的一个结点? 二叉树是非线性结构，每个结点最多两个后继，最常用的链接表示方式是左-右指针表示法? 结点中除存储结点数据外，还包含两个指针llink 和rlink ，分别存放本结点的左子结点和右子结点信息（通用指针）? 当结点的某个子树为空时，相应的指针为空指针。45具体定义的结构和类型：typedef struct BNode BNode, *PBNode; /* 结点和指针类型*/typedef struct BNode*BinTree;/* 注意，和 PBNode 一样 */struct BNode /*

29、二叉树结点*/DataType info; /* 数据域 */BinTree llink;/* 指向左子女*/BinTree rlink; /* 指向右子女*/; 二叉树的许多处理可用递归算法描述，为方便，没对二叉树进行封装，直接将二叉树定义为指向结点的指针类型有些操作可能要改二叉树的根，为方便描述，可定义：typedef BinTree*PBinTree;46ABDCEFIHGtAB C EF I H G D 二叉树的链接表示求左右子结点的操作极其简单，就是直接取结构成分47求父结点操作较难实现，只能从根周游，检查当前结点是否所求结点的父结点。最坏时间代价为O(n) 。若求父结点的操作使用频

30、繁，可采用三叉链表表示，加一个父结点指针。但这样也增加了空间开销48二叉树的构造创建二叉树与表示方式有关。用顺序表示时，应先扩充为完全二叉树（用特殊符号表示无结点），按层次方式列出，直接读入并装入数组创建链接二叉树有多种方式。这里介绍一种：设计一种线性输入方式：? 按给出先序周游的结点序列，如：A B D C E G F H I? 加入空二叉树信息（支持二叉树构造），如用A B D C E G F H I 相当于做出扩充二叉树，所有外部结点用标记ABDCEFIHG名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

31、- - - - - - 第 8 页，共 19 页 - - - - - - - - - 49/* 递归地创建二叉树*/BinTree createBTree() PBNode pnd; charch;scanf( %c, &ch);if (ch = ) return NULL;pnd = (PBNode )malloc(sizeof(BNode);if ( pnd = NULL ) printf(NoSpace!); return NULL; pnd-info =ch;pnd-llink= createBTree();/* 构造左子树*/pnd-rlink= createBTree();/* 构

32、造右子树*/return pnd;本函数创建以字符为数据的二叉树。如果用其他数据类型，程序需修改。完整二叉树的字符序列使函数结束50另一方法是用二叉树构造函数：BinTree consBinTree(DataTypea, BinTree l, BinTreer) PBNode pbnode = (PBNode)malloc(sizeof(BNode);if( pbnode = NULL ) printf(Out of space!n); return NULL;pbnode-info = a;pbnode-llink = l; pbnode-rlink = r;return pbnode;构造

33、二叉树的例（设DataType 是 int ，可根据需要定义）：BinTree ta = consBinTree(3, NULL, consBinTree(5, NULL, NULL);BinTree tb = consBinTree(4, ta, consBinTree(8, NULL, NULL);用这一函数可以逐步构造出任意的二叉树515.4 二叉树的应用-+abcd表达式 (a b) / (c + d)的二叉树表示5.4.1 表达式树二元运算符直接表示，一元运算符只有一个子树，一元和二元函数用与运算符同样的方式多元函数特殊方式（例如用一个右子树序列）计算表达式值（给定一组变量值），可通

34、过后序周游完成数学软件都采用这类表示方式52从后缀表达式构造表达式树例： a 2 c b * 2 / + d - *方法：用一个栈，其中存放构造的部分树反复读入运算对象和运算符：? 遇运算对象 x：以 x为数据构造一个结点的二叉树，入栈? 遇运算符 o：弹出两个子树，设分别为r 和l，构造二叉树consBinTree(o, l, r) 并将其入栈。如果读完整个表达式时栈里只有一个元素，那就是构造出的表达式树53从中缀表达式构造表达式树运算对象栈（保存构造好二叉树）和运算符栈ost。逐个读入单词：? 遇运算对象 x，构造以 x为数据的单结点二叉树压入dst? 遇运算符o，与 ost 栈顶 o 比

35、较。 o 优先级不低于o 时弹出 o，从 dst 弹出两个二叉树，构造新二叉树并压入dst。反复至栈顶运算符优先级低于o 时将运算符o 压入 ost? 遇左括号，直接进栈ost? 遇右括号，逐个弹出运算符，从dst 弹出两个二叉树，构造新二叉树并压入dst，直至把对应左括号弹出? 遇表达式结束，逐个弹出运算符并构造，直至处理完全部运算符。若ost 只剩一个元素则成功，否则表达式有错545.4.2 优先队列和堆优先队列一种常用抽象数据类型，它遵循“ 最小元素先出” 的原则基本操作（代表优先队列的特征）：?向优先队列里插入一个元素(add)?在优先队列中找出最小元素（min ）?删除优先队列中最小

36、元素（removeMin ）优先级别代表了数据的某种性质，如用于描述一个大项目中各种工作任务的急迫程度，顾客信任度决定优先贷款名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 19 页 - - - - - - - - - 55创建空优先队列：PriorityQueue createEmptyPriQueue( void)判断 S是否为空（返回1/0值）：int isEmpty(PriorityQueue S)向S中加入元素 e：void add(PriorityQueue

37、S,DataType e)求出 S中的最小元素：DataType min(PriorityQueue S)删除 S中的最小元素：void removeMin(PriorityQueue S) 简单实现可用线性表或元素按优先序排列的表。但插入，取最小，或删除操作中必然有O(n) 操作56堆和优先队列二叉树结构支持优先队列的高效实现，这里需要堆的概念一棵完全二叉树称为堆，如果其结点的值满足堆序 ：任何父结点值小于等于其两个子结点值（若子结点存在）：kik2i+1kik2i+2 ( i = 0, 1, , (n-1)/2，下标从0 开始)上面定义的是“ 小顶堆 ” 。也可定义 “ 大顶堆 ” ：ki

38、k2i+1kik2i+2下面考虑 “ 小顶堆 ” ，其最小元素在堆顶，O(1)时间可取得完全二叉树可自然存放在数组里，因此堆的实现很简单57几个事实：1.若数组 k0,k1, ,kn-1 是小顶堆，则堆顶元素必为值最小的元素2.去掉堆顶，其余元素形成两个堆3.去掉最后元素，剩下仍然是堆aBC用堆实现优先队列，需要解决：1.怎样加入一个元素，使得到的结果仍然是一个堆2.删除最小元素后，如何将剩下的元素恢复为堆下面说明，这两个操作均可在O(log n) 时间内完成其他操作都简单，取最小元素是O(1) 操作58向上筛选：堆 B后增加一个元素a，把它们做成一个堆：方法：不断用a 与其父结点数据比较，如

39、果a小就交换两个元素的位置。直至a的父结点的数据小于等于a时停止插入操作的实现：把新元素放在已有元素之后，执行一次向上筛选动作完全二叉树高度是O(log n) ，插入可在O(log n) 时间完成59向下筛选：两个堆B,C和元素 a，把它们做成一个堆：siftaBC方法：用 a与B、C的顶元比，最小者作为整个堆的顶。若a非最小，最小的必为B（或 C）的顶元素。下面考虑把a 放入去掉堆顶的 B（或 C）（是同样问题）。结束情况：1， 在某次比较中 a最小，以它为顶的这个局部是堆2，a 落到底，这时它本身就是堆两种情况下，堆的构造都完成了。删除操作的实现：删去堆顶，从堆最后取一个元素放在堆顶，执行

40、一次向下筛选。O(log n) 操作60/* 程序实现 */typedef struct PriorityQueueint MAXNUM; /*元素个数上限*/int n;/* 堆中的实际元素个数*/DataType *pq; /* 堆中元素的顺序表示*/ PriorityQueue, * PPriorityQueue;void add_heap(PPriorityQueue papq,DataType x) int i = paqu-n; DataType *elems = papq-pq;if (papq-n = papq-MAXNUM) printf(Full!n);return;for

41、 ( ; i 0 & elems(i -1) / 2 x; i = (i -1) / 2 )elemsi = elems(i -1) / 2; /* 找插入的位置 */elemsi = x; /* 存入 x*/papq-n+; /* 计数增加*/名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 19 页 - - - - - - - - - 61void removeMin_heap(PPriorityQueue papq) int s, i, child; DataTyp

42、e temp, *elems= papq-pq;if (isEmpty_heap(papq) printf(Empty!n); return; s = -papq-n; /* 改元素计数（删除）*/temp = elemss; /* 取原最后元素到temp */* 从根结点出发，找temp 的正确插入位置*/for (i =0, child = 1; child s; ) /*找存元素位置 */if (child elemschild + 1) child+; /* 选择 i 的较小子结点*/if (temp elemschild) /* 需要继续向下考虑*/elemsi = elemschi

43、ld; i = child; child = 2 * i + 1; else break; /* 已找到适当位置*/elemsi = temp; /* 把最后元素填入*/62利用堆的概念和操作，得到了优先队列的一种高效实现? 实现基础是连续表（或者数组），无需保存其他附加信息? 插入和删除元素的操作都具有O(log n) 复杂性，取最小元素操作具有O(1) 复杂性但是：? 这种优先队列保存的元素个数受到数组大小的限制? 插入元素时存储区溢出的问题可采用动态顺序表技术，但这一次插入就需要O(n) 的时间优先队列在被作为辅助结构用在许多复杂算法的实现中其操作效率对许多高级算法的复杂性有重大影响。人

44、们还提出另外一些实现技术，例如斜堆（也是一种二叉树）635.4.3 哈夫曼 (Huffman) 树哈夫曼树可看作二叉树的一种应用，哈夫曼编码是一组信息的最短编码，在信息领域有重要理论和实际价值扩充二叉树的外部路径长度：（外部结点的路径长度之和）li为从根到外部结点i的路径长度， m为外部结点个数1miiEl=扩充二叉树的带权外部路径长度m为外部结点个数，wi是外部结点 i的权值， li为从根到 i的路径长度。权值是与结点关联的某种量1mi iiWPLwl=带权外部路径长度：64哈夫曼树定义：设有实数集w1, w2, w3, , wm，要求构造一棵扩充二叉树，包含m 个分别以wi（i = 1,

45、2, , m）为权的外部结点，其带权外部路径长度WPL 达到最小这样的扩充二叉树称为哈夫曼树 或最优二叉树11423WPL = 3423411WPL = 5321134WPL = 40例：以 2, 3, 4, 11 为外部结点权的几棵扩充二叉树：65哈夫曼算法给定权值w1,w2, ,wm。算法：1.构造包含 m 棵二叉树的集合F = T1,T2, ,Tm，其中二叉树 Ti 只含权为 wi 的根结点2.从 F 中选取两棵权最小的树作为左右子树，构造一棵新二叉树，其根结点的权值为两棵子树的根结点权值之和3.从 F 删除所选的两棵树，把新构造的二叉树加入F4.重复（ 2）和（ 3），直到 F 中只含

46、一棵树为止66哈夫曼算法过程的示例设有权集合2, 3, 7, 10, 4, 2, 523710425227104354227104354722510437479225104374791419225104374791419225104374791433名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 19 页 - - - - - - - - - 67哈夫曼 (huffman) 算法的实现存储结构：typedef struct HtNode /* 哈夫曼树结点的结构*/int

47、 ww;int parent, llink, rlink; HtNode;typedef struct HtTree /* 哈夫曼树定义*/HtNode *ht;int root;/* 哈夫曼树根在数组中的下标*/ HtTree, *PHtTree;用顺序表表示哈夫曼树的结点，用数组下标表示子结点和父结点关系。在构造哈夫曼树的过程中逐步建立这些链接68构造过程：?m 个权值（整数）存放在（参数）数组w 里?在可容纳2m-1 个 HtNode 结点的数组里构造哈夫曼树1. 初始化： 把给定权值存入前m 个结点，其父指针和子指针都赋值为1 ，表示无链接2. 反复做 m-1 遍： 在数组的有效结点范

48、围里找权值最小且无父结点的两个结点，为它们建立一个父结点（在数组右面部分的下一个空闲位置），并建立父子链接3. 哈夫曼树的树根是最后一个结点（下标2*m-2 ）不变关系：当前树集合的结点连续存在结点表左边部分。各树根结点的权是其两子结点的权之和，其父结点链接为-169/* 分配并初始化 Huffman 树数据结构*/PHtTree initHFT(int m, int *w) int i;PHtTree pht= (PHtTree)malloc(sizeof(HtTree);if (pht = NULL) printf(NoSpace!n); return NULL; pht-ht = (Ht

49、Node*) malloc(2*m-1)*sizeof(HtNode) );if (pht-ht = NULL) printf(NoSpace!n); return NULL; for (i = 0; i hti);p-llink= p-rlink= p-parent = -1;p-ww = (i m) ? wi : -1; /*其他结点的权置为-1*/return pht;70/* 构造具有m 个叶结点的哈夫曼树*/PHtTree huffman(intm, int *w) PHtTree pht= initHFT(m, w); inti, j, x1, x2, w1, w2;if (pht

50、= NULL) return NULL;for ( i = 0; i m -1; i+) /* 每次构造一个内部结点，共m-1次 */w1 = w2 = MAXINT; x1 = x2 = -1; /* x1和x2是结点下标*/for (j = 0; j htj); /* 考察一个结点*/ if (p-parent != -1) continue; /* p 不是子树根，向下找*/if (p-wwww; x1 = j; else if (p-wwww; x2 = j; pht-htx1.parent =pht-htx2.parent = m + i; /* 构造内部结点*/pht-htm+i.