数据结构7-8.ppt

1、数据结构数据结构第七章第七章 树和二叉树树和二叉树 这是一类这是一类非线性结构非线性结构。这类结构中至少存在一个数据。这类结构中至少存在一个数据元素，它具有两个或两个以上的直接后继或直接前驱。元素，它具有两个或两个以上的直接后继或直接前驱。 树型结构是一类十分重要的非线性结构，它的树型结构是一类十分重要的非线性结构，它的特点特点是是树中结点之间具有树中结点之间具有层次关系层次关系。常用到的两种结构是树和二。常用到的两种结构是树和二叉树。叉树。 本章介绍树和二叉树的基本概念、存储结构及一些常本章介绍树和二叉树的基本概念、存储结构及一些常用操作的算法实现。重点为二叉树内容。用操作的算法实现。重点为

2、二叉树内容。数据结构数据结构7.1 树树 树的定义树的定义 树树(Tree)是是 n(n0)个结点构成的集合。个结点构成的集合。n=0的的树称树称为空树；对为空树；对n0的树的树T，有：，有： 当当 n1时时，除根结点外其它结点被分成，除根结点外其它结点被分成 m(m0)个个互不相交的集合互不相交的集合T1 ,T2 , , Tm ，其中每个集合，其中每个集合Ti(1im)本身又是一棵结构与树类同的子树。本身又是一棵结构与树类同的子树。 有一个特殊的结点称为树的根结点，根结点没有有一个特殊的结点称为树的根结点，根结点没有前驱结点。前驱结点。数据结构数据结构特特点点 根结点没有前驱结点，除根结点之

3、外的所有结根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点；树中所有结点可以有零点有且只有一个前驱结点；树中所有结点可以有零个或多个后继结点。个或多个后继结点。 树结构的用途很广泛，如磁盘文件目录管理就是树树结构的用途很广泛，如磁盘文件目录管理就是树结构的一个典型应用。结构的一个典型应用。LIUWUWANGDOSWINDOWSUSERSC：FILE1FILE2FILEn数据结构数据结构 A D B C E F G H I J 结点、结点、 结点的度、结点的度、叶结点、叶结点、 分枝结点、分枝结点、孩子结点、双亲结点、孩子结点、双亲结点、 兄弟结点、兄弟结点、树的度、树的度、 结点

4、的层次、树的深度、结点的层次、树的深度、无序树、无序树、 有序树、有序树、 森林森林树的常用术语树的常用术语数据结构数据结构 树的表示方法树的表示方法常常用用方方法法直观表示法直观表示法主要用于直观描述树的逻辑结构主要用于直观描述树的逻辑结构形式化表示法形式化表示法主要用于树的理论描述主要用于树的理论描述T = ( D , R ) 凹入表示法凹入表示法主要用于树的屏幕和打印机显示主要用于树的屏幕和打印机显示数据结构数据结构 树的抽象数据类型树的抽象数据类型数据集合数据集合 是树的结点集合，是树的结点集合，每个结点由数据元素和构造数据每个结点由数据元素和构造数据元素之间关系的指针组成。元素之间关

5、系的指针组成。操作集合操作集合 数据集合上可进行的操作，如：创建、撤消、双亲结数据集合上可进行的操作，如：创建、撤消、双亲结点、左孩子结点、遍历树等。点、左孩子结点、遍历树等。（具体实现要结合存储结构）（具体实现要结合存储结构）数据结构数据结构 要求存储结构不但能存储各结点本身的要求存储结构不但能存储各结点本身的数据信息数据信息，还要能唯一地反映树中各结点之间的还要能唯一地反映树中各结点之间的逻辑关系逻辑关系。 树的存储结构树的存储结构双亲表示法双亲表示法 利用利用“树中每个结点除根结点外有且仅有一个双亲树中每个结点除根结点外有且仅有一个双亲”这这一性质。用一组连续的存储空间（一维数组）存储树

6、中的一性质。用一组连续的存储空间（一维数组）存储树中的各结点，其中每个元素表示树中的一个结点，包括结点本各结点，其中每个元素表示树中的一个结点，包括结点本身的身的信息信息和结点的和结点的双亲结点在数组中的序号双亲结点在数组中的序号。数据结构数据结构图图(a)所示的一棵树，其双亲表示法如图所示的一棵树，其双亲表示法如图(b)所示所示 A B D F E H I C G (a)dataparent012345678ABCDEFGHI00111244-1(b)数据结构数据结构 每个结点除存放每个结点除存放结点本身的信息结点本身的信息外，还存放外，还存放结点与孩结点与孩子之间的关系子之间的关系。通过指

7、针反映树中各结点之间的关系。通过指针反映树中各结点之间的关系。 设置结点指针域个数的两种方法：设置结点指针域个数的两种方法： 每个结点指针域的个数等于该结点的度数（每个结点指针域的个数等于该结点的度数（树树 中各结点中各结点不同构不同构） 每个结点指针域的个数等于该树的度数（每个结点指针域的个数等于该树的度数（树中树中 各结点各结点同构同构）孩子表示法孩子表示法数据结构数据结构图图(a)所示的一棵树，其孩子表示法如图所示的一棵树，其孩子表示法如图(b)所示所示 A B D F E H I C G (a)(b)ABECGFIHD root数据结构数据结构 将双亲表示将双亲表示法和孩子表示法法和孩

8、子表示法结合起来，各结结合起来，各结点的孩子结点分点的孩子结点分别组成单链表。别组成单链表。A-1BCDEFG0HI0111244dataparent01234567812345678双亲孩子表示法双亲孩子表示法数据结构数据结构 每个结点除每个结点除本身的信息外，本身的信息外，有两个分别指向有两个分别指向该结点的第一个该结点的第一个孩子结点和下一孩子结点和下一个兄弟结点的指个兄弟结点的指针域。针域。A B C D E FGHIroot孩子兄弟表示法孩子兄弟表示法数据结构数据结构7.2 二叉二叉树树 二叉树的定义二叉树的定义 二叉树二叉树 ( Binary Tree ) 是是 n ( n 0 )

9、 个有限结点个有限结点构成的集合，构成的集合，n = 0 的的二叉二叉树树称为空二叉树；称为空二叉树；n 0 的的二叉树由一个根结点和两个互不相交的、分别称为二叉树由一个根结点和两个互不相交的、分别称为左左子树子树和和右子树右子树的子二叉树组成。的子二叉树组成。数据结构数据结构 A B G C E F H I D 每个结点最多只有两个每个结点最多只有两个孩子，且有左右之分。孩子，且有左右之分。图例图例(a)(b)左子树(c)右子树(d)左子树 右子树(e)五种基本形态五种基本形态数据结构数据结构 满二叉树：满二叉树：在一棵二叉树中，若所有分支结点都存在一棵二叉树中，若所有分支结点都存在左子树和

10、右子树，并且所有叶结点都在同一层上，这在左子树和右子树，并且所有叶结点都在同一层上，这样的二叉树称为满二叉树。样的二叉树称为满二叉树。 A B C D E F G 1 2 3 4 5 6 7 (a) 满二叉树满二叉树 A B C D E 1 2 3 4 5 (b) 非满二叉树非满二叉树两种特殊的二叉树两种特殊的二叉树数据结构数据结构 完全二叉树：完全二叉树：若一棵具有若一棵具有 n 个结点的二叉树的结个结点的二叉树的结构与满二叉树的前构与满二叉树的前 n 个结点的结构相同，这样的二叉个结点的结构相同，这样的二叉树称为完全二叉树。树称为完全二叉树。 A B C D E F G 1 2 3 4 5

11、 6 7 (a) 满二叉树满二叉树 A B C D E F 1 2 3 4 5 6 (b) 完全二叉树完全二叉树 A B C D F 1 2 3 4 5 (c) 非完全二叉树非完全二叉树数据结构数据结构 二叉树抽象数据类型二叉树抽象数据类型数据集合数据集合 二叉树的结点集合，二叉树的结点集合，每个结点由数据元素和构造数每个结点由数据元素和构造数据元素之间关系的指针组成的数据。据元素之间关系的指针组成的数据。操作集合操作集合 数据集合上可进行的操作，如：创建、撤消、左插入数据集合上可进行的操作，如：创建、撤消、左插入结点、遍历二叉树等。结点、遍历二叉树等。（具体实现要结合存储结构）（具体实现要结

12、合存储结构）数据结构数据结构 二叉树的性质二叉树的性质 若规定根结点的层次为若规定根结点的层次为0，则，则一棵非空一棵非空二叉树的第二叉树的第i 层上最多有层上最多有2i ( i0 ) 个结点。个结点。 若规定空树的深度为若规定空树的深度为-1，则，则深度为深度为k的的二叉树的最大二叉树的最大结点数是结点数是2k+1-1( k-1 )个。个。 具有具有 n n个结点的完全个结点的完全二叉树的深度二叉树的深度 k为为: :1) 1(logn2数据结构数据结构 对于对于一棵非空的一棵非空的二叉树，如果叶结点数为二叉树，如果叶结点数为 n0，度为，度为2 的结点数为的结点数为 n2 ，则有，则有 n

13、0 = n2 + 1。证明证明：设：设 n：二叉树结点总数，二叉树结点总数， n1：度为度为1 1 的结点数的结点数 则有则有 n = n0 + n1 + n2 (1) 设设B：二叉树中的分支数：二叉树中的分支数 则有则有 B = n - 1 (2) 又有又有 B = n1 + 2 n2 (3)综合综合(1)、(2)、(3)式可得到：式可得到：n0 = n2 + 1数据结构数据结构 对于具有对于具有 n 个个结点的完全二叉树，如果按照从上结点的完全二叉树，如果按照从上至下和从左到右的顺序对所有结点从至下和从左到右的顺序对所有结点从 0开始顺序编号，则开始顺序编号，则对于任意的序号为对于任意的序

14、号为 i 的结点，有：的结点，有： 若若2i+2n，则序号为，则序号为 i 的结点的右孩子结点的序号的结点的右孩子结点的序号为为2i+2 ；如果；如果2i+2n，则序号为，则序号为 i 的结点无右孩子。的结点无右孩子。 若若2i+10，则序号为，则序号为 i 的结点的双亲结点的序号为的结点的双亲结点的序号为 (i-1)/2；否则，；否则， 序号为序号为 i 的结点是根结点，无双亲结点。的结点是根结点，无双亲结点。数据结构数据结构7.3 二叉树的设计和实现二叉树的设计和实现 二叉树的存储结构二叉树的存储结构二叉树的顺序存储结构二叉树的顺序存储结构用一组连续的存储单元存放二叉树中的结点。用一组连续

15、的存储单元存放二叉树中的结点。 A B C D E F 0 1 2 3 4 5 A BCD EF012345 0 1 2 3 4 5 A B C F E G 6 9 12 D A BCD EFG012345678910 11 12数据结构数据结构二叉树的链式存储结构二叉树的链式存储结构 用链建立二叉树中结点之间的关系，通常采用二叉用链建立二叉树中结点之间的关系，通常采用二叉链表形式。在二叉链表结构中，将二叉树结点设置为链表形式。在二叉链表结构中，将二叉树结点设置为 data为保存结点本身信息的数据域，为保存结点本身信息的数据域， leftChild 和和rightChild 分别是指向结点的左

16、孩子和右孩子的指针域。分别是指向结点的左孩子和右孩子的指针域。leftChildrightChilddata数据结构数据结构 A B C D G F E A B C D EFGroot还有一些其它形式，如三叉链表、带头结点的链表形式等。还有一些其它形式，如三叉链表、带头结点的链表形式等。数据结构数据结构二叉树的仿真指针二叉树的仿真指针 用数组存储二叉树中结点，数组中每个结点除数据用数组存储二叉树中结点，数组中每个结点除数据元素域元素域data外，再设置仿真指针域存储二叉树中结点之外，再设置仿真指针域存储二叉树中结点之间的关系。间的关系。leftChild 域和域和 rightChild 域分别

17、是左孩子结域分别是左孩子结点和右孩子结点在数组中的下标序号，点和右孩子结点在数组中的下标序号，-1表示空指针。表示空指针。数据结构数据结构 A B C D G F E ABCDEFG134-1-1-1-12-156-1-1-10123456data leftChild rightChild数据结构数据结构 二叉树的操作实现二叉树的操作实现 ( 二叉链存储结构二叉链存储结构 ) typedef struct Node DataType data ; struct Node *leftChild ; struct Node *rightChild ; BiTreeNode ;二叉链表结点结构可定义

18、为：二叉链表结点结构可定义为：数据结构数据结构 void Initiate ( BiTreeNode * * root ) *root =( BiTreeNode * )malloc( sizeof( BiTreeNode ) ; ( *root ) leftChild = NULL ; ( *root ) rightChild = NULL ; root创建二叉树创建二叉树 root的头结点的头结点初始化初始化数据结构数据结构 将数据域信息为将数据域信息为 x 的结的结点插入到二叉树中结点点插入到二叉树中结点curr 的左孩子处。如果结点的左孩子处。如果结点curr 原来有左孩子结点，则将该

19、原来有左孩子结点，则将该左孩子结点作为结点左孩子结点作为结点 x 的左的左孩子结点。孩子结点。左结点插入左结点插入curr xs x currs数据结构数据结构 BiTreeNode *InsertLeftNode( BiTreeNode *curr , DataType x ) BiTreeNode *s , *t ; if ( curr = = NULL ) return NULL ; t = curr leftChild ; s = ( BiTreeNode * ) malloc ( sizeof ( BiTreeNode ) ) ; s data = x ; s leftChild =

20、 t ; s rightChild = NULL ; curr leftChild = s ; return curr leftChild ; 数据结构数据结构 将数据域信息为将数据域信息为 x 的结的结点插入到二叉树中结点点插入到二叉树中结点curr 的右孩子处。如果结点的右孩子处。如果结点curr 原来有右孩子结点，则将该原来有右孩子结点，则将该右孩子结点作为结点右孩子结点作为结点 x 的右的右孩子结点。孩子结点。右结点插入右结点插入curr xscurr x s数据结构数据结构 BiTreeNode *InsertRightNode( BiTreeNode *curr , DataTyp

21、e x ) BiTreeNode *s , *t ; if ( curr = = NULL ) return NULL ; t = curr rightChild ; s = ( BiTreeNode * ) malloc ( sizeof ( BiTreeNode ) ) ; s data = x ; s rightChild = t ; s leftChild = NULL ; curr rightChild = s ; return curr rightChild ; 数据结构数据结构 删除二叉树中结点删除二叉树中结点curr 的左子树。当的左子树。当curr 或或curr的的左孩子结点

22、为空时删除失败。左孩子结点为空时删除失败。左子树删除左子树删除 BiTreeNode *DeleteLeftTree( BiTreeNode *curr ) if ( curr = = NULL | curr leftChild = = NULL) return NULL ; Destroy ( & curr leftChild ) ; curr leftChild = NULL ; return curr ; 数据结构数据结构 删除二叉树中结点删除二叉树中结点curr 的右子树。当的右子树。当curr 或或curr的的右孩子结点为空时删除失败。右孩子结点为空时删除失败。右子树删除右子树删除

23、BiTreeNode *DeleteRightTree( BiTreeNode *curr ) if ( curr = = NULL | curr rightChild = = NULL) return NULL ; Destroy ( & curr rightChild ) ; curr rightChild = NULL ; return curr ; 数据结构数据结构7.4 二叉树遍历二叉树遍历 二叉树遍历二叉树遍历 二叉树的遍历是指按照某种顺序访问二叉树的遍历是指按照某种顺序访问二叉树中的二叉树中的每个结点，使每个结点被访问一次且只被访问一次。每个结点，使每个结点被访问一次且只被访问一

24、次。 遍历操作使非线性结构线性化。遍历操作使非线性结构线性化。 遍历二叉树包括遍历二叉树包括三个步骤三个步骤：遍历根的左子树：遍历根的左子树( L )、遍历根的右子树遍历根的右子树( R )、访问根结点、访问根结点( D )。 数据结构数据结构DLR( (前序前序) ) LDR( (中序中序) ) LRD( (后序后序) )DRL( (逆前序逆前序) ) RDL( (逆中序逆中序) ) RLD( (逆后序逆后序) )层序遍历方式层序遍历方式二叉树遍历的基本方法二叉树遍历的基本方法数据结构数据结构前序遍历前序遍历 ( DLR ) 前序遍历的前序遍历的递归定义递归定义为：为：若二叉树为空，遍历结束

25、。否则：若二叉树为空，遍历结束。否则：. 访问根结点；访问根结点；. 前序遍历根结点的左子树；前序遍历根结点的左子树；. 前序遍历根结点的右子树。前序遍历根结点的右子树。 A B C D G F E 前序遍历前序遍历A B D G C E F数据结构数据结构 中序遍历的中序遍历的递归定义递归定义为：为：若二叉树为空，遍历结束。否则：若二叉树为空，遍历结束。否则：. . 中序遍历根结点的左子树；中序遍历根结点的左子树；. . 访问根结点；访问根结点；. 中序遍历根结点的右子树。中序遍历根结点的右子树。 A B C D G F E 中序遍历中序遍历D G B A E C F中序遍历中序遍历 ( L

26、DR )数据结构数据结构 后序遍历的后序遍历的递归定义递归定义为：为：若二叉树为空，遍历结束。否则，若二叉树为空，遍历结束。否则，. . 后序遍历根结点的左子树；后序遍历根结点的左子树；. . 后序遍历根结点的右子树；后序遍历根结点的右子树；. 访问根结点。访问根结点。G D B E F C A后序遍历后序遍历 ( LRD )后序遍历后序遍历 A B C D G F E 数据结构数据结构层序遍历层序遍历 层序遍历是指：从二叉层序遍历是指：从二叉树的根结点开始，从上至下树的根结点开始，从上至下逐层遍历，在同一层中，按逐层遍历，在同一层中，按照从左到右的顺序对结点逐照从左到右的顺序对结点逐个访问。

27、个访问。 A B C D G F E 层序遍历层序遍历A B C D E F G数据结构数据结构 在下面的算法中，函数在下面的算法中，函数 Visit ( t data ) 表示访表示访问指针问指针 t 所指向结点的数据域。为了设计通用的二叉所指向结点的数据域。为了设计通用的二叉树遍历函数，将该访问操作设计成遍历函数的一个函树遍历函数，将该访问操作设计成遍历函数的一个函数虚参，实际应用时再相应变换。数虚参，实际应用时再相应变换。 二叉树遍历的实现二叉树遍历的实现 ( 二叉链存储结构二叉链存储结构 )二叉树遍历函数二叉树遍历函数数据结构数据结构 void PreOrder( BiTreeNode

28、 *t , void Visit ( DataType item ) ) if ( t ! = NULL ) Visit ( t data ) ; PreOrder ( t leftChild , Visit ) ; PreOrder ( t rightChild , Visit ) ; 前序遍历前序遍历 ( DLR )数据结构数据结构 void InOrder( BiTreeNode * t , void Visit ( DataType item ) ) if ( t ! = NULL ) InOrder ( t leftChild , Visit ) ; Visit( t data )

29、; InOrder ( t rightChild , Visit ) ; 中序遍历中序遍历 ( LDR )数据结构数据结构 void PostOrder( BiTreeNode * t , void Visit ( DataType item ) ) if ( t ! = NULL ) PostOrder ( t leftChild , Visit ) ; PostOrder ( t rightChild , Visit ) ; Visit( t data ) ; 后序遍历后序遍历 ( LRD )数据结构数据结构层序遍历层序遍历 void LeverOrder( BiTreeNode *t ,

30、 void Visit ( DataType item ) ) SeqCQueue myQueue ; BiTreeNode *p ; if ( t != NULL ) QueueInitiate( & myQueue ) ; QueueAppend( &myQueue , t ) ; （注意队列结构体定义中元素的类型问题）注意队列结构体定义中元素的类型问题）数据结构数据结构 while ( QueueNotEmpty ( myQueue ) = = 1 ) QueueDelete( &myQueue , &p ) ; Visit( p data ) ; if ( p leftChild !=

31、 NULL ) QueueAppend(&myQueue , p leftChild ) ; if ( p rightChild != NULL ) QueueAppend(&myQueue , p rightChild ) ; 数据结构数据结构撤消操作函数撤消操作函数 void Destroy ( BiTreeNode * * root ) if ( ( *root ) != NULL & (*root) leftChild != NULL) Destroy ( &( *root ) leftChild ) ; if ( ( *root ) != NULL & (*root) rightCh

32、ild != NULL) Destroy( &( *root ) rightChild ) ; free ( * root ) ; 数据结构数据结构 二叉树遍历的应用二叉树遍历的应用 在在bt为根结点的二叉树中查找数据元素为根结点的二叉树中查找数据元素 x ，若找到，若找到，则返回该结点的指针，否则返回空指针。则返回该结点的指针，否则返回空指针。 BiTreeNode *Search ( BiTreeNode *bt , DataType x ) BiTreeNode *p ; if ( bt = = NULL ) return NULL ; if ( bt data = = x ) retu

33、rn bt ; 查找数据元素查找数据元素数据结构数据结构 if ( bt leftChild != NULL ) p = Search ( bt leftChild , x ) ; if ( p != NULL ) return p ; if ( bt rightChild != NULL ) p = Search ( bt rightChild , x ) ; if ( p != NULL ) return p ; return NULL ; 数据结构数据结构 以非递归方式模拟递归算法，需要设置一个栈结构以非递归方式模拟递归算法，需要设置一个栈结构保存指向某结点的指针，以便在遍历某结点的左子

34、树之保存指向某结点的指针，以便在遍历某结点的左子树之后，由该指针找到该结点的右子树。后，由该指针找到该结点的右子树。左子树右子树 非递归的二叉树遍历算法非递归的二叉树遍历算法数据结构数据结构 void PreOrder( BiTreeNode *t , void Visit ( DataType item ) ) BiTreeNode *stack MaxSize , *p ; int top ; if ( t = = NULL ) return ; top = 0 ; p = t ; while ( !( p = =NULL & top = = 0 ) ) while ( p != NULL

35、 ) Visit ( p data ) ;数据结构数据结构 if ( top leftChild ; if ( top rightChild ; 数据结构数据结构7.6 哈夫曼树哈夫曼树 哈夫曼树的基本概念哈夫曼树的基本概念路径、结点的路径长度、路径、结点的路径长度、二叉树的路径长度、带权二叉树、二叉树的路径长度、带权二叉树、二叉树的带权路径长度二叉树的带权路径长度 ( WPL = )iniilw1 1 3 5 7 带权二叉树带权二叉树WPL = 32数据结构数据结构 5 7 1 3 WPL = 33 1 7 3 5 WPL = 43 7 1 5 3 WPL = 29 叶结点的权相同，二叉树形

36、状不同，则叶结点的权相同，二叉树形状不同，则 WPL 就可就可 能不同；即使形状相同，但同样权值的叶结点所在位置能不同；即使形状相同，但同样权值的叶结点所在位置 不同，不同， WPL 也可能不同。也可能不同。数据结构数据结构最优二叉树最优二叉树 在权在权 w1 ,w2 , ,wn 对应的带权二叉树对应的带权二叉树 中，中，WPL最小的二叉树。也称为最小的二叉树。也称为哈夫曼树哈夫曼树。 由给定的由给定的 n个权值个权值 w1 , w2 , , wn 构造构造 n 棵只棵只有根结点的二叉树，从而得到一个二叉树森林有根结点的二叉树，从而得到一个二叉树森林 F = T1 , T2 , , Tn ；哈

37、夫曼算法哈夫曼算法数据结构数据结构 在在 F 中选取根结点的权值最小和次小的两棵二叉树中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；根结点的权值为其左、右子树根结点权值之和； 在集合在集合 F 中删除作为左、右子树的两棵二叉树，并中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合将新建立的二叉树加入到集合 F 中；中； 重复重复、两步，当两步，当 F 中只剩下一棵二叉树时，即中只剩下一棵二叉树时，即得哈夫曼树。得哈夫曼树。数据结构数据结构3567678

38、35对权集合为对权集合为W = 7 , 3 , 5 , 6 ，构造哈夫曼树的过程如下：，构造哈夫曼树的过程如下：83513678351367数据结构数据结构 哈夫曼树在编码问题中的应用哈夫曼树在编码问题中的应用编码编码 等长编码等长编码 不等长编码不等长编码字符字符码码000010100111ABCD(a)字符字符码码00011011ABCD(b)字符字符码码 011010111ABCD(c)字符的不同编码方案字符的不同编码方案数据结构数据结构 以需要编码的字符集以需要编码的字符集 d1 , d2 , , dn 为叶结点，为叶结点，以它们在电文中出现的次数或频率以它们在电文中出现的次数或频率

39、w1 , w2 , , wn 为它为它们的权值构造一棵哈夫曼树。们的权值构造一棵哈夫曼树。 为哈夫曼树各分支编码，规定左分支为为哈夫曼树各分支编码，规定左分支为 0 ，右分，右分支为支为 1 。则从根结点到每个叶结点所经过的路径分支组。则从根结点到每个叶结点所经过的路径分支组成的成的 0 或或 1 序列，就是该结点对应字符的编码，称为哈序列，就是该结点对应字符的编码，称为哈夫曼编码。夫曼编码。使电文编码总长最短的编码方案使电文编码总长最短的编码方案数据结构数据结构 补充例补充例 对对电文电文“ this is a tree ”进行编码。字符集为进行编码。字符集为 t , h , i , s ,

40、 (空格空格) , a , r , e ，相应的出现次数集合为，相应的出现次数集合为 2 , 1 , 2 , 2 , 3 , 1 , 1 , 2 ，构造哈夫曼树，并由此得到，构造哈夫曼树，并由此得到 哈夫曼编码表。哈夫曼编码表。数据结构数据结构哈夫曼编码树哈夫曼编码树 0 1 空 1 r a h 0 0 0 1 1 i t e s 0 0 0 1 1 1 哈夫曼编码哈夫曼编码字符字符编码编码thisare0010100101110010011000111空空数据结构数据结构若某工厂有一大批零件要分类，规定：若某工厂有一大批零件要分类，规定： 0.1 mm 一等品一等品 0.1 mm 0.4 m

41、m 二等品二等品 0.4 mm 1 mm 三等品三等品 1 mm 不合格品不合格品 哈夫曼树在判定问题中的应用哈夫曼树在判定问题中的应用数据结构数据结构 1 不合格不合格Y 三三等品等品Y 二等品二等品Y 0.4N 一等品一等品NN 0.1数据结构数据结构 0.4 三三等品等品Y 1N 不合格不合格N 二等品二等品N一等品一等品YY 0.1数据结构数据结构假设零件等级的分布概率为：假设零件等级的分布概率为：等级等级123不合格不合格概率概率0.400.350.200.05 0.4 0.2 0.05 0.35 (a) 哈夫曼树哈夫曼树数据结构数据结构 0.1一等品一等品Y 0.4N二等二等品品Y

42、N不合格不合格N三等品三等品Y 1(b) 对应的最佳判断过程对应的最佳判断过程数据结构数据结构7.7 树与二叉树的转换树与二叉树的转换 A C B E F D G A C B E F D G 树转换为二叉树树转换为二叉树数据结构数据结构 A C B E F D G A C B E F D G 数据结构数据结构 A C B E F D G A C B E F D G 二叉树还原为树二叉树还原为树数据结构数据结构ACBEFDGACBEFDG数据结构数据结构A AB BC CE ED DF FG GH HI IJ JK K 森林转换为二叉树森林转换为二叉树数据结构数据结构A AB BC CG GH

43、HI IJ JK KE ED DF FA AB BG GH HI IJ JK KC CE ED DF F数据结构数据结构7.8 7.8 树的遍历树的遍历. 访问根结点；访问根结点；. 按照从左到右的顺序按照从左到右的顺序 先根遍历根结点的每先根遍历根结点的每 一棵子树。一棵子树。 A C B E F D G A B E F C D G先根遍历先根遍历数据结构数据结构. 按照从左到右的顺序按照从左到右的顺序 后根遍历根结点的每后根遍历根结点的每 一棵子树；一棵子树；. 访问根结点。访问根结点。E F B C G D A A C B E F D G 后根遍历后根遍历数据结构数据结构第八章第八章 图

44、图 图是另一种非线性结构，比树型结构更加复图是另一种非线性结构，比树型结构更加复杂，树只是图的一种特例。树中结点之间具有层杂，树只是图的一种特例。树中结点之间具有层次关系，是一对多的关系；而图中元素之间具有次关系，是一对多的关系；而图中元素之间具有网状关系网状关系，是多对，是多对多的关系多的关系( ( 结点之间的关系是结点之间的关系是任意的任意的 ) )。 本章介绍图的基本概念、存储结构及一些常本章介绍图的基本概念、存储结构及一些常用操作的算法实现。用操作的算法实现。数据结构数据结构8.1 图图 图的基本概念图的基本概念 图图( Graph )是由结点集合及结点间的关系集合组成是由结点集合及结

45、点间的关系集合组成的一种数据结构。图的一种数据结构。图G的形式化定义为：的形式化定义为： G = ( V , E ) V = x | x 某个数据元素集合某个数据元素集合 E = ( x , y ) | x , y V 或或 E = | x , y V Path(x , y ) 数据结构数据结构ABDCFEHG(a) 图图 G1图图 G1 表示为表示为： G1 = ( V , E )V(G1) = A , B , C , D , E , F , G , H E(G1) = (A , B) , (A , C) , (B , D) , (C , D) , (C , F) , (E , G) , (

46、G , H) 图的画法示例及表示图的画法示例及表示数据结构数据结构图图 G2 表示为表示为： G2 = ( V , E )V(G2) = A , B , C , D , E , F E(G2) = , , , , , 弧（或有向边）弧（或有向边）EFBACD(b) 图图 G2数据结构数据结构结点和边、有向图和无向图、完全图（无向、有向）结点和边、有向图和无向图、完全图（无向、有向）依附于、邻接点依附于、邻接点结点的度结点的度TD(V) 、出度出度OD(V) 、入度入度ID(V)对有向图：对有向图：TD(V) = ID(V) + OD(V)边数边数 e = 结点数结点数 k2)(1kiiVTD基

47、本术语基本术语数据结构数据结构权、网或网络权、网或网络路径、路径长度、回路或环、简单路径、简单回路路径、路径长度、回路或环、简单路径、简单回路ABCDE60408030754535EBACD40505030302020数据结构数据结构子图、连通的、连通图、连通分量子图、连通的、连通图、连通分量23542136215421354678数据结构数据结构EFBACDEFBABCDAC强连通图、强连通分量强连通图、强连通分量生成树生成树数据结构数据结构 图的抽象数据类型图的抽象数据类型数据集合数据集合 由一组结点集合由一组结点集合vi和一组边集合和一组边集合ei 组成。若为带组成。若为带权图，还有每条

48、边上的权集合权图，还有每条边上的权集合wi 。操作集合操作集合 数据集合上可进行的操作，如：初始化、插入结点、数据集合上可进行的操作，如：初始化、插入结点、插入边、删除边、遍历图等。插入边、删除边、遍历图等。（具体实现要结合存储结构）（具体实现要结合存储结构）数据结构数据结构8.2 图的存储结构图的存储结构 要求存储结构不但能存储各结点本身的要求存储结构不但能存储各结点本身的数据信息数据信息，还，还要能反映图中各结点之间的要能反映图中各结点之间的关联关系关联关系。 假设图假设图 G = (V , E)有有n个结点，则可用以下形式的一个结点，则可用以下形式的一个个nn矩阵矩阵A描述边集合描述边集

49、合，A中的元素为：中的元素为： 若若(vi ，vj)E 或或 E 否则否则01ija 用一维数组存储图中结点的信息，用矩阵表示图中各用一维数组存储图中结点的信息，用矩阵表示图中各结点之间的结点之间的相邻相邻关系。关系。 图的邻接矩阵存储结构图的邻接矩阵存储结构数据结构数据结构12435(a) 无向图无向图54321A0010100011100010100111110B(b) 邻接矩阵邻接矩阵数据结构数据结构 邻接矩阵是对称的，可用邻接矩阵是对称的，可用n(n-1)/2个存储单元存放个存储单元存放它的上三角阵或下三角阵；它的上三角阵或下三角阵； 只需查看只需查看aij0？（或（或aji0？），就

50、可判断两结），就可判断两结点点vi ，vj 之间是否有边相连；之间是否有边相连； 容易求得各结点的度：容易求得各结点的度：第第i行（或第行（或第i列）中非零元素个数（或之和）就是结点列）中非零元素个数（或之和）就是结点i的度。的度。 1010)(njjinjijiaavTD 无向图无向图数据结构数据结构ABDCE(a) 有向图有向图EDCBAA0000000010100000000011110B(b) 邻接矩阵邻接矩阵数据结构数据结构 邻接矩阵是非对称的，要用邻接矩阵是非对称的，要用nn个存储单元存放；个存储单元存放； 查看查看aij0？可判断从结点可判断从结点vi到结点到结点vj是否有边相是