清华名师数据结构考研辅导课件附带考试大纲第六章树和二叉树

1、树与二叉树2022/8/3考研辅导三、树与二叉树树与二叉树 （一）树的概念（二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 2022/8/3考研辅导三、树与二叉树树与二叉树（三）树、森林 1.树的存储结构 2.森林与二叉树的转换 3.树和森林的遍历（四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码2022/8/3考研辅导平衡二叉树平衡二叉树(又称AVL树)，是二叉排序树的另一种形式。它或者是一棵空树；或者是具有如下性质的二叉树： 它的左子树和右子树都是平衡

2、二叉树，且左子树和右子树的深度之差的绝对值不超过1。结点的平衡因子 该结点的左子树高度减去它的右子树高度：hL-hR 则平衡二叉树中的每个结点满足： hL-hR12022/8/3考研辅导平衡二叉树3023378263242252840平衡二叉树的存储结构typedef struct BSTNode ElemType date; int bf; /结点的平衡因子 struct BSTNode * lchild, * rchild; BSTNode, *BSTree;主要操作：插入2022/8/3考研辅导平衡二叉树的插入 一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为

3、A（即A是离新插入结点最近，且平衡因子绝对值超过1的祖先结点）。 失去平衡后进行调整的规律可归纳为下列四种情况： LL型、LR型、RR型、RL型。2022/8/3考研辅导LBLABARBR插入结点BA LL型：即新插入的结点在 A 的左子树的左子树上。此时应选择 A 的左子树的根结点 B，然后进行调整。LARBRBL2022/8/3考研辅导平衡二叉树void R_Rotate ( BSTree &p) /对以*p为根的二叉排序树作右旋处理，处理之后p指向新的根结点/即旋转处理之前的左子树的根结点 算法9.9 lc=p-lchild; /lc指向p的左子树的根,本例指向B p-lchild=lc

4、-rchild; /改变A的左子树-变为B的右子树 lc-rchild=p; /改变B的右子树-变为A p=lc; /p指向新的根结点LLBLABARBRlcp2022/8/3考研辅导RBLABALBR插入结点BA RR型：即新插入的结点在 A 的右子树的右子树上。此时应选择 A的右子树的根结点 B，然后进行调整。RBLALBR2022/8/3考研辅导平衡二叉树void L_Rotate ( BSTree &p) /对以*p为根的二叉排序树作左旋处理，处理之后p指向新的根结点/即旋转处理之前的右子树的根结点 算法9.10 rc=p-rchild; /rc指向p的右子树的根 p-rchild=r

5、c-lchild; /改变A的右子树-变为B的左子树 rc-lchild=p; /改变B的左子树-变为A p=rc;RBLABALRBRprc2022/8/3考研辅导LBLABAR插入结点 LR型：即新插入的结点在A的左子树的右子树上。此时应选择 A 的左子树的根结点B ，和 B 的右子树的根结点 C ，然后进行调整。RCCLCRCAARCRCARBCLCRABLBBLCL简便方法：将C提为根，B、A分别挂两边原B左子树、原A右子树不变原C的左子树挂在B的右边(仍在C左) 原C的右子树挂在A的左边(仍在C右)2022/8/3考研辅导LBRABAL插入结点 RL型：即新插入的结点在 A 的右子树

6、的左子树上。此时应选择 A的右子树的根结点 B ，和 B 的左子树的根结点 C ，然后进行调整。RCCLCRCBBRCRCLALA简便方法：将C提为根，A、B分别挂两边原A左子树、原B右子树不变原C的左子树挂在A的右边(仍在C左) 原C的右子树挂在B的左边(仍在C右)ACB2022/8/3考研辅导小结：插入结点失衡时，LL型(或RR型)：拿失衡结点的孩子开刀，以该孩子结点为轴(沿其双亲方向)进行右旋(或左旋)。LR型(或RL型)：拿失衡结点的孙子开刀，两次以该孙子结点为轴(沿其双亲方向) ，先左旋，再右旋(先右旋，再左旋)。最后孙子结点变为根。return2022/8/3考研辅导树的存储结构双

7、亲表示法#define MAX_TREE_SIZE 100 typedef struct PTNode /结点结构 Elem data; int parent; /双亲位置域 PTNode; *BiTree;typedef struct /树结构 PTNode nodes MAX_TREE_SIZE; int r, n; /根结点的位置和结点个数 PTree;A-1B0C0D2E3ABCDE2022/8/3考研辅导树的存储结构孩子链表表示法typedef struct CTNode /孩子结点结构 int child; struct CTNode *next; /指向下一孩子结点的指针 *Ch

8、ildPtr;typedef struct /双亲结点结构 Elem data; ChildPtr firstchild; / 孩子链的头指针 CTBox;typedef struct /树结构 CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;ABCDEABCDE12342022/8/3考研辅导树的存储结构二叉链表(孩子-兄弟)表示法typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;firstchild：

9、指向左边第一个子结点nextsibling：指向右边第一个兄弟结点见教材P137图6.16return2022/8/3考研辅导森林与二叉树的转换设森林为： F= ( T1, T2, , Tn ); T1= (root，T11, T12, , T1m);二叉树为： B=(root, LB, RB);2022/8/3考研辅导森林与二叉树的转换森林转换成二叉树的转换规则若F=，则B=；若F非空，T1-root-B-root T11,T12,T1m-B-LB； T2,T3,Tn-B-RB。二叉树转换成森林的转换规则若B=，则F=；若B非空，B-root-T1-root B-LB-T11,T12,T1m

10、 B-RB-T2,T3,Tn2022/8/3考研辅导森林转换成二叉树12435678911123478911562022/8/3考研辅导二叉树转换成森林124356789124635798return2022/8/3考研辅导树和森林的遍历树的遍历:先根遍历:若树非空，则先访问根结点，然后依次先根遍历各棵子树。后根遍历:若树非空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历:若树非空，则自上而下自左至右访问树中每个结点。森林的遍历:先根遍历:若森林非空，则先访问森林中第一棵树的根结点；然后依次先根遍历该根结点的各子树；先根遍历森林中的其它树。中根遍历:若森林非空，则先中根遍历森林中第一棵

11、树的根的各子树；然后访问第一棵树的根结点；中根遍历森林中的其它树。return2022/8/3考研辅导等价类问题 在求解实际问题时，常会遇到等价类问题。如： 编写程序，判断输入的3个数能否构成三角形的三条边。在实际输入时，可能会输入多组测试数据：(1,2,3),(3,4,5),(6,2,7),(7,8,9),(3,5,6) 若按“任意两边和均大于第三边”划分等价类，则可分为两个等价类：满足条件的：(3,4,5),(6,2,7),(7,8,9)不满足条件的：(1,2,3),(6,2,7),(3,5,6) 2022/8/3考研辅导等价类问题 数学上，等价类是一个集合，该集合包含一个或多个元素，且此

12、集合中的所有元素都满足一个等价关系。 等价关系：如果集合S中的关系R是自反的、对称的和传递的，则称R为一个等价关系。 即：对于集合S中的任意元素x，y，z，下列性质成立： 对于任一元素x，xRx(即等于自身)，则R为自反的； 对于任意两个元素x，y，如果xRy，则yRx。则R为对称的； 对于任意三个元素x，y，z，如果xRy且yRz，则xRz。关系R就是传递的。 一般地，一个集合S中的所有元素可以通过等价关系划分为若干个互不相交的子集S1，S2，S3它们的并就是S。这些子集称为等价类。 利用等价关系把集合S划分成若干等价类的原则是：对于集合S中的两个元素x与y，当且仅当xRy，它们才属于同一等

13、价类。 2022/8/3考研辅导等价类问题 将集合中S的n个不同的元素按等价关系R划分成等价类：开始时：使S中每个元素自成一个单元素集合；然后：若xRy，且x和y属于不同的集合，则将x所属集合和y所属集合合并。 按此条件处理所有满足等价关系R的元素。最后得到的各不相交的子集即S的等价类。此过程中用到的运算：查询某个元素归属于哪个集合，合并集合并查集：一种集合，支持操作：构造单元素集合：将并查集S中的n个元素初始化成一个由n个子集(每个子集只包含一个元素)构成的集合。确定某元素x所属子集：搜索单元素x所在集合，并返回该集合的名字。合并两个集合：将两个互不相交的非空子集合并。其抽象数据类型的定义见

14、教材P140。2022/8/3考研辅导等价类问题 并查集的实现：用树型结构表示元素及其所属子集的关系。每个集合用一棵树表示，树中每个结点表示集合的一个元素。树型结构用双亲表示法：#define MAX_TREE_SIZE 100 typedef struct PTNode /结点结构 Elem data; int parent; /双亲位置域 PTNode; *BiTree;typedef struct /树结构 PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;typedef PTree MFSet;约定：根结点的成员兼作子集

15、的名称。1-121314354123452022/8/3考研辅导确定i所在子集-算法6.8 算法的时间复杂度为：O(d)，d为树的高度。求Si和Sj的并集-算法6.9 算法的时间复杂度为：O(1) (见教材P141)树的高度与树的形成有关：极端的例子是：在合并集合树时，每次都将元素多的子集树的根指向元素少的子集树的根，则最后得到的集合树的高度为n(S的总元素个数)。在这种情况下：先确定i所在子集，时间复杂度为O(n); 再合并n-1次，形成最终的集合树; 总时间复杂度为O(n2)123442312022/8/3考研辅导/合并两个互不相交的子集Si和Sj-算法6.9的改进算法6.10改进：将结点

16、数少的集合树并至结点数多的集合树下。修改存储结构：使根结点的parent域存储该集合树的总结点数的负值。按此方法得到的集合树的高度不超过：log2n+1 证明见教材P142。123456712345671-42131415-365751-72131415165752022/8/3考研辅导/确定i所在子集-算法6.8的改进算法6.11。改进：确定i所在集合树的根的同时将i至根的路径压缩，使该路径上的结点都成为根的孩子。使树的高度变小。123457612345672022/8/3考研辅导/确定i所在子集，并将i至根的路径压缩，使该路径上的结点都成为根的孩子。算法6.11 int fix_mfset

17、(MFSet &S,int i) if(iS.n) return -1; for(j=i;S.nodesj.parent0;j=S.nodesj.parent);/寻找i所在树的根j for(k=i;k!=j;k=t)/压缩i至j间的路径，将该路径上除根外的所有结点的根置为j t=S.nodesk.parent;S.nodesk.parent=j; return j; 123457612345672022/8/3考研辅导/合并两个互不相交的子集Si和Sj。算法6.10/S.nodesi和S.nodesj分别为Si和Sj的根结点。status mix_mfset(MFSet &S,int i,i

18、nt j) if(iS.n|jS.n) return ERROR; if(S.nodesi.parentS.nodesj.parent) /Sj的结点数多 S.nodesj.parent+=S.nodesi.parent; /更新Sj的结点数 S.nodesi.parent=j; /i的双亲置为j else S.nodesi.parent+=S.nodesj.parent; /更新Sj的结点数 S.nodesj.parent=i; /j的双亲置为i return OK; 12345671234567return2022/8/3考研辅导哈夫曼树一组概念：结点的路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路经上的分支数目称作路经长度。树的路径长度：从树根到每个结点的路径长度之和。结点的带权路径长度：从该结点到树根之间的路经长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作： WPL(T) = wklk 最优二叉树(哈夫曼树)：设有n个权值w1,w2,wn ，若构造一棵有 n 个叶子结点的二叉树，每个叶结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树(哈夫曼树)。2022/8/3考研辅导WPL(T)= 13+23+33