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

《数据结构第六章-树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章-树和二叉树.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A线性结构B非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面第六章树和二叉树o6.1树的定义和基本术语o6.2二叉树n6.2.1二叉树的定义n6.2.2二叉树的性质n6.2.3二叉树的存储结构o6.3遍历二叉树和线索二叉树n6.3.1遍历二叉树n6.3.2线索二叉树o6.4树和森林n6.4.1树的存储结构n6.4.2森林与二叉树的转换o6.6赫夫曼树及其应用n6.6.1最优二叉树(赫夫曼树)n6.6.2赫夫曼编码o树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的

2、结构。它非常类似于自然界中的树。ABCDEFGH树形结构结点间具有分层次的连接关系HBCDEFGA6.1树的定义和基本术语p树(Tree)是n(n0)个结点的有限集合T，它满足如下条件：有且仅有一个称为根(Root)的结点。其余结点可划分为m(m=0)个互不相交的有限集合T1,T2,Tm,其中每个集合又是一棵树，并称其为根的子树(SubTree)。这是一个递归定义。有时n=0也称为空树。ACGT2DHIT3JMBELKT1F树的表示方法1）树形图法2）嵌套集合法3）广义表形式4）凹入表示法(A(B,C(E,F),D(G)ABCDEFGABCEFDGABDGEFC线性结构（一对一关系）树结构（一

3、对多关系）第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个终端结点(无后继)其它数据元素树中其它结点(一个前驱、一个后继)(一个前驱、多个后继)树形结构和线性结构的比较树结构的基本术语o结点结点(node)表示树中的元素，包括数据元素及若干指向其子树的分支。o结点的度结点的度(degree)结点拥有的子树数。o叶子叶子(leaf)或终端结点终端结点度为0的结点。o分支结点分支结点度大于零的结点。o树的度树的度树中所有结点的度的最大值。o孩子孩子(child)结点的子树的根。o双亲双亲(parents)孩子结点的上层结点。o兄弟兄弟(sibling)同一双亲的孩子。o堂兄弟

4、堂兄弟其双亲在同一层的结点互为堂兄弟。o结点的层次结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层。o深度深度(depth)树中结点的最大层次数。o森林森林(forest)m(m0)棵互不相交的树的集合。ABCDEFGHIJKLM树的抽象数据类型定义：ADTTree数据对象数据对象D：D是具有相同特性的数据元素的集合。数据关系数据关系R：若D为空集，则称为空树;若D仅含一个数据元素，则R为空集，否则RH，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若Droot，则存在Droot的一个划分D1,D2,.,Dm（m0），对任意jk（

5、1j,km）有DjDk=，且对任意的i（1im），唯一存在数据元素xiDi，有 H;（3）对 应 于 D root 的 划 分，H ，.，有唯一的一个划分H1,H2,.,Hm（m0），对任意jk（1j,km）有HjHk=，且对任意的i（1im），Hi是Di上的二元关系，（Di,Hi）是一棵符合本定义的树，称为根root的子树。树的抽象数据类型定义-基本操作（之一）InitTree(&T)；操作结果：构造空树T。DestroyTree(&T)；初始条件：树T存在。操作结果：销毁树T。CreateTree(&T，definition)；初始条件：definition给出树T的定义。操作结果：按de

6、finition构造树T。ClearTree(&T)；初始条件：树T存在。操作结果：将树T清为空树。树的抽象数据类型定义-基本操作（之二）TreeEmpty(T)初始条件：树T存在。操作结果：若T为空树，则返回TURE，否则FALSE。TreeDepth(T)初始条件：树T存在。操作结果：返回T的深度。Root(T)初始条件：树T存在。操作结果：返回T的根。Value(T,cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。树的抽象数据类型定义-基本操作（之三）Assign(T，cur_e，value)初始条件：树T存在，cur_e是T中某个结点。操作结果

7、：结点cur_e赋值为value。Parent(T，cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T，cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T，cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。树的抽象数据类型定义-基本操作（之四）InsertChild(&T，&p，i，c)；初始条件：树T存

8、在，p指向T中某个结点，1ip所指结点的度1，非空树c与T不相交。操作结果：插入c为T中p指结点的第i棵子树。DeleteChild(&T，&p，i)；初始条件：树T存在，p指向T中某个结点，1ip指结点的度。操作结果：删除T中p所指结点的第i棵子树。TraverseTree(T，Visit()；初始条件：树t存在，Visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败，则操作失败。ADTTree6.2二叉树o二叉树的定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树

9、的互不相交的二叉树构成。o二叉树的特点：每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的五种基本形态：空二叉树空二叉树只有一个根结点只有一个根结点的二叉树的二叉树右子树为空右子树为空的二叉树的二叉树左子树为空左子树为空的二叉树的二叉树左、右子树均左、右子树均非空的二叉树非空的二叉树注意：注意：二叉树中子树是有左右之分的，即使只有一棵子树，或为左子二叉树中子树是有左右之分的，即使只有一棵子树，或为左子树，或为右子树树，或为右子树这不是二叉树这不是二叉树这是二叉树这是二叉树6.2.2二叉树的性质o性质性质1：在二叉树的第i层上至多有2i-1个结

10、点(i1)。o性质性质2：深度为k的二叉树至多有2k-1个结点(k1)。o性质性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。1234567几种特殊形态的二叉树o满二叉树n定义：深度为k且有2k-1个结点的二叉树n特点：每一层上的结点数都是最大结点数p完全二叉树n定义：定义：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。n特点：叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1n说明：满二叉树是完全二叉树

11、,反之不成立;对于完全二叉树,若某结点无左孩子,则必无右孩子,该结点为叶结点。1231145891213671014151231145891267101234567123456o性质性质4：具有n个结点的完全二叉树的深度为log2n+1o性质性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2(2)如果2in，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+11231145891267106.2.3二叉树的存储结构

12、o顺序存储结构用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。下标01234567891011A B C D E F G H I J K LABCDEFGHIJKLo对完全二叉树而言，顺序存储结构既简单又节省存储空间。o一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。(最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间)ABCDEEDCBA链式存储结构typedefstructBiTNodeTElemTypedata;structBiTNod

13、e*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;rchilddatalchilddataparentlchildrchilddatalchildrchildparent链式存储结构示例注意：一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。基本操作的函数原型说明(一)StatusCreateBiTree(BiTree&T);/按先序次序输入二叉树中结点的值（一个字符），/空格字符表示空树

14、，/构造二叉链表表示的二叉树T。StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二叉链表存储结构,Visit是对结点操作的应用函数/先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。/一旦Visit()失败，则操作失败。基本操作的函数原型说明(二)StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二叉链表存储结构,Visit是对结点操作的应用函数。/中序遍历二叉树T，一旦Visit()失败，则操作失败。StatusPostOrderTrave

15、rse(BiTreeT,Status(*Visit)(TElemTypee);/采用二叉链表存储结构,Visit是对结点操作的应用函数。/后序遍历二叉树T，一旦Visit()失败，则操作失败。StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二叉链表存储结构,Visit是对结点操作的应用函数。/层序遍历二叉树T，一旦Visit()失败，则操作失败。6.3遍历二叉树按某条搜索路径巡访二叉树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。ABCDGEFo假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍

16、历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：oDLR先（根）序遍历，oLDR中（根）序遍历，oLRD后（根）序遍历。先序遍历二叉树的操作定义若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。ABCDFEGABCDGEF中序遍历二叉树的操作定义若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。CBDFAGEABCDGEF后序遍历二叉树的操作定义若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。CFDB

17、GEAABCDGEF例：已知结点的先序序列和中序序列，求整棵二叉树o先序序列：A B C D E F Go中序序列：C B E D A F GACBEDFGABCDEFGABCFDEG先序遍历二叉树的递归算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit)returnOK;returnERROR;elsereturnOK;/PreOrderTrave

18、rse作业o分别写出中序遍历二叉树和后序遍历二叉树的递归算法o已知一棵二叉树的中序和后序序列如下，画出此二叉树并写出该二叉树的先序遍历序列。中序序列：A,B,C,D,J,E,F,H,G,I后序序列：B,C,J,D,A,H,I,G,F,E中序遍历二叉树的非递归算法o基本思想中序遍历一棵非空树t时，首先应该进入t的左子树访问，此时由于t的根结点及右子树尚未访问，因此必须将t保存起来，放入栈中，以便访问完其左子树后，从栈中取出t，进行其根结点及右子树的访问；对t的左子树和右子树的遍历也是如此。o主要步棸1)先将根结点入栈；2)将栈顶元素的所有左孩子依次入栈；3)出栈一个结点，访问之；4)若该结点的右

19、孩子不空，入栈，重复2)，3)步；5)如果栈不空，重复3)，4)步，否则结束。StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存储结构，中序遍历二叉树的非递归算法。采用二叉链表存储结构，中序遍历二叉树的非递归算法。InitStack(S);Push(S,T);/根指针进栈根指针进栈while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);/向左走到尽头向左走到尽头Pop(S,p);/空指针退栈空指针退栈if(!StackEmpty(S)/访问结点，向右一步访问结

20、点，向右一步Pop(S,p);if(!Visit(p-data)returnERROR;Push(S,p-rchild);/if/whilereturnOK;/InOrderTraverse算法6.2算法6.3StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;/根指针进栈，遍历左子树根指针进栈，遍历左子树else/根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树Pop(S,p);if(

21、!Visit(p-data)returnERROR;p=p-rchild;/else/whilereturnOK;/InOrderTraverse6.3.2线索二叉树on个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为“线索”）o这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。线索二叉树结点的结构:其中，ltag和rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，

22、还是指向其前趋或后继的线索。0 lchild域指示其左孩子ltag=1 lchild域指示其前驱 0 rchild域指示其右孩子rtag=1 rchild域指示其后继datalchildrchildrtagltag中序线索二叉树的表示注意：图中的实线表示指针，虚线表示线索。结点C的左线索为空，表示C是中序序列的开始结点，无前趋；结点E的右线索为空，表示E是中序序列的终端结点，无后继。线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。6.4树和森林o树的存储结构n双亲表示法（静态链表存储）：以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在(静态)链表中的位置

23、 双亲表示法举例RADEFCBGKHR -1 A 0 B 0 C 0 D 1 E 1 F 3 G 6 H 6 K 6 0123456789数组下标:#defineMAX_TREE_SIZE100typedefstructPTNodeTElemTypedata;intparent;/双亲位置域PTNode;typedefstructPTNodenodesMAX_TREE_SIZE;intn;/结点数PTree;*便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。孩子链表存储表示举例RADEFCBGKH0123456789数组下标:R A B C D E F G H K 1 2 3 4 5 6

24、7 8 9 6.4.1树的存储结构o孩子表示法（链式存储）typedefstructCTNode/孩子结点结构孩子结点结构intchild;structCTNode*next;*ChildPtr;typedefstruct/双亲结点结构双亲结点结构TElemTypedata;ChildPtrfirstchild;/孩子链表头指针孩子链表头指针CTBox;typedefstruct/树结构树结构CTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根的位置结点数和根的位置CTree;*便于涉及孩子的操作；*求结点的双亲时不方便。6.4.1树的存储结构o孩子兄弟表示法：n又称二叉

25、树表示法，或二叉链表表示法。记以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。ntypedefstructCSNodeELemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;RADEFCBGKHR A DE C HF GBK孩子兄弟表示法示例：*易于实现找结点孩子的操作；6.4.2森林与二叉树的转换o将树转换成二叉树的步骤：n将所有兄弟结点用边连接起来n对每个结点，除了保留与其长子的边外，去掉该结点与其它孩子的边ab

26、cefd 转换转换abcefd 整理整理abcefd说明：根结点没有右孩子说明：根结点没有右孩子6.4.2森林与二叉树的转换o将森林转换成二叉树的步骤n将森林中的每棵树转换成二叉树n将每个二叉树的根结点看成兄弟用边连起来bacdefghi 转换转换abcdefghi 整理整理abcdefghi6.4.2森林与二叉树的转换o将二叉树转换成树(森林)的步骤n如果根有右子树，将根的右子树分开，得到几棵二叉树n根据得到的二叉树往回转换。(若结点X是双亲y的左孩子，则把X的右孩子，右孩子的右孩子,都与y用连线连起来，最后去掉所有X到右孩子的连线。)abcdefghijk 转换转换feabcdjkghi

27、去边去边整理整理feabcdjkghi6.4.3树和森林的遍历o树的两种遍历方法：n先根遍历：访问树的根结点；依次先根遍历每棵子树。R A D E B C F G H Kn后根遍历：依次后根遍历每棵子树；访问树的根结点。D E A B G H K F C RRADEFCBGKH6.4.3树和森林的遍历o森林的两种遍历方法：n先序遍历森林：若森林非空，则访问森林中第一棵树的根结点；先序遍历第一棵树的根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的的森林。n中序遍历森林：若森林非空，则中序遍历第一棵树的根结点的子树森林；访问森林中第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的的森

28、林。o先序遍历：ABCDEFGHIJo中序遍历：BCDAFEHJIGABCDEFGH IJo先序遍历：ABCDEFGHIJo中序遍历：BCDAFEHJIGABCDEFGH IJ说明o先序遍历森林等同于先序遍历该森林对应的二叉树o中序遍历森林等同于中序遍历该森林对应的二叉树o当用二叉链表作树和森林的存储结构时，树和森林的先序遍历和后序遍历，可用二叉树的先序遍历和中序遍历算法来实现。6.6赫夫曼树及其应用o路径长度路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。o树的路径长度树的路径长度：从树根到每一结点的路径长度之和。o结点的带权路径长度结点

29、的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。o树的带权路径长度树的带权路径长度：树中所有叶子结点的带权路径长度之和。通常记作：n WPL=kk k=1 6.6.1最优二叉树（赫夫曼树）o定义：假设有n个权值1,2,n，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为i,则其中：带权路径长度WPL最小的二叉树称做最优二叉树最优二叉树或赫夫曼树赫夫曼树。例：下面三棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4abcd7524abcd7524cdab7524(a)WPL=72+52+22+42=36(b)WPL=73+53+21+42=46(c)WPL=71+52+

30、22+42=35赫夫曼算法的基本思想o根据给定的n个权值1,2,n构成n棵二叉树的集合F=T1,T2,Tn其中每棵二叉树Ti中只有一个带权为i的根结点,其左右子树均空。o在F中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。o在F中删除这两棵树，同时将新得到的二叉树加入F中。o重复上述两个步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。构造赫夫曼树举例cdab7524abc2d457abc6d57abcd1176.2.2赫夫曼编码在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：p发送

31、方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样p发送的二进制编码尽可能地短编码方式o等长编码等长编码：将给定字符集C中每个字符的码长相同o【例】设待压缩的数据文件共有100000个字符，这些字符均取自字符集C=a，b，c，d，e，f，等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为300000位。编码方式o不等长编码：将频度高的字符编码设置短，将频度低的字符编码设置较长。o根据计算公式：(45*1+13*3+12*3+16*3+9*4+584)*1000=224000，整个文件被编码为224000位，比定长编码方式节约了约25的存储空

32、间。编码方式o注意注意：变长编码可能使解码产生二义性。产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同。o【例】设E、T、W分别编码为00、01、0001，则解码时无法确定信息串0001是ET还是W。编码方式o前缀编码：对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。o可以利用二叉树来设计二进制的前缀编码。设每种字符在电文中出现的次数为i，其编码长度为li,，电文中只有n个字符，则电文总长为：n WPL=kk。k=1前缀编码o如何得到电文总长最短的二进制的前缀编码？(1)利用字符集中每个字符的使用频率作为权值构造一

33、个赫夫曼树；(2)从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。532311178291400000001111110 1 1 012345678 1 01 1 1 01 1 1 1 1 1 00 00 1 1 10 1 0HC假设有一个电文字符集中有8个字符，每个字符的使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，现以此为例设计哈夫曼编码。哈夫曼编码设计过程为：（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到5,29,7,8,14,23,3,11；（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，本章小结o掌握树的定义和基本术语，灵活运用二叉树的性质，熟练掌握二叉树的存储结构。o能够快速写出二叉树的先序、中序和后序序列，并熟练掌握与理解二叉树遍历的递归非递归算法。o熟练掌握树的各种存储结构，并能够对森林和二叉树进行相互转换。o会构造赫夫曼树并给出相应的赫夫曼编码。作业o假设用于通讯的电文仅由8个字符组成（字母表中ah），字母在电文中出现的频率为7，15，3，6，10，27，12，20，画出字母频率作权值的赫夫曼树，并写出赫夫曼编码，并求带权路径长度WPL。