数据结构第六章-树和二叉树课件.ppt

1、6.1 树的定义和基本术语树的定义和基本术语6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.6 哈夫曼树及其应用哈夫曼树及其应用6.1 树的定义和基本术语树的定义和基本术语ABCDEFGHIJMKLABCDEFGHIJMKL森林：森林：是m（m0）棵互不相交的树的集合BEFKLACGDHIJMABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如:BEFKLABCDEFGHK根结点6.2 二叉树二叉树二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L

2、左子树为空树左子树为空树左右子树左右子树均不为空均不为空树树查查 找找 插插 入入 删删 除除 性质性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1)用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。性质性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。性质性质 3：对任何

3、一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。证明：证明：设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+1。123456789 10 11 12 13 14 15abcdefghij 性质性质 4：具有 n 个结点的完全二叉树的深度深度为 log2n +1。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+

4、1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。6.2.3 二叉树的存储结构二叉树的存储结构1.二叉树的顺序存储表示二叉树的顺序存储表示 例如例如:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 1314013262 2、二叉树的链式存储表示、二叉树的链式存储表示ADEBCF rootlchild data rchild结点结构结点结构:lchild data rchild结点结构结点结构:ADEBCF root（2）三叉链表三叉链表parent lchild data rchild结点结构结点结构:parent l

5、child data rchild结点结构结点结构:6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 对对“二叉树二叉树”而言，可以而言，可以有三条搜索路径：有三条搜索路径：1先上后下先上后下的按层次遍历；2先左先左（子树）后右后右（子树）的遍历；3先右先右（子树）后左后左（子树）的遍历。二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（

6、2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 (先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)3 3、建立二叉树、建立二叉树1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想

7、:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想:从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1。首先

8、分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。不同的定义方法相应有不同的不同的定义方法相应有不同的存储结构的建立算法存储结构的建立算法例如:ABCD以空白字符“”表示A(B(,C(,),D(,)空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A ”表示以下列字符串表示A B C D A BCD上页算法执行过程举例如下：上页算法执行过程举例如下：ATBCD 由先缀表示式建树由先缀表示式建树例如：已知表达式的先缀表示式 -+a b c/d e 由原表达式建树由原表达式建树例如：已知表达式(a+b)c d/e d/eabcde-+/特点特点：操作数为叶子叶子

9、结点 运算符为分支分支结点scanf(&ch);if(In(ch,字母集)建叶子结点;else 建根结点;递归建左子树;递归建右子树;a+b(a+b)c d/e d/ea+bc ab+abc+abc+(a+b)cabcde-+/基本操作基本操作:scanf(&ch);if(In(ch,字母集)建叶子结点;暂存;else if (In(ch,运算符集)和前一个运算符比较优先数;若当前的优先数“高”，则暂存;否则建子树;while(!Gettop(S,c)&(precede(c,ch)CrtSubtree(t,c);Pop(S,c);if(ch!=#)Push(S,ch);break;建叶子结点的

10、算法为：建叶子结点的算法为：二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例如例如:aab bccddeeffggabcdefg先序序列中序序列 遍历二叉树的结果是，遍历二叉树的结果是，求得结点的一个线性序列。求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列:A B C D E F G H K中序中序序列:B D C A H G K F E后序后序序列:D C B H K G F E AA B C D E F G H K D C B E ABCDEFG0 A -11 B 02 C 03

11、D 04 E 2 5 F 26 G 5r=0n=6data parent一、双亲表示法一、双亲表示法:typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述:typedef struct PTNode nodes MAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;树结构树结构:ABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 5r=0n=6 data

12、firstchild 1 2 34 56二、孩子链表表示法二、孩子链表表示法:-1000224typedef struct CTNode int child;struct CTNode*next;*ChildPtr;孩子结点结构孩子结点结构:child nextC语言的类型描述语言的类型描述:typedef struct Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;双亲结点结构双亲结点结构 data firstchildtypedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree

13、;树结构树结构:ABCDEFG AB C E D F Groot AB C E D F G typedef struct CSNode Elem data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;C语言的类型描述语言的类型描述:结点结构结点结构:firstchild data nextsibling 6.4.2 森林和二叉树的对应关系森林和二叉树的对应关系设设森林森林 F=(T1,T2,Tn);T1=(root，t11,t12,t1m);二叉树二叉树 B=(LBT,Node(root),RBT);由森林转换成二叉树由森林转换成

14、二叉树的转换规则为:若 F=，则 B=；否则，由 ROOT(T1)对应得到 Node(root)；由(t11,t12,t1m)对应得到 LBT；由(T2,T3,Tn)对应得到 RBT。由二叉树转换为森林由二叉树转换为森林的转换规则为：若 B=，则 F=；否则，由 Node(root)对应得到 ROOT(T1)；由LBT 对应得到(t11,t12,，t1m)；由RBT 对应得到(T2,T3,Tn)。由此，树的各种操作均可对应二叉树的操作来完成。应当注意的是，应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。左是孩子，右是兄弟。A B C DE F G H I J K

15、 先根遍历时顶点先根遍历时顶点的访问次序：的访问次序：A B E F C D G H I J K 后根遍历时顶点后根遍历时顶点的访问次序：的访问次序：E F B C I J K H G D A 层次遍历时顶点层次遍历时顶点的访问次序：的访问次序：A B C D E F G H I J K B C DE F G H I J K1森林中第一棵树的根结点；2森林中第一棵树的子树森林；3森林中其它树构成的森林。森林由三部分构成：1.先序遍历先序遍历森林的遍历森林的遍历 若森林不空，则访问访问森林中第一棵树的根结点；先序遍历先序遍历森林中第一棵树的子树森林；先序遍历先序遍历森林中(除第一棵树之外)其 余

16、树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行先根遍历先根遍历。中序遍历中序遍历 若森林不空，则中序遍历中序遍历森林中第一棵树的子树森林；访问访问森林中第一棵树的根结点；中序遍历中序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行后根遍历后根遍历。最优树的定义最优树的定义 如何构造最优树如何构造最优树 前缀编码前缀编码 一、最优树的定义一、最优树的定义树的路径长度树的路径长度定义为：树中每个结点的路径长度之和。结点的路径长度结点的路径长度定义为：从根结点到该结点的路径上 分支的数目。树的带权路径长度树的带权路径长度定义为：

17、树中所有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点)。在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径带权路径长度取最小值长度取最小值的树，称为“最优树最优树”。例如：例如：27 9 75492WPL(T)=72+52+23+43+92 =60WPL(T)=74+94+53+42+21 =89 54 根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；二、如何构造最优树二、如何构造最优树(1)(赫夫曼算法)以二叉树为

18、例：在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和；(2)从F中删去这两棵树，同时加入 刚生成的新树；重复(2)和(3)两步，直至 F 中只 含一棵树为止。(3)(4)9例如:已知权值 W=5,6,2,9,7 5627527697671395276713952795271667132900001111000110110111 指的是，任何一个字符的编码都任何一个字符的编码都不是同一字符集中另一个字符的编码不是同一字符集中另一个字符的编码的前缀的前缀。三、前缀编码三、前缀编码 利用赫夫曼树可以构造一种不等长利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的的二进制编码，并且构造所得的赫夫赫夫曼编码曼编码是一种是一种最优前缀编码最优前缀编码，即使所，即使所传传电文的总长度最短电文的总长度最短。（a）（b）（c）（d）abdecfhg。42531678CABCABD（a）（b）