第4 章数据结构.ppt

第第 4 章章 数据结构数据结构 4.1 基本数据结构与算法基本数据结构与算法 4.2 线性表线性表 4.3 栈和队列栈和队列4.4 树和二叉树树和二叉树 4.5 查找查找4.6 内部排序内部排序ABCDEFG姓名姓名 学号学号 成绩成绩 班级班级 李红李红 9761059 95 机机97.6 1065865 A C G T2D H I T3J M B E L KT1 F 树树型型结结构构是是一一类类重重要要的的非非线线性性数数据据结结构构，元元素素结结点点间间存存在在明明显显的的分分支支和和层层次次关关系系。现现实实世世界界中中，能能用用树树的的结结构构表表示示的的例例子子：学校的行政关系、书的层次结构、人类的家族血缘关系等。学校的行政关系、书的层次结构、人类的家族血缘关系等。4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 1.1.树的定义树的定义概念：概念：树是树是n（n0）个结点构成的有限集合。个结点构成的有限集合。n=0为空为空树；树；n0时时，树中结点应该满足两个条件，树中结点应该满足两个条件（1）有且仅有一个特定的根的结点。）有且仅有一个特定的根的结点。（2）其余的）其余的n-1个结点个结点可划分为可划分为m（m0）个互不相交的有限集）个互不相交的有限集T1，T2，Tm，其中，其中Ti又是一棵树，称为又是一棵树，称为根的子树。根的子树。示意图：示意图：T1B，E，F，J，KT2C，GT3D，H，I，L4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 T1T2T31.1.树的定义树的定义4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 2.2.树的基本概念树的基本概念(相关术语相关术语)1 1）根结点）根结点:没有前驱的结点只有一个没有前驱的结点只有一个,称为根结点。称为根结点。2 2）双亲（父）结点）双亲（父）结点:树中每个结点只有一个直接前驱树中每个结点只有一个直接前驱,称为该结称为该结 点的双亲结点或父结点。点的双亲结点或父结点。3 3）孩子（）孩子（子子）结结点点：一个一个结结点的子树的根或者后继结点数称为点的子树的根或者后继结点数称为该节点的孩子该节点的孩子结结点或子点或子结结点。点。4 4）叶子结点）叶子结点(终端结点终端结点):):没有子结点没有子结点(后继后继)的结点。的结点。ABCDEFGHIJKL1.1.树的定义树的定义4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 2.2.树的基本概念树的基本概念(相关术语相关术语)A:是根是根结结点点,同时是同时是B B、C C、D D结结点的父点的父结结点或双亲点或双亲结结点点B:是是E E、F F的父结点，的父结点，E E、F F是是B B的子的子结结点或孩子点或孩子结结点点J、K、L、F、G、I：是叶是叶子节点子节点1.1.树的定义树的定义4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 2.2.树的基本概念树的基本概念(相关术语相关术语)5）兄弟：）兄弟：同一个双亲同一个双亲的孩子结点之间互称兄弟。的孩子结点之间互称兄弟。6）堂兄弟：）堂兄弟：其其双亲在同一层双亲在同一层的结点互为堂兄弟。的结点互为堂兄弟。7）结点的祖先：）结点的祖先：结点的祖先是从结点的祖先是从根到该结点所经分支的根到该结点所经分支的所有结点。所有结点。8）结点的子孙：）结点的子孙：以某结点为根的子树中的任一结点都称以某结点为根的子树中的任一结点都称为该结点的子孙。为该结点的子孙。1.1.树的定义树的定义4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 2.2.树的基本概念树的基本概念(相关术语相关术语)ABCDEFGHIJKLB的子孙为的子孙为E、F、J、K。G与与E、F、H、I互为互为堂堂兄弟结点兄弟结点L的祖先为的祖先为A、D、H。B,C,D互为互为兄弟兄弟1.1.树的定义树的定义4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 2.2.树的基本概念树的基本概念(相关术语相关术语)9)9)结点的层次：结点的层次：从根开始定义起，根为第一层，根的孩子从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第为第二层。若某结点在第k k层，则其子树的根就在第层，则其子树的根就在第k+1k+1层。层。10)结点的度结点的度:一个结点的子树的个数一个结点的子树的个数(拥有拥有后继的个数后继的个数)。11)树的度树的度:所有所有结点度的最大值结点度的最大值。12）树的深度或高度：）树的深度或高度：树中结点的树中结点的最大层次最大层次称为树的深度称为树的深度。1.1.树的定义树的定义4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 2.2.树的基本概念树的基本概念(相关术语相关术语)ABCDEFGHIJKL结点结点A的层次：的层次：1结点结点L的层次：的层次：4结点的度结点的度:A的度为的度为3；C的度为的度为1 F的度为的度为0 树的度：树的度：3树的深度：树的深度：4注意注意:一棵树中一棵树中,每个结点的度数之和每个结点的度数之和=结点总数结点总数-1-1=树中树中边的条数边的条数1.1.树的定义树的定义4.4 树与二叉树树与二叉树4.4.1 树的定义和基本术语树的定义和基本术语 2.2.树的基本概念树的基本概念(相关术语相关术语)13）有序树：）有序树：如果将树中结点的各子树看成从左至如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树。右是有次序的（即不能互换），则称该树为有序树。否则为无序树。在有序树的最左边的根称为第一个否则为无序树。在有序树的最左边的根称为第一个孩子，最右边的称为最后一个孩子。孩子，最右边的称为最后一个孩子。14）森林：）森林：是是m m（m0m0）棵互不相交的树的集合。对）棵互不相交的树的集合。对树中根结点而言，其子树的集合即为森林。由此，树中根结点而言，其子树的集合即为森林。由此，可用森林和树相互递归的定义来描述树。可用森林和树相互递归的定义来描述树。因因为为树树的的每每个个结结点点的的度度不不同同，存存储储困困难难，使使对对树的处理算法很复杂，所以引出二叉树的讨论。树的处理算法很复杂，所以引出二叉树的讨论。1.1.二叉树的定义二叉树的定义4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树v定定义义：二二叉叉树树是是n(nn(n 0)0)个个结结点点的的有有限限集集，它它或或为为空空树树(n=0)n=0)，或或由由一一个个根根结结点点和和两两棵棵分分别别称称为为左左子子树树和和右右子子树树的互不相交的二叉树构成。的互不相交的二叉树构成。v特特点点：每每个个结结点点至至多多有有二二棵棵子子树树(即即不不存存在在度度大大于于2 2的的结结点点)二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的子树有左、右之分，且其次序不能任意颠倒v二叉树的五种基本形态二叉树的五种基本形态 空空二叉树二叉树 仅有仅有根结点根结点 右子树右子树为空为空 左子树左子树为空为空左右子树左右子树均非空均非空1.1.二叉树的定义二叉树的定义性质性质1：二叉树的第二叉树的第i层上至多有层上至多有2 i-1（i 1）个结点。个结点。证明：证明：根据二叉树的特点，结论是显然的。（用归纳法根据二叉树的特点，结论是显然的。（用归纳法证明）证明）。性质性质2：深度为深度为k k的二叉树中至多的二叉树中至多2 2k k-1-1个结点。个结点。证明：证明：深度为深度为k k的二叉树最多有的二叉树最多有k k层，根据性质层，根据性质1 1，只要，只要将第将第1 1层到第层到第k k层的最大结点数相加，就可得到整个二叉层的最大结点数相加，就可得到整个二叉树中结点的最大值。树中结点的最大值。21-1+2 2-1+2 k-1=2 k-1(k 1)4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树2.2.二叉树的性质二叉树的性质4231567891011121314151.1.二叉树的定义二叉树的定义4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树2.2.二叉树的性质二叉树的性质性质性质3：对任何一棵二叉树对任何一棵二叉树T T，如果其终端结点数为，如果其终端结点数为n n0 0，度，度为为2 2的结点数为的结点数为n n2 2，则，则n n0 0n n2 21 1。ABCDEF证明：证明：(2)(2)进入分支总数进入分支总数m(m(每个结点唯一分支进入每个结点唯一分支进入)n=m+1(1)(1)结点总数结点总数 n=n0+n1+n2 (n1是度为是度为1的结点数的结点数)(3)m(3)m个分支是由非叶子结点射出个分支是由非叶子结点射出 m=n1+2n2最后得最后得:n0n21 叶子结点：叶子结点：n0=3 度为度为2的结点：的结点：n2=21.1.二叉树的定义二叉树的定义4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树2.2.二叉树的性质二叉树的性质满二叉树满二叉树定定义义：如如果果一一个个二二叉叉树树深深度度为为K K，结结点点数数为为2 2k k-1-1，则则称称为为满满二叉树二叉树特点：特点：除最后一层外，每一层所有结点都有两个子结点除最后一层外，每一层所有结点都有两个子结点。4231567891011 1213 14 15满二叉树满二叉树1.1.二叉树的定义二叉树的定义4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树2.2.二叉树的性质二叉树的性质完全二叉树完全二叉树定义定义:指深度为指深度为k k的，有的，有n n个结点的，且每一个结点都与深个结点的，且每一个结点都与深度为度为k k的满二叉树中编号从的满二叉树中编号从1 1至至n n的结点的结点一一对应一一对应。特点特点:叶子结点只可能在最下面两层上叶子结点只可能在最下面两层上,且最下层叶子结点且最下层叶子结点集中在树的左部。任一结点集中在树的左部。任一结点,右分支下子孙结点最大层次右分支下子孙结点最大层次为为h h，则左分支必为，则左分支必为h h或或h+1h+1。423156789104231567非完全二叉树非完全二叉树注意注意:满二叉树满二叉树必是完全二叉必是完全二叉树；而完全二树；而完全二叉树未必是满叉树未必是满二叉树。二叉树。1.1.二叉树的定义二叉树的定义4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树2.2.二叉树的性质二叉树的性质性质性质4 4：具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度k为为log2n+1证明：证明：根据完全二叉树的定义和性质根据完全二叉树的定义和性质2可知，当一棵完全可知，当一棵完全二叉树的深度为二叉树的深度为k，结点个数为，结点个数为n时，有时，有 2k-1-1n2k-1 即即2k-1n2k对不等式取对数，有对不等式取对数，有 k-1log2n 2 2k-1k-1-1=3-1=3个个4231567深度为深度为3 3的的完全二叉树完全二叉树结点结点数最多情况是数最多情况是2 2k k-1=-1=7 7个个1.1.二叉树的定义二叉树的定义4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树2.2.二叉树的性质二叉树的性质性质性质5 5：具有具有n个结点的完全二叉树，从上至下和从左到右个结点的完全二叉树，从上至下和从左到右的顺序对所有结点从的顺序对所有结点从1开始顺序编号，则对任意结点开始顺序编号，则对任意结点i有有:1)i=1,该结点是根结点。否则该结点是根结点。否则(i1),其双亲其双亲结点序号为结点序号为i/2。2)如果如果2in,其左孩子结点的序号为其左孩子结点的序号为2i。如。如2、3、4、5结点）结点）3)如果如果 2in,则则i结点，无左子结点结点，无左子结点,显然也没右结点。显然也没右结点。4)(如图中如图中6、7结点）结点）3）如果）如果2i+1n，则序号为，则序号为i的结点的右孩子结点的序号为的结点的右孩子结点的序号为 2i+1 (如如2、3、4的右结点分别为的右结点分别为5，7，9）；）；如果如果2i+1n，则序号为，则序号为i的结点无右孩子的结点无右孩子结点。结点。(如如5、6、7)42315678910作用：作用：很容易确定每个结点的父结点、左子和右子结点的位置。很容易确定每个结点的父结点、左子和右子结点的位置。1.1.二叉树的定义二叉树的定义4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树2.2.二叉树的性质二叉树的性质3.3.二叉树的存储结构二叉树的存储结构(1)(1)顺序存储结构顺序存储结构:用一组用一组连续的连续的存储单元存放二叉树中的结点存储单元存放二叉树中的结点存储存储结构结构优点：优点：适用于满二叉树和完全二叉树，适用于满二叉树和完全二叉树，按结点从上至按结点从上至下，从左到右顺序存放，下，从左到右顺序存放，结点序号唯一反映出结点间结点序号唯一反映出结点间逻辑关系，逻辑关系，又可用数组下标值确定结点位置。又可用数组下标值确定结点位置。缺点：缺点：对一般二叉树，需增加许多空结点将一棵二叉对一般二叉树，需增加许多空结点将一棵二叉树改造成完全二叉树，树改造成完全二叉树，浪费大量存储空间浪费大量存储空间。(否则数否则数组元素下标间组元素下标间不能反映各结点间逻辑关系不能反映各结点间逻辑关系)存储存储结构结构1.1.二叉树的定义二叉树的定义4.4 树与二叉树树与二叉树4.4.2 二叉树二叉树2.2.二叉树的性质二叉树的性质3.3.二叉树的存储结构二叉树的存储结构(1)(1)顺序存储结构顺序存储结构:用一组用一组连续的连续的存储单元存放二叉树中的结点存储单元存放二叉树中的结点(2)链式存储结构链式存储结构:每个结点由每个结点由数据域数据域、左指针域左指针域和和右指针域右指针域组成。组成。lchildDatarchildlchildDatarchildADBCEFAECBDF在在n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空指针域个空指针域定义：定义：按照一定规律对二叉树中的每个结点访问一次按照一定规律对二叉树中的每个结点访问一次目的：目的：非线性结构线性化。非线性结构线性化。二叉树是非线性结构，经过一次二叉树是非线性结构，经过一次完整遍历，可将各结点的非线性排列变为某种意义的线性序完整遍历，可将各结点的非线性排列变为某种意义的线性序列。列。4.4 树与二叉树树与二叉树4.4.3 遍历二叉树遍历二叉树一棵二叉树的组成一棵二叉树的组成:根结点根结点 D(D(访问根结点访问根结点)左子树左子树 L(L(遍历左子树遍历左子树)右子树右子树 R(R(遍历右子树遍历右子树)3 3种遍历方式：种遍历方式：(1)前序遍历前序遍历(DLR)(2)中序遍历中序遍历(LDR)(3)后序遍历后序遍历(LRD)定义：定义：按照一定规律对二叉树中的每个结点访问一次按照一定规律对二叉树中的每个结点访问一次目的：目的：非线性结构线性化。非线性结构线性化。二叉树是非线性结构，经过一次二叉树是非线性结构，经过一次完整遍历，可将各结点的非线性排列变为某种意义的线性序完整遍历，可将各结点的非线性排列变为某种意义的线性序列。列。4.4 树与二叉树树与二叉树4.4.3 遍历二叉树遍历二叉树(1)前序遍历前序遍历(DLR)(2)中序遍历中序遍历(LDR)(3)后序遍历后序遍历(LRD)访问访问根结点根结点按照按照前前序遍历序遍历顺序访问根结点的顺序访问根结点的左子树左子树按照按照前前序遍历序遍历顺序访问根结点的顺序访问根结点的右子树右子树按中序遍历顺序访问根结点的按中序遍历顺序访问根结点的左子树左子树访问访问根结点根结点按中序遍历顺序访问根结点的按中序遍历顺序访问根结点的右子树右子树按后序遍历顺序访问根结点的按后序遍历顺序访问根结点的左子树左子树按后序遍历顺序访问根结点的按后序遍历顺序访问根结点的右子树右子树访问访问根结点根结点先序遍历：先序遍历：D L R中序遍历：中序遍历：L D R后序遍历：后序遍历：L R DADBCT1T2T3D L RAD L RD L RBDCD L R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCBDAC DBCA4.4 树与二叉树树与二叉树4.4.3 遍历二叉树遍历二叉树举例：举例：前序遍历前序遍历(根左右根左右)：中序遍历中序遍历(左根右左根右)：后序遍历后序遍历(左右根左右根)：a b d e g h c fd b g e h a c fd g h e b f c a1 1）在一棵二叉树上第）在一棵二叉树上第4 4层的结点数最多是层的结点数最多是_。A.4 B.8 C.32 D.12A.4 B.8 C.32 D.122)2)在深度为在深度为5 5的满二叉树中，叶子结点的个数为的满二叉树中，叶子结点的个数为_。A.32 B.31 C.16 D.15A.32 B.31 C.16 D.153)3)在深度为在深度为5 5的二叉树中，至多有的二叉树中，至多有_个结点。个结点。A.32 B.31 C.16 D.15A.32 B.31 C.16 D.154 4）在具有）在具有10 10 个结点的树中，其边的树目为个结点的树中，其边的树目为_。A.11 B.10 C.8 D.9A.11 B.10 C.8 D.95 5）设一棵完全二叉树共有）设一棵完全二叉树共有1010个结点，则在该二叉树中的叶个结点，则在该二叉树中的叶 子结点数为子结点数为_。A.9 B.5 C.2 D.4A.9 B.5 C.2 D.4习题习题解答：解答：BCBDB5.根据性质根据性质5，可知最后叶子结点为，可知最后叶子结点为10，其父结点是，其父结点是5，且该结点，且该结点5是最后一个是最后一个非叶子结点非叶子结点,那么从结点那么从结点 610均为叶子结点。（均为叶子结点。（1061）423156789106 6 设一棵二叉树中有设一棵二叉树中有3 3个叶子结点，有个叶子结点，有8 8个度为个度为1 1的结点，则该二叉的结点，则该二叉树中总的结点数是树中总的结点数是_。A.12 B.13 C.14 D.15A.12 B.13 C.14 D.157.7.下面关于完全二叉树的叙述中，错误的是下面关于完全二叉树的叙述中，错误的是_。A.A.除了最后一层外，每一层上结点数均达到最大值除了最后一层外，每一层上结点数均达到最大值 B.B.可能缺少若干个左右叶子结点可能缺少若干个左右叶子结点 C.C.完全二叉数一般不是满二叉数完全二叉数一般不是满二叉数 D.D.具有结点的完全二叉树的深度为具有结点的完全二叉树的深度为loglog2 2n+1n+18.8.对于所示的二叉树，其后序遍历序列是对于所示的二叉树，其后序遍历序列是_。A.ABDECFG B.DEBAFCGA.ABDECFG B.DEBAFCG C.DEBFGCA D.GFCEBDA C.DEBFGCA D.GFCEBDADBCAEFG解答：解答：BBC6.=n0+n1+n2=3+8+(3-1)7.(性质性质3:n0=n2+1 ）9.在深度为在深度为7的满二叉树中，的满二叉树中，叶子结点的个数为叶子结点的个数为_。(06.4(06.4月）月）A)32 B)31 C)64 D)6310.对如下二叉树，进行后序遍历的结果为对如下二叉树，进行后序遍历的结果为_。（。（06.406.4月月 )A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA解答：解答：解答：解答：CDACDA11.11.分析：分析：分析：分析：设叶子结点数为设叶子结点数为设叶子结点数为设叶子结点数为n0,n0,度为度为度为度为1 1的结点数的结点数的结点数的结点数n1,n1,度为度为度为度为2 2的结点数的结点数的结点数的结点数n2,n2,度为度为度为度为3 3的结点数的结点数的结点数的结点数n3,n3,度为度为度为度为4 4的结点数的结点数的结点数的结点数n4,n4,则总结点数：则总结点数：则总结点数：则总结点数：n=n0+n1+n2+n3+n4 (1)n=n0+n1+n2+n3+n4 (1)设树的总入分支数为设树的总入分支数为设树的总入分支数为设树的总入分支数为m,m,则则则则 n=m+1 (2)n=m+1 (2)而而而而mm个进入分支分别由非叶子结点射出，所以个进入分支分别由非叶子结点射出，所以个进入分支分别由非叶子结点射出，所以个进入分支分别由非叶子结点射出，所以 m=n1+2n2+3n3+4n4 (3)m=n1+2n2+3n3+4n4 (3)由（由（由（由（1 1）（）（）（）（2 2）（）（）（）（3 3）式可以得到：）式可以得到：）式可以得到：）式可以得到：n0=n2+2n3+3n4+1=2+21+31+1=8n0=n2+2n3+3n4+1=2+21+31+1=8 DBCAEF11.设树设树T的度为的度为4，其中度为，其中度为1、2、3、4的结点个数分别为的结点个数分别为4、2、1、1，则，则T中的叶子节点为中的叶子节点为_。A.8 B.7 C.6 D.512.对如下对如下a图二叉树，进行中序遍历的结果为图二叉树，进行中序遍历的结果为_。（。（06.906.9月月)A)A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG13.结论结论“_”是正确的是正确的 A.二叉树的度为二叉树的度为2 B.树中结点的度可以小于树中结点的度可以小于2 C.二叉树中至少有一个结点的度为二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度为二叉树中任何一个结点的度为2ACEFDGBa图图答案答案:ABC14.解析解析解析解析:要使二叉树在规定的结点数下的深度最小要使二叉树在规定的结点数下的深度最小要使二叉树在规定的结点数下的深度最小要使二叉树在规定的结点数下的深度最小,这样的二叉树这样的二叉树这样的二叉树这样的二叉树只能是完全二叉树只能是完全二叉树只能是完全二叉树只能是完全二叉树,根结点点的层次是根结点点的层次是根结点点的层次是根结点点的层次是0,0,根据性质根据性质根据性质根据性质2,2,结点与深度的关结点与深度的关结点与深度的关结点与深度的关系为系为系为系为:n=2 n=2h+1h+1-1-114.14.假定根结点的层次是假定根结点的层次是假定根结点的层次是假定根结点的层次是0,0,含有含有含有含有7 7个结点的的二叉树的最小树深是个结点的的二叉树的最小树深是个结点的的二叉树的最小树深是个结点的的二叉树的最小树深是()A)3 B)4 C)2 D)5 A)3 B)4 C)2 D)515.已知二叉树后序遍历序列是已知二叉树后序遍历序列是dabec，中序遍历序列是中序遍历序列是debac，它的前序遍历序列是，它的前序遍历序列是_。A.cedba B.acbed C.decab D.deabc填空题：填空题：填空题：填空题：1.1.某二叉树中度为某二叉树中度为某二叉树中度为某二叉树中度为2 2的结点有的结点有的结点有的结点有1818个，个，个，个，2.2.则该二叉树中有则该二叉树中有则该二叉树中有则该二叉树中有_叶子结点。（叶子结点。（叶子结点。（叶子结点。（05.405.4月月月月 ）dCebab图图分析：由后序分析：由后序分析：由后序分析：由后序dabecdabec确定确定确定确定c c c c为根结点，由中序为根结点，由中序为根结点，由中序为根结点，由中序debacdebac知知知知左子树为左子树为左子树为左子树为debadebadebadeba,再由再由再由再由后序后序后序后序dabecdabec后知后知后知后知e e e e为左子树的根结为左子树的根结为左子树的根结为左子树的根结点，再由中点，再由中点，再由中点，再由中debacdebac知知知知d d d d为为为为e e e e的左结点及的左结点及的左结点及的左结点及a a a a、b b b b关系。最后关系。最后关系。最后关系。最后如如如如b b b b图图图图.A 19A 19