数据结构与STL树.pptx

《数据结构与STL树.pptx》由会员分享，可在线阅读，更多相关《数据结构与STL树.pptx（153页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 树和二叉树学习内容：1.树的逻辑结构2.树的存储结构3.二叉树的逻辑结构4.二叉树的存储结构5.树、森林、二叉树的转换6.哈夫曼树（计划学时6h）11.树的逻辑结构树的逻辑结构第1页/共153页5.1 树的逻辑结构定义 树是n(n0)个结点的有限集,如果n=0，称为空树；如果n0，则 (1)有且仅有一个称为根的结点root (2)n1时，其余结点可分为m个互不相交的有限集T1 Tn，其中每一个集合又是一棵树，称为根的子树2第2页/共153页5.1 树的逻辑结构3ABCDEFGHIJMKLrootT1T3T2第3页/共153页2.树的基本术语结点的度树的度叶结点分支结点4ABCDEFGH

2、IJMKL结点的度：结点拥有的子树的个数。树的度：树内各结点的度的最大值。叶结点：度为0的结点。分支结点：度不为0的结点。第4页/共153页2.树的基本术语孩子双亲兄弟祖先子孙5ABCDEFGHIJMKL 结点的子树的根称为该结点的结点的子树的根称为该结点的孩子孩子，该结，该结点称为孩子的点称为孩子的双亲双亲。同一双亲的孩子之间互称兄弟。同一双亲的孩子之间互称兄弟。结点的祖先：从根到该结点所经分支上的所有结点的祖先：从根到该结点所经分支上的所有结点。结点。结点的子孙：以某结点为根的子树中任一结点。结点的子孙：以某结点为根的子树中任一结点。第5页/共153页2.树的基本术语路径路径长度6ABCD

3、EFGHIJMKL路径：从根结点到其他结点的一条路经路径：从根结点到其他结点的一条路经。路径长度：路经经过的边的个数路径长度：路经经过的边的个数。路径长度路径长度=3=3第6页/共153页2.树的基本术语结点层次树的深度7ABCDEFGHIJMKL结点层次：从根开始，根为第一层，根的孩子结点层次：从根开始，根为第一层，根的孩子 为第二层，以此类推为第二层，以此类推。1234树的深度：树中结点的最大层次。树的深度：树中结点的最大层次。第7页/共153页2.树的基本术语层序编号812345678910131112 将树中结点按照从上到下将树中结点按照从上到下.同层从左到右的次序同层从左到右的次序依

4、次给它们从依次给它们从1开始编号，这种方式就是层序编号开始编号，这种方式就是层序编号。第8页/共153页2.树的基本术语有序树无序树9ABCDEFGHIJMKL 如果树中各结点的子树从左至右是有次序的（不如果树中各结点的子树从左至右是有次序的（不能互换），则称该树为有序树；否则为无序树。能互换），则称该树为有序树；否则为无序树。第9页/共153页2.树的基本术语森林10 m(m=0)棵互不相交的树的集合构成森林棵互不相交的树的集合构成森林。BCDEFGHIJMKL第10页/共153页2.树的基本术语同构11 两棵树同构就是这两棵树的形状相同两棵树同构就是这两棵树的形状相同。BCEFKLDGHI

5、JM第11页/共153页第五章 树和二叉树学习内容：1.树的逻辑结构2.树的存储结构3.二叉树的逻辑结构4.二叉树的存储结构5.树、森林、二叉树的转换6.哈夫曼树122.树的存储结构树的存储结构第12页/共153页5.2 树的存储结构四种存储结构双亲表示法孩子表示法双亲孩子表示法 孩子兄弟表示法树的基本操作13第13页/共153页1）双亲表示法14dataparentA-1B0C0D0E2F2G50123456size=6ABCDEFG结点结构结点结构结点的结点的C+描述描述 dataparent#define MaxSize 100 template struct pNode T data;

6、int parent;树的描述：树的描述：pNode TreeMaxSize;int size;第14页/共153页带右兄弟的双亲表示法15ABCDEFGdataparentrightsibA-1-1B02C03D0-1E25F2-1G5-10123456size=6结点结构结点结构结点的结点的C+描述描述 dataparentrightsibtemplate struct pNode T data;int parent，rightsib;树描述：树描述：pNode TreeMaxSize;int size;第15页/共153页2）孩子表示法多重链表表示法16ABFDECGrootABCDEF

7、Gdatachild1child2childd结点结构结点结构缺点：会浪费大量的指针域缺点：会浪费大量的指针域第16页/共153页2）孩子表示法17dataABCDEFG0123456 1 2 34 56ABCDEFGstruct CNode int child;CNode*next;template struct CBNode T data;CNode *firstchild;childnextdatafirstchild孩子结点表头结点孩子链表表示法孩子链表表示法第17页/共153页3）双亲孩子表示法18data parentA-1B0C0D0E2F2G40123456 1 2 34 56

8、ABCDEFG第18页/共153页4）孩子兄弟表示法19ABFDECGrootABCDEFG结点结构结点结构结点描述结点描述template struct TNode T data;TNode *firstchild,*rightsib;firstchilddatarightsib第19页/共153页树的基本操作InitTree()DestroyTree()Root()Parent()Depth()/求树的深度PreOrder()/先序遍历PostOrder()/后序遍历LevelOrder()/层次遍历20第20页/共153页树的遍历定义 从根结点出发，按照某种次序依次访问树的所有结点，使每

9、个结点仅被访问一次。分类 1.前序遍历 2.后序遍历 3.层序遍历21 访问：对结点的各种访问：对结点的各种处理，比如，输出结点处理，比如，输出结点内容内容第21页/共153页如何遍历这棵树？22ABCDEFGHIJMKLrootT1T3T2第22页/共153页树的遍历1.前序遍历 （1）访问根结点 （2）按照从左到右的顺序依次遍历根结点的每一棵子树。23ABCDEFGHIJMKLA BEFKL CG DHIJM第23页/共153页树的遍历2.后序遍历 （1）按照从左到右的顺序依次遍历根结点的每一棵子树 （2）访问根结点。24ABCDEFGHIJMKLEKLFB GC HIMJD A第24页/

10、共153页树的遍历3.层序遍历（也称为广度遍历）从第一层开始，从上到下逐层遍历，同层按从左到右的顺序遍历。25ABCDEFGHIJMKLA BCD EFGHIJ KLM第25页/共153页练习写出该树的前序.后序.层次遍历序列26ABCDEFG前序前序：ABCEFGD后序后序：BEGFCDA层次：层次：ABCDEFG第26页/共153页练习写出该树的度.深度，以及前序.后序.层次遍历序列27DECBAIHJKFGLM前序前序：ABEFCGDHKLMIJ后序后序：EFBGCKLMHIJDA层次：层次：ABCDEFGHIJKLM树的度为树的度为3 3，深度为，深度为4 4第27页/共153页第五章

11、 树和二叉树学习内容：1.树的逻辑结构2.树的存储结构3.二叉树的逻辑结构4.二叉树的存储结构5.树、森林、二叉树的转换6.哈夫曼树283.二叉树的逻辑结构二叉树的逻辑结构第28页/共153页5.2 二叉树的逻辑结构定义 n(n=0)个结点的有限集合，该集合或者为空集，或者由一个根结点和两棵互不相交的左右子树组成。特点 1.每个结点最多只有两个子树 2.左右子树次序不能颠倒29FGDEBCA第29页/共153页5.2 二叉树的逻辑结构树和二叉树的区别 30ABABABAB同一棵树同一棵树不同的二叉树不同的二叉树第30页/共153页5.2 二叉树的逻辑结构二叉树具备5种形态31RLLR二叉树的五

12、种不同形态二叉树的五种不同形态第31页/共153页5.2 二叉树的逻辑结构特殊的二叉树 （1）斜树 （2）满二叉树 （3）完全二叉树32第32页/共153页特殊的二叉树（1）斜树 所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树。33ABCABC第33页/共153页特殊的二叉树（2）满二叉树所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上。34891011121314154567231第34页/共153页特殊的二叉树（3）完全二叉树按从上到下.从左到右的顺序为结点编号，与满二叉树序号一一对应的二叉树。3581910456723第35页/共153页2.二

13、叉树的性质性质1：在二叉树的第i层上至多有 2i-1个结点(i1).36数学归纳法证明数学归纳法证明当当i=1 只有一个根结点只有一个根结点 2i-1=20=1成立成立假设假设i=k 结论成立，即第结论成立，即第k层最多有层最多有2k-1结点则结点则i=k+1时，由于第时，由于第k层每个结点最多有两个孩层每个结点最多有两个孩子结点，所以该层最多有结点子结点，所以该层最多有结点2*2k-1=2k结点结点.由此，该结论成立由此，该结论成立第36页/共153页2.二叉树的性质性质2 深度为 k 的二叉树至多有 2k-1 个结点(k0)。37根据性质根据性质1 1，求等比数列的前，求等比数列的前k k

14、项和：项和：20+21+22+2k-1=2k-1提示：试试利用性质提示：试试利用性质1第37页/共153页2.二叉树的性质性质3任何一棵二叉树T，如果其叶结点数为n0，度为2的结点数为n2，则n0=n2+1.38FGDEBCA第38页/共153页2.二叉树的性质1）二叉树只有三类结点，度为0.1.2的结点，所以 树总的结点：n0+n1+n22）二叉树n0没有分支，n1有1个分支；n2有2个分支，所以 树的总分支:2*n2+n139 结点数和分支数结点数和分支数的关系？的关系？FGDEBCA结点结点分支分支第39页/共153页习题已知正则二叉树中（只有度为0和2的结点）有n个叶子结点，则这个二叉

15、树的结点总数是_ A 2*n B 2*n-1 C 2*n+1 D 不确定40第40页/共153页2.二叉树的性质性质4具有n个结点的完全二叉树的深度为 +1。41根据性质根据性质2:2:设完全二叉树的深度为设完全二叉树的深度为k k，则其结点数则其结点数 2k-1-1 n 2k-1 2k-1 n 2k 所以所以 k-1 Log2n k Log2n 1，则其双亲为i/2 (2)如果2in，则结点无左孩子，否则其左孩子为2i (3)如果2i+1n，则无右孩子，否则其右孩子为2i+14381910456723第43页/共153页2.二叉树的性质442i2i+12i+22i+3ii+1i/2双亲左孩子

16、右孩子81910456723用归纳法可证（用归纳法可证（2）和（和（3），再用（），再用（2）和（和（3）证明（）证明（1）。）。第44页/共153页3.二叉树的基本操作InitBiTree()DestroyBiTree()PreOrder()/前序遍历InOrder()/中序遍历PostOrder()/后序遍历LevelOrder()/层次遍历45第45页/共153页4.二叉树的遍历三种遍历方式 1）前序遍历（DLR）2）中序遍历（LDR）3）后序遍历（LRD）4）层序遍历约定 D：根结点 L：左子树 R：右子树46第46页/共153页4.二叉树的遍历1.前序遍历（DLR）（1）访问根结点

17、（2）前序遍历左子树 （3）前序遍历右子树 47FGDEBCAA BDEFG C第47页/共153页4.二叉树的遍历2.中序遍历（LDR）（1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树48FGDEBCADBFEG A C第48页/共153页4.二叉树的遍历3.后序遍历（LRD）（1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点49FGDEBCADFGEB C A第49页/共153页4.二叉树的遍历4.层序遍历（也称为广度遍历）从第一层开始，从上到下逐层遍历，同层按从左到右的顺序遍历50FGDEBCAA BC DE FG第50页/共153页练习写出二叉树的前序.中序.后序

18、.层序序列51FGDEBCAH前序：前序：A BDEF CGH中序：中序：DBFE A GHC后序：后序：DFEB HGC A层序：层序：A BC DEG FH第51页/共153页思考已知二叉树的前序序列 ABCDEFGH 和中序序列 CDBAFEHG ，能否唯一确定一棵二叉树?D L R L D R L R D52第52页/共153页53前序序列前序序列 A BCD EFGH 中序序列中序序列 CDB A FEHG BCDEFGHAAABEFGHCDAABEFGHCDAABGHCDEF第53页/共153页练习已知二叉树的前序序列 ABHFDECKG 和中序序列 HBDFAEKCG ，画出该二

19、叉树。54第54页/共153页55HBDFEKCGA前序 ABHFDECKG 中序 HBDFAEKCG AABEKCGHDFAAB EKCGHFDAB KCGHFDEAB HFDECKG第55页/共153页思考什么样的二叉树前序序列和中序序列相同？什么样的二叉树后序序列和中序序列相同？什么样的二叉树前序序列和后序序列相同？D L R L D R L R D56第56页/共153页第五章 树和二叉树学习内容：1.树的逻辑结构2.树的存储结构3.二叉树的逻辑结构4.二叉树的存储结构5.树、森林、二叉树的转换6.哈夫曼树574.二叉树的存储结构二叉树的存储结构第57页/共153页5.4 二叉树的存储

20、结构二叉树的存储结构 1）顺序存储结构 2）二叉链表 3）三叉链表 4）线索链表58第58页/共153页1 1）顺序存储结构59 用一维数组存储二叉树中的结点用一维数组存储二叉树中的结点 结点的存储位置（下标）体现结点之间的逻辑关系结点的存储位置（下标）体现结点之间的逻辑关系父子关系。父子关系。完全二叉树 一般二叉树00 1 2 3 4 5 6 7 8 990 1 2 3 4 5 6 7 8 9137894562012543678第59页/共153页顺序存储结构60FGDEBCAHFGDEBCAHHHHHH1234567891011 1213ABCDEGFH1 2 3 4 5 6 7 8 9

21、10 11 12 13数据结构与STL方法：方法：1.将二叉树按照完全二叉树编号将二叉树按照完全二叉树编号 2.然后用一维数组存储该二叉树，其中无结点然后用一维数组存储该二叉树，其中无结点的位置使用的位置使用NULL表示表示完全二叉树适合采用顺序存储结构第60页/共153页2 2）二叉链表61lchilddatarchild 结点结构：LeftChilddataRightChildFGDEBCAACGBE rootD F 结点的结点的C+的类型描述：的类型描述：template struct Node T data;Node*lch;Node*rch;第61页/共153页二叉树的C+描述tem

22、plate class BiTreeprotected:Node*root;void Create (Node*&R,int i);void Release(Node*R);public:BiTree():root(NULL)BiTree(Node*R);void PreOrder(Node*R);void InOrder(Node*R);void PostOrder(Node*R);void LevelOrder(Node*R);BiTree();62第62页/共153页建立二叉树基本思想 以顺序存储结构作为建立二叉树的输入，根据二叉树的定义，分三步建树：1.建立根结点 2.建立左子树 3.

23、建立右子树63FGDEBCAHABCDEG000F00H第63页/共153页template void BiTree:Create(Node*&R,int i,char ch,int num)if(inum|chi=0)R=NULL;else R=new Node;R-data=chi;Create(R-lch,2*i,ch,num);Create(R-rch,2*i+1,ch,num);/注意，ch0没用。64FGDEBCAHABCDEG000F00H第64页/共153页二叉链表的遍历假设使用二叉链表表示二叉树已经建立，则如何实现以下四种遍历操作？PreOrder()/前序遍历 InOrde

24、r()/中序遍历 PostOrder()/后序遍历 LevelOrder()/层次遍历65第65页/共153页 PreOrder()前序遍历 DLR递归递归实现实现template void BiTree:PreOrder(Node *Root)if(Root!=NULL)coutdata;/访问结点 PreOrder(Root-lchild);/遍历左子树 PreOrder(Root-rchild);/遍历右子树 66第66页/共153页 PreOrder()前序遍历 DLR非递归实非递归实现现二叉树前序遍历非递归的关键 在前序遍历完某结点的左子树后，如何找到该结点的右子树的根？67 这就需

25、要栈：保存当前结点，然后当该结这就需要栈：保存当前结点，然后当该结点的左子树访问完毕后，当前结点出栈，访点的左子树访问完毕后，当前结点出栈，访问其右子树。问其右子树。lchDrchlchBrchlchArch第67页/共153页前序遍历过程68FGDEBCAAPrint(A)出栈出栈出栈出栈ABPrint(B)ABDPrint(D)AB出栈出栈A出栈出栈AEPrint(E)AEFPrint(F)AE出栈出栈CPrint(C)CGPrint(G)C出栈出栈A出栈出栈第68页/共153页基本思想1）如果当前结点非空访问当前结点当前结点入栈；将当前结点的左孩子作为当前结点；2）如果当前结点为空栈顶结

26、点出栈，将该结点的右孩子作为当前结点；反复执行1）2)，直到当前结点=NULL&栈空.69FGDEBCA第69页/共153页template void BiTree:PreOrder(Node*R)StackNode*S;while(!S.IsEmpty()|(R!=NULL)if(R!=NULL)coutdata;S.Push(R);R=R-lch;else R=S.Pop();R=R-rch;70A0B00C0root第70页/共153页InOrder()中序遍历LDR-递归递归template void BiTree:InOrder(Node *Root)if(Root!=NULL)In

27、Order(Root-lchild);/遍历左子树 coutdata;/访问结点 InOrder(Root-rchild);/遍历右子树 71A0B00C0root第71页/共153页InOrder()中序遍历LDR-非递归中序与前序遍历的区别 前序遍历：1）先访问该结点2）再入栈3）然后访问其左子树；4）出栈，访问其右子树 中序遍历：1）先入栈2）访问其左子树3）结点出栈，访问该结点；4）访问该结点的右子树72第72页/共153页中序遍历过程73FGDEBCAA入栈入栈AB入栈入栈ABD入栈入栈ABPrint(D)APrint(B)AE入栈入栈AEF入栈入栈AEPrint(F)C入栈入栈CG

28、入栈入栈CPrint(G)Print(C)APrint(E)Print(A)第73页/共153页基本思想1）如果当前结点非空当前结点入栈；将当前结点的左孩子作为当前结点；2）如果当前结点为空栈顶结点出栈，访问当前结点将该结点的右孩子作为当前结点；反复执行1）2)，直到当前结点NULL&栈空 74FGDEBCA第74页/共153页template void BiTree:InOrder(Node*R)StackNode*S;while(!S.IsEmpty()|(R!=NULL)if(R!=NULL)S.Push(R);R=R-lch;else R=S.Pop();coutdata;R=R-rc

29、h;75第75页/共153页PostOrder()后序遍历LRD-递归template void BiTree:PostOrder(Node *Root)if(Root!=NULL)PostOrder(Root-lchild);/遍历左子树 PostOrder(Root-rchild);/遍历右子树 coutdata;/访问结点 76第76页/共153页PostOrder()后序遍历LRD 非递归二叉树后序遍历的关键 1）当前结点入栈，访问其左子树 2）利用栈顶结点，访问其右子树 3）当前结点出栈，访问该结点77 因此，必须为栈中的元素设置标记，用因此，必须为栈中的元素设置标记，用来判断什么时

30、候出栈。来判断什么时候出栈。第77页/共153页后序遍历过程78FGDEBCAl,A,r,1入栈入栈l,A,r,1l,B,r,1入栈入栈l,A,r,1l,B,r,1l,D,r,1-2入栈入栈l,A,r,1l,B,r,2Print(D)l,A,r,1l,B,r,2l,E,r,1入栈入栈l,F,r,1-2l,A,r,1l,B,r,2l,E,r,1入栈入栈l,A,r,2l,C,r,1-2Print(G)l,A,r,2l,C,r,1l,G,r,1-2入栈入栈l,A,r,2Print(C)l,A,r,1l,B,r,2l,E,r,2Print(F)l,A,r,1l,B,r,2Print(E)l,A,r,2

31、Print(B)l,A,r,2l,C,r,1入栈入栈Print(A)第78页/共153页PostOrder()后序遍历LRD-非递归后序遍历的过程1.当前结点指针!=NULL时，入栈，置标记(L)，遍历左子树;2.当前结点指针=NULL时，(1)若栈顶元素标记为R，退栈打印，直到栈顶元素标记为L；(2)若栈顶元素标记为L，改标记R,则遍历右子树；反复执行1）2）直到栈空。79栈中元素的结构栈中元素的结构template struct SNode Node*ptr;int tag;/1左左 2右右;第79页/共153页template void BiTreee:Postorder(Node*R)

32、SNode SMAXSIZE;int top=-1;do while(R!=NULL)/左子树不空，进栈 S+top.ptr=R;Stop.tag=1；R=R-lch;while(top!=-1&Stop.tag=2)/右子树返回,访问结点；coutdata;top-;if(top!=-1&Stop.tag=1)/左子树返回，修改标志；R=Stop.ptr-rch;Stop.tag=2;while(top!=-1)80数据结构与STLint tag Node*ptr第80页/共153页LevelOrder()/层次遍历层序遍历从上到下，从左到右依次访问每一个结点。先访问的结点，其左右孩子结点也

33、会先访问。81FGDEBCAABCDEGF第81页/共153页LevelOrder()层次遍历这是一个队列的应用基本思想 根结点非空，入队。如果队列不空 队头元素出队 访问该元素 若该结点的左孩子非空，则左孩子入队；若该结点的右孩子非空，则右孩子入队；82FGDEBCA第82页/共153页template void BiTree:LevelOrder(Node*R)QueueNode*Q;if(R!=NULL)Q.InQueue(R);while(!Q.IsEmpty()Node*p=Q.DelQueue();coutdata;if(p-lchild!=NULL)Q.InQueue(p-lch

34、ild);if(p-rchild!=NULL)Q.InQueue(p-rchild)83第83页/共153页析构函数template void BiTree:Release(Node *Root)if(Root!=NULL)Release(Root-lchild);/释放左子树 Release(Root-rchild);/释放右子树 delete Root;/释放根结点 84第84页/共153页例例1统计二叉树中的结点总数 85LRFGDEBCAH提示：提示：结点总数结点总数=左子树左子树 +右子树右子树 +1+1第85页/共153页统计二叉树中的结点总数template int Count(

35、Node*R)if(R=NULL)return 0;elseint m=Count(R-lch);int n=Count(R-rch);return m+n+1;86FGDEBCAH第86页/共153页思考题已知二叉树的前序序列 和中序序列，编写算法建立二叉树。测试数据：前序序列 ABHFDECKG 中序序列 HBDFAEKCG 87数据结构与STL第87页/共153页88HBDFEKCGA前序 ABHFDECKG 中序 HBDFAEKCG AABEKCGHDFAAB EKCGHFDAB KCGHFDEAB HFDECKG数据结构与STL第88页/共153页HBDFEKCGA基本思路1.前序序

36、列(s1,e1)中的s1位置是根结点R2.在中序序列(s2,e2)中找R的位置pos3.将前序序列进行分割 i=s1+pos-s2，(s1+1,i)(i+1,e1)4.将中序序列进行分割 (s2,pos-1)(pos+1,e2)反复继续，1，2，3,4直到区间中只有一个元素。89数据结构与STL前序 ABHFDECKG 中序 HBDFAEKCG 第89页/共153页代码/辅助函数，查找元素x中序序列的位置template int BiTree:Find(T x,T InBuf,int s,int e)/s中序序列查找区间左边界 e 右边界for(int i=s;i=e&InBufi!=0;i+

37、)if(InBufi=x)return i;return 0;/注意下标0的元素没使用90数据结构与STL第90页/共153页template void BiTree:Create(Node*&R,T PreBuf,T InBuf,int s1,int e1,int s2,int e2)if(s1=e1)int pos=Find(PreBufs1,InBuf,s2,e2);if(pos=0)R=NULL;else R=new Node;R-data=PreBufs1;int i=s1+pos-s2;Create(R-lch,PreBuf,InBuf,s1+1,i,s2,pos-1);Creat

38、e(R-rch,PreBuf,InBuf,i+1,e1,pos+1,e2);else R=NULL;91数据结构与STL前序 ABC 中序 BAC 第91页/共153页3 3）三叉链表92 A D E B C F root lchilddatarchild 结点结构：parentLeftChilddataRightChildparent第92页/共153页3 3）三叉链表 三叉链表结点的C+的类型描述：template struct Node public:T data;Node*parent;Node*lchild;Node*rchild;93第93页/共153页4.4.线索链表N个结点的二

39、叉链表一共有_指针域？其中有_指针域是NULL?我们能不能充分利用这些NULL的指针域，用来保存一些有用的信息？942NN+1第94页/共153页4.4.中序线索链表95ACGBErootDFFGDEBCAlchilddatarchild 结点结构：ltagrtag第95页/共153页线索二叉树线索二叉树template struct Node T data;Node*lch,*rch;int ltag；/1 表示左孩子 2表示前驱 int rtag;/1 表示右孩子 2表示后继96第96页/共153页第五章 树和二叉树学习内容：1.树的逻辑结构2.树的存储结构3.二叉树的逻辑结构4.二叉树的

40、存储结构5.树、森林、二叉树的转换6.哈夫曼树975.树、森林、二叉树的转换树、森林、二叉树的转换第97页/共153页5.5 5.5 树、森林、二叉树的转换树的孩子兄弟表示法98ABCDEFGABFDECGroot第98页/共153页5.5 5.5 树、森林、二叉树的转换二叉链表表示法99ABCEDFGABFDECGroot第99页/共153页物理结构100ABFDECGrootABFDECGroot物理结构相同，只是解释不同而已。第100页/共153页逻辑结构101ABCDEFGABCEDFG树和二叉树的逻辑结构有一一对应的关系。树和二叉树的逻辑结构有一一对应的关系。BCDEFGA第101页

41、/共153页1.树转换成二叉树102树与二叉树的对应关系树与二叉树的对应关系当以二叉链表为存储结构时，给定一颗树，可以找当以二叉链表为存储结构时，给定一颗树，可以找到唯一的一颗二叉树与之对应。到唯一的一颗二叉树与之对应。任何一颗与树对应的二叉树，其右子树必空。任何一颗与树对应的二叉树，其右子树必空。ABCEDABCDEABCD EA BC E D A BC D E 第102页/共153页树转换成二叉树转换原则 第一个右兄弟结点 右孩子 第一个孩子结点 左孩子103数据结构与STLDECBAIHJKFGLMDECBAIHJKFGLM第103页/共153页树转换为二叉树的方法：树转换为二叉树的方法

42、：（1 1）加加线线：树树中中所所有有相相同同双双亲亲结结点点的的兄兄弟弟结结点点之之间间加加一一条连线；条连线；（2 2）去去线线：对对树树中中的的每每个个结结点点，只只保保留留它它与与第第一一个个孩孩子子结结点之间的连线，删去该结点与其他孩子结点之间的连线；点之间的连线，删去该结点与其他孩子结点之间的连线；（3 3）调调整整：整整理理所所有有保保留留的的和和添添加加的的连连线线，使使每每个个结结点点的的孩孩子子结结点点连连线线位位于于左左孩孩子子指指针针位位置置，使使每每个个结结点点的的兄兄弟弟结结点点连线位于右孩子指针位置。连线位于右孩子指针位置。第104页/共153页树转换成二叉树特点

43、 树的前序遍历 二叉树的前序遍历 树的后序遍历 二叉树的中序遍历105前序前序:ABCDE后序：后序：BDCEA前序前序:ABCDE中序：中序：BDCEA第105页/共153页ABCDEF GIHABDCEIFGH练习练习第106页/共153页二叉树还原为树的方法二叉树还原为树的方法 （1 1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子都与该结点的双亲结点用线连起来；都与该结点的双亲结点用线连起来；（2 2）删除原二叉树中所有双亲结点与右孩子结点的连线；）删除原二叉树中所有双亲结点与右孩子结点的连线；（3

44、3）整理所有保留的和添加的连线，使每个结点的孩子结点连线顺序位于下方孩）整理所有保留的和添加的连线，使每个结点的孩子结点连线顺序位于下方孩子结点位置。子结点位置。第107页/共153页2.森林转换成二叉树森林：是若干棵树的集合若干棵树森林，每一棵树二叉树 森林二叉树转换原则 1）将森林中的每棵树转换成二叉树 2）从第二棵树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子。108第108页/共153页森林转换为二叉树方法森林转换为二叉树方法从第二棵二叉树开始，依次将当前二叉树的根结点从第二棵二叉树开始，依次将当前二叉树的根结点作为前一棵二叉树根结点的右孩子结点，直至所有作为前一棵二

45、叉树根结点的右孩子结点，直至所有二叉树都连接起来。二叉树都连接起来。第109页/共153页森林转换成二叉树110DECBAIHJKFGDGECBFAIHJK第110页/共153页3.二叉树转换成森林转换原则 1）根结点的右孩子 第二棵树的根结点 根结点右孩子的右孩子第三棵树的根结点 2）根结点的左孩子 按照结点的左孩子是该结点的第一个孩子，结点右孩子是该结点的右兄弟转换。111第111页/共153页二叉树转换成森林112DECBAIHJKFGDGECBFAIHJK第112页/共153页4.森林的遍历森林有两种遍历方式 1）前序遍历 前序遍历森林中的每一棵树 2）后序遍历 后序遍历森林中的每一棵

46、树113第113页/共153页森林的遍历前序序列：后序序列：114DECBAIHJKFGABECD FG HIJKEBCDA GF IKJH第114页/共153页第五章 树和二叉树学习内容：1.树的逻辑结构2.树的存储结构3.二叉树的逻辑结构4.二叉树的存储结构5.树、森林、二叉树的转换6.哈夫曼树1156.哈夫曼树哈夫曼树第115页/共153页5.6 5.6 哈夫曼树1.相关概念 1）叶子结点的权值 对叶子结点赋予一个有意义的数量值。2）二叉树的带权路径长度 设二叉树有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。11627549例如：例如：WPL=7

47、2+5 2+2 3+4 3+9 2=60第116页/共153页 3）哈夫曼树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。117WPL1=2 2+4 3+5 3+3 2=37WPL2=2 3+4 3+5 2+3 1=31WPL3=2 2 2+3 2+4 2+5 2=28 WPL4=2 2 3+3 3+4 2+5 1=28三棵具有相同权值叶子结点的二叉树三棵具有相同权值叶子结点的二叉树3452图图a3452图图b图图c图d第117页/共153页已知：一组权值给定的叶子结点w1,w2,wn，如何构造一棵哈夫曼树？118提示提示

48、：只要让只要让权值最大权值最大的叶子结点离根的叶子结点离根最近最近，权值最小权值最小的叶子结点离根的叶子结点离根最远最远，就能使，就能使带权路径长度最小。带权路径长度最小。2.2.Huffman树构造算法树构造算法第118页/共153页构造哈夫曼树（从下向上构造）已知：权值表 w1,w2,wn1）选择有效权值中最小的两个，构成最小二叉树，标记这两个权值已用。2）将这两个权值相加，之和并入权值表;返回1。结束条件如果权值表没有没用过的权值。119第119页/共153页例如：已知权值 W=5,6,2,9,7 1209562725769767139257第一步第一步第二步第二步第三步第三步第120页

49、/共153页例如：已知权值 W=5,6,2,9,7 1216713第四步第四步925716925716671329第五步第五步：注意注意:结点有规律的结点有规律的放置问题放置问题(全部左小全部左小右大或全部左大右小右大或全部左大右小)第121页/共153页3.Huffman编码编码给每一个字符标记一个单独的代码。编码分类等长编码：ASCII码等不等长编码：Huffman编码122例如，假设要传送的电文为 ABACCDA，电文中只有A,B,C,D四种字符。00 01 00 10 10 11 00，码长14。(表a,等长码)0 110 0 10 10 111 0，码长13。(表b)第122页/共1

50、53页思想（不等长编码）使用频率高的字符，编码长度短；使用频率低的字符，编码长度长；利用不等长编码，可以使报文总长度较短，这也是文件压缩技术的核心。123第123页/共153页不等长编码的关键：解码时的唯一性 比如：A:0 B:1 C:10 编码：AABAABC00100110 解码：AA?124 让任意编码都让任意编码都不是其他编码的不是其他编码的前缀前缀B:10B:10C:11C:11编码：编码：AABAABC0010001011解码：解码：AABAABC第124页/共153页Huffman编码是最优前缀编码.约定 左分支：0 右分支：1叶结点编码 从根到叶子的路径125952716671