数据结构课件C版第六章.ppt

2019/2/23,mayan,第六章 树,树 二叉树 线索二叉树 树与森林 Huffman树,2019/2/23,mayan,树 -树的定义和术语,树：一棵树 T，简称为树，它是n (n0) 个结点的有限集合。当n = 0时，T 称为空树；否则，T 是非空树，记作 其中，r 是一个特定的称为根(root)的结点，它没有直接前驱；根以外的其他结点划分为 m (m 0) 个互不相交的有限集合T1, T2, , Tm，每个集合又是一棵树，并且称之为根的子树。,2019/2/23,mayan,树 -树的定义和术语,相关术语 子女：若结点的子树非空，结点子树的根即为该结点的子女。 双亲：若结点有子女，该结点是子女双亲。 兄弟：同一结点的子女互称为兄弟。 度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。 分支结点：度不为0的结点即为分支结点，亦称为非终端结点。,2019/2/23,mayan,树 -树的定义和术语,叶结点：度为0的结点即为叶结点，亦称为终端结点。 祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。 子孙：某结点的所有下属结点，都是该结点的子孙。 结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以此类推。 深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。,2019/2/23,mayan,树 -树的定义和术语,高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。 树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。 有序树：树中结点的各棵子树 T0, T1, 是有次序的，即为有序树。 无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。 森林：森林是m（m0）棵树的集合。,2019/2/23,mayan,树 -树的抽象数据类型,教材 p118-120,2019/2/23,mayan,二叉树 -二叉树的定义,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,2019/2/23,mayan,二叉树 -二叉树的性质,性质1 若二叉树结点的层次从 1 开始, 则在二叉树的第 i (i1)层最多有 2i-1 个结点。 证明用数学归纳法 性质2 深度为 k (k0) 的二叉树最少有 k 个结点，最多有 2k-1个结点。 证明：因为每一层最少要有1个结点，因此，最少结点数为 k。最多结点个数借助性质1用求等比级数前k项和的公式20 +21 +22 + +2k-1 = 2k-1,2019/2/23,mayan,二叉树 -二叉树的性质,性质3 对任何一棵二叉树，如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有 n0n21 证明：若设度为 1 的结点有 n1 个，总结点数为n，总边数为e，则根据二叉树的定义， n = n0+n1+n2 , e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1则 n2 = n0-1 n0 = n2+1,2019/2/23,mayan,二叉树 -二叉树的性质,定义1 满二叉树 (Full Binary Tree) ：深度为k的满二叉树是有2k-1个结点的二叉树。 定义2 完全二叉树 (Complete Binary Tree)：若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。,2019/2/23,mayan,二叉树 -二叉树的性质,性质4 具有 n (n0) 个结点的完全二叉树的深度为 log2(n+1)。 证明： 设完全二叉树的深度为k，则有2k-1-1 n 2k-1 即 2k-1 n+12k ，取对数 k-1 log2(n+1) k 有 k= log2(n+1),2019/2/23,mayan,二叉树 -二叉树的性质,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, , n，则有以下关系： 若i = 1, 则 i 无双亲； 若i 1, 则 i 的双亲为i2； 若2*i = n, 则 i 的左子女为 2*i； 若2*i+1 = n, 则 i 的右子女为2*i+1； 若 i 为奇数, 且i != 1, 则其左兄弟为i-1； 若 i 为偶数, 且i != n, 则其右兄弟为i+1； 结点i 所在的层次为log2i+1,2019/2/23,mayan,二叉树 -二叉树的抽象数据类型,教材 P121-123,2019/2/23,mayan,二叉树 -二叉树的数组存储表示,教材p126定义,2019/2/23,mayan,二叉树 -二叉树的链表存储表示,二叉链表和三叉链表的概念 二叉树结点定义：每个结点有3个域，data域存储结点数据，lchild和rchild分别存放指向左子女和右子女的指针。 二叉链表如下图所示：,2019/2/23,mayan,二叉树 -二叉树的链表存储表示,每个结点增加一个指向双亲的指针parent，使得查找双亲也很方便。,2019/2/23,mayan,二叉树 -二叉树的链表存储表示,整个二叉树的链表有一个表头指针，他指向二叉树的根结点。 在含有n个结点的二叉链表中有n+1个空链指针域，三叉链表则有n+2个空链指针域。 2n-(n-1)=n+1 n+1+1=n+2,2019/2/23,mayan,二叉树 -二叉树的链表存储表示,二叉树的链表表示,2019/2/23,mayan,二叉树 -二叉树的二叉链表存储表示,二叉树的二叉链表存储表示 typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild;/ 左、右孩子指针 BiTNode, *BiTree; 二叉树的三叉链表存储表示 typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,基于二叉树的二叉链表存储表示的基本操作的函数原形见教材p127,2019/2/23,mayan,二叉树 -二叉树的遍历,二叉树的遍历（Binary Tree Traversal）就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。“访问”的意思是对结点施行某些操作。 令L、R、D分别代表遍历一个结点的左子树、右子树和访问该结点的操作，则可能有DLR, LDR,LRD,DRL,RDL,RLD六种遍历二叉树的规则，若规定先左后右则有DLR（前序遍历）、 LDR（中序遍历）、 LRD（后序遍历）三种。,2019/2/23,mayan,二叉树 -二叉树的遍历,三种遍历算法： 先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。 中序遍历：中序遍历左子树；访问根结点；中序遍历右子树。 后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。,2019/2/23,mayan,二叉树 -二叉树的遍历,Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 算法6.1.采用二叉链表存储结构，Visit是对数据元 /素操作的应用函数，先序遍历二叉树T的递归算 / 法，对每个数据元素调用函数Visit。 / 最简单的Visit函数是： / Status PrintElement( ElemType e ) / 输出元素e的值 / printf( e ); / 实用时，加上格式串 / return OK; / / 调用实例：PreOrderTraverse(T, PrintElement);,2019/2/23,mayan,二叉树 -二叉树的遍历,if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild, Visit) if (PreOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return OK; / PreOrderTraverse,2019/2/23,mayan,二叉树 -二叉树的遍历,中序遍历二叉树T的非递归算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.2.采用二叉链表存储结构，Visit是对数据元 /素操作的应用函数。中序遍历二叉树T的非递归算 /法，对每个数据元素调用函数Visit。,2019/2/23,mayan,二叉树 -二叉树的遍历,InitStack(S); Push(S, T); / 根指针进栈 while (!StackEmpty(S) while (GetTop(S, p) / InOrderTraverse,2019/2/23,mayan,二叉树 -二叉树的遍历,中序遍历二叉树T的非递归算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.3.采用二叉链表存储结构，Visit是对数据 /元素操作的应用函数。中序遍历二叉树T的非递归 /算法，对每个数据元素调用函数Visit。,2019/2/23,mayan,二叉树 -二叉树的遍历,InitStack(S); p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; else Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse,2019/2/23,mayan,二叉树 -以递归方式建立二叉树,BiTree CreateBiTree(BiTree &T) / 算法6.4 / 按先序次序输入二叉树中结点的值（一个字 /符），#字符表示空树，构造二叉链表表示的二 /叉树T。,2019/2/23,mayan,二叉树 -以递归方式建立二叉树,char ch; scanf(“%c“, / CreateBiTree,2019/2/23,mayan,二叉树,例1：给定一棵二叉树的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK，画出这颗二叉树。,2019/2/23,mayan,二叉树,例2：给定一棵二叉树的中序序列DCBGEAHFIJK和后序序列DCEGBFHKJIA，画出这颗二叉树。,2019/2/23,mayan,二叉树,例3：给定一棵二叉树的先序和后序序列不能确定一棵二叉树。,2019/2/23,mayan,线索二叉树 -线索二叉树的概念,为什么提出线索二叉树？ 遍历的过程实质上是对一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这个线性序列中有且仅有一个直接前驱和直接后继。二叉树中只存储了左右孩子的信息，因此，前驱和后继的信息无法直接找到。就提出了线索二叉树的概念。 又因为n个结点的二叉链表中有n+1个空链域，从而得到线索二叉树的存储结构如下。,2019/2/23,mayan,线索二叉树 -线索二叉树的概念,规定：若结点有左子树，则lchild指示其左孩子，否则令lchild指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。为避免混淆，增加两个标志域：LTag为0（1）表示lchild指向左孩子（前驱），RTag为0（1）表示rchild指向右孩子（后继）。,2019/2/23,mayan,线索二叉树 -线索二叉树的概念,其中，指向结点前驱和后继的指针叫做线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫线索化。,2019/2/23,mayan,线索二叉树 -线索二叉树的概念,2019/2/23,mayan,线索二叉树 -二叉树的二叉线索存储表示,typedef enum PointerTag Link, Thread ; / Link=0:指针，Thread=1:线索 typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerTag LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,2019/2/23,mayan,线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱和后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。,线索二叉树 -通过中序遍历建立中序线索化二叉树,2019/2/23,mayan,线索二叉树 -通过中序遍历建立中序线索化二叉树,Status InOrderThreading(BiThrTree / InOrderThreading,2019/2/23,mayan,线索二叉树 -通过中序遍历建立中序线索化二叉树,void InThreading(BiThrTree p) / 算法6.7 if (p) InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持pre指向p的前驱 InThreading(p-rchild); / 右子树线索化 / InThreading,2019/2/23,mayan,线索二叉树 -中序遍历二叉线索链表表示的二叉树,Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType) / 算法6.5 p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; while (p-RTag=Thread / InOrderTraverse_Thr,2019/2/23,mayan,线索二叉树 -寻找当前结点在中序下的后继,寻找当前结点在中序下的后继,RTag,rchild,2019/2/23,mayan,线索二叉树 -寻找当前结点在中序下的后继,寻找当前结点在中序下的前驱,2019/2/23,mayan,树与森林 -树的存储表示,双亲表示法（父指针表示法） 以一组连续的存储单元来存放树中的结点，每个结点有两个域，一个是data域，用来存放数据元素，一个是parent域，用来存放指示其父结点位置的指针。 这种存储表示适合经常需要寻找父结点的应用。,2019/2/23,mayan,树与森林 -树的存储表示,树的双亲表存储表示 #define MAX_TREE_SIZE 100 typedef struct PTNode /结点结构 TElemType data; int parent; / 双亲位置域 PTNode; typedef struct /树结构 PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;,2019/2/23,mayan,树与森林 -树的存储表示,孩子表示法（子女链表表示法） 为树中每个结点设置一个子女链表，并将这些结点的数据和对应子女链表的头指针放在一个向量中，就构成了子女链表表示。 这种存储表示适合需要频繁寻找子女的应用。无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。,2019/2/23,mayan,树与森林 -树的存储表示,树的孩子链表存储表示 typedef struct CTNode /孩子结点结构 int child; struct CTNode *next; *ChildPtr; typedef struct /双亲结点结构 TElemType data; ChildPtr firstchild; / 孩子链的头指针 CTBox; typedef struct /树结构 CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;,2019/2/23,mayan,树与森林 -树的存储表示,孩子兄弟表示法（子女-兄弟链表表示法） 子女-兄弟链表表示法也称为树的二叉树表示。他的每个结点的度为2 ，是最节省存储空间的树的存储表示。每个结点由三个域组成： firstChild 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。 nextSibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。,2019/2/23,mayan,树与森林 -树的存储表示,孩子兄弟表示法（子女-兄弟链表表示法）,2019/2/23,mayan,树与森林 -树的存储表示,树的二叉链表存储表示 typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,2019/2/23,mayan,树与森林 -森林与二叉树的转换,将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。 森林与二叉树表示的转换可以借助树的二叉树表示来实现。,2019/2/23,mayan,树与森林 -森林与二叉树的转换,森林转化成二叉树的规则 若 F 为空，即 n = 0，则对应的二叉树 B 为空树。 若 F 不空，则 二叉树 B 的根是 F 第一棵树 T1 的根； 其左子树为B (T11, T12, , T1m)，其中，T11, T12, , T1m 是 T1 的根的子树； 其右子树为 B (T2, T3, , Tn)，其中，T2, T3, , Tn 是除 T1 外其它树构成的森林。,2019/2/23,mayan,树与森林 -森林与二叉树的转换,二叉树转换为森林的规则 如果 B 为空，则对应的森林 F 也为空。 如果 B 非空，则 F 中第一棵树 T1 的根为 B 的根； T1 的根的子树森林 T11, T12, , T1m 是由 B 的根的左子树 LB 转换而来； F 中除了 T1 之外其余的树组成的森林 T2, T3, , Tn 是由 B 的根的右子树 RB 转换而成的森林。,2019/2/23,mayan,树与森林 -森林与二叉树的转换,2019/2/23,mayan,树与森林 -树的遍历,深度优先遍历 先根次序遍历：先访问树的根结点，然后先根遍历根的每棵子树。树的先根遍历结果与其对应二叉树表示的前序遍历结果相同。树的先根遍历可以借助对应二叉树的前序遍历算法实现。 后根次序遍历：先依次后根遍历每棵子树，然后访问根结点。树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。树的后根遍历可以借助对应二叉树的中序遍历算法实现。,2019/2/23,mayan,树与森林 -森林的遍历,森林的遍历也分为深度优先遍历和广度优先遍历，深度优先遍历又可分为先根次序遍历和后根次序遍历。 深度优先遍历 给定森林 F，若 F = Ø，则遍历结束。否则 若F = T1 = r1, T11, , T1k , T2, ., Tm，则可以导出先根遍历、后根遍历两种方法。其中，r1是第一棵树的根结点，T11, , T1k是第一棵树的子树森林，T2, .,Tm是除去第一棵树之后剩余的树构成的森林。,2019/2/23,mayan,树与森林 -森林的遍历,森林的先根次序遍历 若森林F = Ø，返回；否则访问森林的根（也是第一棵树的根）r1；先根遍历森林第一棵树的根的子树森林T11, , T1k；先根遍历森林中除第一棵树外其他树组成的森林T2, .,Tm。 森林的后根次序遍历 若森林 F = Ø，返回；否则后根遍历森林 F 第一棵树的根结点的子树森林T11, , T1k；访问森林的根结点 r1；后根遍历森林中除第一棵树外其他树组成的森林T2, ., Tm。,2019/2/23,mayan,树与森林 -森林的遍历,森林的先根次序遍历和后根次序遍历分别对应为二叉树的前序遍历和中序遍历。 广度优先遍历 若森林 F 为空，返回； 否则依次遍历各棵树的根结点；依次遍历各棵树根结点的所有子女；依次遍历这些子女结点的子女结点；,2019/2/23,mayan,Huffman树 -相关概念,路径长度 (Path Length) 两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。 树的外部路径长度是各叶结点（外结点）到根结点的路径长度之和 EPL。 树的内部路径长度是各非叶结点（内结点）到根结点的路径长度之和 IPL。 树的路径长度 PL = EPL + IPL。,2019/2/23,mayan,Huffman树 -相关概念,n 个结点的二叉树的路径长度不小于下述数列前 n 项的和，即,2019/2/23,mayan,Huffman树 -相关概念,其路径长度最小者为 完全二叉树满足这个要求。 带权路径长度 (Weighted Path Length, WPL) 树的带权路径长度为树中所有叶子结点的带权路径长度之和。,2019/2/23,mayan,Huffman树 -相关概念,2019/2/23,mayan,Huffman树 -相关概念,Huffman树 假设有n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树为最优二叉树，即Huffman树。,2019/2/23,mayan,Huffman树 -Huffman树的构造算法,1.根据给定的n个权值w1,w2,wn构造n棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。 2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 3.在F中删除这两棵树，同时将新得到的二叉树加入F中。 4.重复（2）、（3）步，直到F只含一棵树为止，这棵树为Huffman树。,2019/2/23,mayan,Huffman树 -Huffman树的构造算法,2019/2/23,mayan,Huffman树 -Huffman树的构造算法,2019/2/23,mayan,Huffman树 -Huffman 编码,主要用途是实现数据压缩。设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T ，各个字符出现的频度（次数）是 W 2, 7, 4, 5 。 若给每个字符以等长编码（2位二进制足够） A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36。,2019/2/23,mayan,Huffman树 -Huffman 编码,能否减少总编码长度，使得发出同样报文，可以用最少的二进制代码？ 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 各字符出现概率为 2/18, 7/18, 4/18, 5/18 ,化整为 2, 7, 4, 5 。以它们为各叶结点上的权值, 建立Huffman树。左分支赋 0，右分支赋 1，得Huffman编码(变长编码)。 A : 0 T : 10 C : 110 S : 111,2019/2/23,mayan,Huffman树 -Huffman 编码,A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于Huffman树的带权路径长度WPL。 Huffman编码是一种前缀编码，即任一个二进制编码不是其他二进制编码的前缀。解码时不会混淆。因为需要编码的结点都是叶子结点，他不会成为别的结点的祖先结点，所以也不会成为前缀。,