2022年数据结构课件可用

《2022年数据结构课件可用》由会员分享，可在线阅读，更多相关《2022年数据结构课件可用（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.

51、ww= w1 + w2;pht-htm+i.llink= x1;pht-htm+i.rlink= x2; pht-root = 2*m -2;returnpht;本算法具有平方复杂性。能加快其速度吗？用优先队列可加快哈夫曼树的构造速度，有兴趣的同学可以自己改进算法71设有如下基本数据集合：D=d1, d2, , dnW=w1, w2 , , wn其中： D为需要编码的字符集，W为D中各字符在实际信息传递（或者存储）中出现的频率要求：（ 1）编码的平均总长度最短；（2）如果 didj ，那么 di编码不是dj 编码的前缀。哈夫曼编码第二个条件使解码时容易判断是否已经得到一个字符的编码哈夫曼提出了

52、一种解决这一问题的方法，即哈夫曼编码72通过构造哈夫曼树，实现哈夫曼编码：以字符 d1,d2, , dn 为外部结点标注，把w1,w2, .,wn分别作为这 n 个外部结点的权，构造一棵哈夫曼树。在得到的哈夫曼树中，将所有从一个结点引向其左子女的边标二进制数字0；引向其右子女的边上标1。以从根结点到一个叶结点的路径上的二进制数字序列，作为这个叶结点的字符的编码。这就是哈夫曼编码可以证明：对于任意的集合对D 和 W，这样得到的哈夫曼编码是最优（最短）编码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

53、- - - 第 12 页，共 19 页 - - - - - - - - - 73w = 2 ，3，5，7，11，13，17，19，23，29，31，37，4174补充：补充：线索二叉树把周游二叉树得到的信息保存在树结构里供后面操作使用（1）增加两个指针（2）利用结构中的空链域，并设立标志。线索：指向结点前驱或后继的指针。线索二叉树 ：加了线索的二叉树。可以结点的空指针域表示相关线索，需要加标记区分正常子结点指针和线索指针线索化 ：对二叉树以某种序周游将其修改为线索二叉树按对称序线索化二叉树：按对称序周游二叉树，周游到一个结点时就为它增加线索信息。按对称序周游对称序穿线树，可以利用线索进行周游。

54、75tAB C EF I H G D 线索化后的二叉树原树的空闲指针域，现在都用来保存线索信息。需要区分两种指针：树结构指针和线索指针76typedef structThrTreeNodeThrTreeNode, * PThrTreeNode;/* 线索二叉树结点类型和指向它的指针类型*/struct ThrTreeNode/* 线索二叉树中结点的定义*/DataType info;PThrTreeNode llink, rlink;int ltag, rtag; /* 0:正常的二叉树指针，1:线索指针*/;typedef ThrTreeNode* ThrTree;/* 线索二叉树类型的定义

55、*/typedef ThrTree* PThrTree; /* 线索二叉树类型的指针类型*/77按对称序线索化的算法：? 操作前所有指针都是正常指针，tag都为 0? 周游中用线索指针代替空指针? 线索化的过程首先是一个非递归的对称序周游过程? 其中在遇到空指针时修改它，并修改相应的tag线索树的最大优点是可以较方便地找到周游序列的前一个和下一个结点由于这种情况，再做这种周游时就不需要使用栈了（第二版上有相应算法）78/* 按对称序线索化二叉树*/void thread(ThrTree t) PSeqStack st = createEmptyStack();/* 栈元素是 ThrTree*/

56、ThrTree p = t ，pr = NULL; while ( p != NULL | !isEmptyStack_seq(st) ) while (p!=NULL) push_seq(st,p);p= p-llink; p = top_seq(st); pop_seq(st);if (pr!=NULL) if (pr-rlink=NULL) pr-rlink= p;pr-rtag= 1; /*修改前驱结点的右指针*/if (p-llink=NULL) p-llink= pr; p-ltag= 1;/*修改该结点的左指针*/pr = p; p = p-rlink; /* 进入右子树*/名师

57、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 19 页 - - - - - - - - - 795.5 树的运算和树的实现5.5.1 树的基本运算抽象运算（操作）? 创建树（空树，或者包含若干子树的树）Tree createTree(Node p, Tree t1, Tree t2, , Tree ti) i = 1, 2, 3, ? 判断某棵树是否为空int isEmpty( Tree t )? 求树中的根结点，空树时返回特殊值Node root ( Tree t )8

58、0? 求指定结点的父结点，结点是树根时返回特殊值Node parent ( Node p )? 求树中某个指定结点的最左子结点，指定结点为树叶时返回特殊值Tree leftChild( Tree t )? 求树中某个指定结点的右兄弟结点，当指定结点没有右兄弟时返回特殊值Tree rightSibling( Tree t, Tree child )? 周游：按某种方式访问树中所有结点且每结点只访问一次void trivesal (Tree t )void trivesal (Tree t, Operation op )811. 周游：按某种系统的方式访问树中所有结点，而且每个结点恰好访问一次的过

59、程。2. 周游方法：按深度周游和按宽度周游。5.5.2 树和树林的周游注意： 按深度优先和宽度优先周游，访问结点的顺序就是深度优先搜索和宽度优先搜索中访问结点的顺序。在一般的搜索问题里，搜索过程经历的结点和结点间联系形成了一棵 “ 树” ，称为 “ 搜索树 ”由于非空树总有一个根结点，下面算法中用于表示树的t 也用于表示其根结点82先根序1）访问根结点2）从左到右按先根次序周游根结点的每棵子树1, 2, 3, 5, 8, 9, 6, 10, 4, 7中根序 （称为 “ 中根” 不太有理）1）按中根次序周游根结点的最左子树2）访问根结点3）从左到右按中根次序周游根结点的其它各子树2, 1, 8,

60、 5, 9, 3, 10 , 6, 7, 4(I) 按深度周游83后根序1）从左到右按后根次序周游根结点的每棵子树2）访问根结点2, 8, 9, 5, 10, 6, 3, 7, 4, 1（II）按宽度（层次）周游先访问层数为 0的结点，然后从左到右逐个访问层数为1的结点，依此类推，直到访问完树中全部结点。1, 2, 3, 4, 5, 6, 7, 8, 9, 1084先根序周游的递归算法void preOrder( Tree t ) /*先根序 */Tree c;visit( root( t ) ); /* 访问根结点*/* 考查剩余部分*/for ( c = leftChild( t ); !

61、isEmpty( c ) ;c = rightSibling( t, c ) ) preOrder( c );? 访问各子树的方式与访问整个树一样? 对各子树的访问按规定顺序进行，用循环描述? 各种深度优先周游都可以定义非递归算法，其中需要用一个栈保存信息。这里讨论先根序的非递归算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 19 页 - - - - - - - - - 85先根序周游的非递归算法void npreOrder( Tree t ) PSeqStack

62、s =createEmptyStack( );Tree c = t;while ( !isEmpty( c ) ) visit ( root( c ) );push ( s, c );c = leftChild ( t, c );while ( isEmpty( c ) & !isEmptyStack(s) ) c = rightSibling( t, top (s) ); /* 回溯并考虑其他分支*/pop (s);86void inOrder( Tree t ) /*中根序周游 */Tree c = leftChild( t );if ( !isEmpty( c ) ) inOrder(

63、c ); /* 按中序周游最左子树*/visit( root( t ) ); /* 访问根结点*/if ( !isEmpty( c ) )while ( !isEmpty(c =rightSibling( t, c ) ) /* 剩余部分*/inOrder ( c );void postOrder( Tree t ) /*后根序周游 */Tree c = leftChild( t );while ( !isEmpty( c ) ) /* 首先按后序周游树的各子树*/postOrder ( c );c = rightSibling( t, c );visit( root( t ) ); /* 访

64、问根结点*/87void levelOrder( Tree t) PSeqQueue q = createEmptyQueue( );Tree c = t;if (isEmpty(c) ) return;enQueue_seq(q, c); /* 根结点入队*/while ( !isEmptyQueue(q) ) c = frontQueue(q);deQueue (q);visit( root( c ) ); /* 访问队列里最先入队的结点*/c = leftChild( t, c );while ( !isEmpty(c) ) /* 被访问结点的各子结点入队*/enQueue (q, c)

65、;c = rightSibling( t, c );881. 先根（ A, B, C, K, D, E, H, F, J, G )2. 后根 ( B, K, C, A, H, E, J, F, G, D )树林的周游是其中的树的周游的总和895.5.3 树的存储表示树的存储表示?父指针表示法?子表表示法?长子 - 兄弟表示法首先，树可以借助于二叉树结构实现。下面先讨论这个问题90树、树林二叉树树、树林与二叉树的转换树、树林转换为二叉树。步骤：1.在所有相邻的兄弟结点之间连一条线；2.对每个非叶结点，只保留它到其最左子女的连线，删去它到其它子女的连线树（树林）与二叉树之间都存在一一对应关系，因此

66、二叉树的所有实现技术也都是树和树林的实现技术名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 19 页 - - - - - - - - - 91ABCKDEFGHJ树林转换为二叉树92二叉树转换为树、树林：1.若某结点是其父母的左子女，则把该结点的右子女，右子女的右子女，都与该结点的父母连线；2.去掉原二叉树中所有父母到右子女的连线。ABDCEKHFJG由于二叉树比较规范。树的最常见表示方式就是转换到二叉树，而后用二叉树的表示技术93typedef struct ParT

67、reeNode /* 树结点结构*/DataType info;/* 结点中的数据*/intparent; /* 结点的父结点位置*/ ParTreeNode;typedef struct ParTree int n; /* 记录树中结点个数*/ParTreeNode nodelistMAXNUM; /* 存储树中各结点*/ ParTree, *PParTree;父指针表示法用连续空间存储树结点，每个结点设一个指示器，指示其双亲结点（父结点）位置。可用结点下标? 就是用顺序表保存树中结点及树的结构信息? 树的结构信息通过每个结点的parent 成分表示94优点：a) 容易找到父结点及所有祖先（

68、沿parent 指针）b) 能找到结点的子女和兄弟（通过穷尽检查）缺点：a) 没表示兄弟结点之间的左右顺序b) 找结点的子女和兄弟比较麻烦改进方法：按某种周游序在数组中保存结点。常用按先根序存放结点，如图：? 子结点在根结点之后? 左边的兄弟结点在前，右边的兄弟结点在后95int rightSibling_partree(PParTreet, int p) int i; /* 找结点 p的右兄弟结点（下标对应着结点）*/if (p = 0 & p n) for (i = p+1; i n; i+)if (t-nodelisti.parent = t-nodelistp.parent)retur

69、n i;return -1;/* 依先根序列存储时，求最左子结点的运算简化为*/int leftChild_partree(PParTreet, int p) if (t-nodelistp+1.parent = p)return p+1; /* 最左子结点总排在下一位置*/elsereturn -1;96子表表示法? 结点表中每个元素（结点）关联一个子结点（链）表，其中存放该结点的所有子结点? 结点表顺序存放，子表用链接表示struct EdgeNode /* 子表中节点的结构*/int nodeposition;struct EdgeNode *link;typedef struct Ch

70、iTreeNode /* 结点表中节点结构*/DataType info;struct EdgeNode *children; ChiTreeNode;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 19 页 - - - - - - - - - 97子表表示的树结构定义：typedef struct ChiTree /* 树结构 */struct ChiTreeNode nodelistMAXNUM;int root;/* 根结点的位置*/int n; /* 结点的个数

71、*/ ChiTree, *PChiTree;98/* 求 p 的右兄弟结点*/int rightSibling_chitree(PChiTreet, int p) int i; struct EdgeNode *v;for (i = 0; i n; i+) v = t-nodelisti.children;while (v != NULL)if (v-nodeposition= p)if (v-link = NULL)return -1; /* 已没有下一个兄弟结点*/elsereturn(v-link-nodeposition);elsev = v-link;return -1;如果知道结点

72、所在的链表（子表）结点，求右兄弟就非常简单了99/* 求父结点*/int parent_chitree(PChiTreet, int p) int i;struct EdgeNode *v;for (i = 0; i n; i+) /* 逐个检查是否父结点*/v = t-nodelisti.children;while ( v != NULL )if ( v-nodeposition= p )return i; /* 结点 i 的子结点表中有p，返回 i */elsev = v-link;return -1; /* 无父结点，返回值为-1 */求最左子结点、顺序访问一个结点的各子结点都很简单1

73、00除信息域外，每个结点包含指向其最左子女和右兄弟的指针长子- 兄弟表示法typedef struct CSNode*PCSNode; /* 结点指针 */typedef struct CSNode /* 结点结构 */DataType info;/* 结点中的元素*/PCSNode lchild;/* 结点的最左子女的指针*/PCSNode rsibling;/* 结点的右兄弟的指针*/ CSNode; /* 结点类型 */typedef struct CSNode *CSTree;/* 树类型定义*/101ta b dc e h i j f g 树的长子兄弟表法找长子或者右兄弟都比较简单找

74、父结点很困难（可增加父指针）就是树的二叉树表示！1025.5.4 树林的存储表示是树的各种表示法的变形，同样可以采用：?父指针表示法?子表表示法?长子 - 兄弟表示法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 19 页 - - - - - - - - - 103树林的父结点表示方法? 需要设法表示各树的树根结点104树林的子表表示法需要各树根结点的信息（可增加其他结构来表示）105tA B D C E H J K F G 树林的长子兄弟表示法沿着第一个树根的右兄弟指

75、针，可以找到所有树根106在实际的算法和程序里，树的使用远不如二叉树那么广泛主要原因是树的结构不规整，一棵树中各个结点的子结点个数可能不同，而且没有限制。在计算机里表示和处理都比较麻烦如果实际中真正需要树结构，通常也是利用树与二叉树的关系（下面介绍），把树转换为二叉树后存储和处理107小结z树、树林、二叉树的基本概念和术语；z二叉链表存储结构z树、二叉树的周游z哈夫曼树的构造方法及应用108名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 19 页 - - - - - -

76、 - - - 109非递归周游算法 ：前序和中序周游较简单，易实现（自己考虑）。书上给了一个后序周游算法，其中用一个栈，栈里记录指针和一个标志/* 算法用的堆栈元素*/typedef structPBNode ptr; /* 进栈结点*/int tag; /* 标记 */ Elem;/* 栈顺序表示 */#define MAXNUM 20 /* 栈中最大元素个数*/typedef struct SeqStack /* 顺序栈类型定义*/int t; /* 指示栈顶位置*/Elem sMAXNUM; SeqStack, *PSeqStack;/* 顺序栈类型的指针类型*/ 110void nPo

77、stOrder(PBTree t ) PSeqStack st; Elem stnode; PBNode p; /* 当前处理的结点*/char continueflag; /* 继续退栈标志，从右子树返回访问完根后继续退栈*/if (*t = NULL) return;st = createEmptyStack_seq( ); p = t; /* 从根结点开始*/do /* 每次大循环进入由p所指子树周游*/while (p != NULL) /* 反复把所遇结点进栈并进入其左子树*/stnode.ptr = p; stnode.tag = 1;push_seq(st, stnode); p

78、 = leftChild_btree(p);continueflag= t; while ( continueflag= t & !isEmptyStack_seq(st) ) stnode = top_seq(st); pop_seq(st);p = stnode.ptr;if (stnode.tag = 1) /* 从左子树回来，改标志重进栈并进入右子树*/stnode.tag = 2; push_seq(st,stnode);continueflag= f; p = rightChild_btree(p);else visit(p); while ( !isEmptyStack_seq(

79、st) );/* 栈为空时，全部周游完*/* 很容易用 break 语句，消除这个flag */111不变式：栈里保存经过但未访问的树（子树）根结点。结点的右子树尚未访问时tag=1；已经或正在访问时tag=21212实际上并不需要tag 标记：?因为栈里每一个结点的父结点（如果存在）总是它的下面一个结点?正考虑的结点的父结点（如果存在）就是栈顶结点?根据本结点是其父结点的左子结点或者右子结点，就可以决定下一步怎么做?根据这个想法，完全可以去掉标志，简化算法?下面算法另外做了一些调整，重要的是 “ 下行循环 ”112/* 简化算法。栈里只存结点指针*/void nPostOrder2(PBin

80、Tree t ) PSeqStack st = createEmptyStack_seq( );PBNode p = t;while ( p != NULL | !isEmptyStack_seq(st) ) while (p != NULL) /* 循环到栈顶结点的左右子树都空*/push_seq( st, p );p = leftChild_btree(p) ? leftChild_btree(p) : rightChild_btree(p);p = top_seq(st); pop_seq(st); visit(p); /* 栈顶是应访问结点*/if ( !isEmptyStack_seq(st) &leftChild_btree(top_seq(st) = p )/* 栈不空且是从左子树退回*p = rightChild_btree(top_seq(st) ; /else p = NULL; /* 从右子树返回则强迫退栈*/名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 19 页 - - - - - - - - -