《数据结构C树和二叉树学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构C树和二叉树学习教案.pptx（202页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1数据结构数据结构(sh j ji u)C树和二叉树树和二叉树第一页，共202页。树的定义树的定义(dngy)树：树：n n（n0n0）个结点的有限集合）个结点的有限集合(jh)(jh)。当当n n0 0时，称为空树；时，称为空树；任意一棵非空树满足以下条件：任意一棵非空树满足以下条件：有且仅有一个特定的称为根的结点；有且仅有一个特定的称为根的结点；当当n n1 1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m m（m0m0）个互不相交）个互不相交的有限集合的有限集合(jh)T1,T2,Tm(jh)T1,T2,Tm，其中每个集合，其中每个集合(jh)(jh)又是一棵树
2、，又是一棵树，并称为这个根结点的子树。并称为这个根结点的子树。5.1 树树的的逻逻辑辑(lu j)结构结构树的定义是采用递归方法树的定义是采用递归方法第1页/共202页第二页，共202页。(a)一棵树结构一棵树结构(jigu)(b)一个非树结构一个非树结构(jigu)(c)一个非一个非树结构树结构(jigu)5.1 树树的的逻逻辑辑(lu j)结构结构树的定义树的定义(dngy)ACBGFEDHIACBGFDACBGFDE第2页/共202页第三页，共202页。树的应用举例树的应用举例文件文件(wnjin)结构结构5.1 树树的的逻逻辑辑(lu j)结构结构My ComputerC:D:E:et
3、cWINDOWSProgram FilesPictureMusic第3页/共202页第四页，共202页。树的基本树的基本(jbn)术术语语结点结点(ji din)(ji din)的度：结点的度：结点(ji din)(ji din)所拥有的子树的所拥有的子树的个数。个数。树的度：树中各结点树的度：树中各结点(ji din)(ji din)度的最大值。度的最大值。5.1 树树的的逻逻辑辑(lu j)结构结构CGBDEFKLHMIJA第4页/共202页第五页，共202页。5.1 树树的的逻逻辑辑(lu j)结构结构叶子结点叶子结点(ji din)(ji din)：度为：度为0 0的结点的结点(ji
4、din)(ji din)，也称为终，也称为终端结点端结点(ji din)(ji din)。分支结点分支结点(ji din)(ji din)：度不为：度不为0 0的结点的结点(ji din)(ji din)，也称为，也称为非终端结点非终端结点(ji din)(ji din)。CGBDEFKLHMIJA树的基本树的基本(jbn)术术语语第5页/共202页第六页，共202页。孩子、双亲孩子、双亲(shungqn)：树中某结点子树的根结点称为这个：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点的孩子结点，这个结点称为它孩子结点的双亲(shungqn)结点；结点；兄弟：具
5、有同一个双亲兄弟：具有同一个双亲(shungqn)的孩子结点互称为兄弟。的孩子结点互称为兄弟。5.1 树树的的逻逻辑辑(lu j)结构结构CGBDEFKLHMIJA树的基本树的基本(jbn)术语术语第6页/共202页第七页，共202页。路径：如果树的结点路径：如果树的结点(ji din)序列序列n1,n2,nk有如下关系：结点有如下关系：结点(ji din)ni是是ni+1的双亲（的双亲（1=ik），则把），则把n1,n2,nk称为一条由称为一条由n1至至nk的路径；路径上经过的边的个数称为路径长度。的路径；路径上经过的边的个数称为路径长度。CGBDEFKLHMIJA5.1 树树的的逻逻辑辑(
6、lu j)结构结构树的基本树的基本(jbn)术语术语第7页/共202页第八页，共202页。祖先、子孙：在树中，如果有一条路径从结点祖先、子孙：在树中，如果有一条路径从结点(ji(ji din)xdin)x到结点到结点(ji din)y(ji din)y，那么，那么x x就称为就称为y y的祖先，的祖先，而而y y称为称为x x的子孙。的子孙。5.1 树树的的逻逻辑辑(lu j)结构结构CGBDEFKLHMIJA树的基本树的基本(jbn)术术语语第8页/共202页第九页，共202页。结点所在层数：根结点的层数为结点所在层数：根结点的层数为1 1；对其余任何结点，若某结点；对其余任何结点，若某结点
7、在第在第k k层，则其孩子层，则其孩子(hi zi)(hi zi)结点在第结点在第k+1k+1层。层。树的深度：树中所有结点的最大层数，也称高度。树的深度：树中所有结点的最大层数，也称高度。1 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJC5.1 树树的的逻逻辑辑(lu j)结构结构树的基本树的基本(jbn)术语术语第9页/共202页第十页，共202页。CBDEFKLHJA71234568910层序编号：将树中结点按照从上层层序编号：将树中结点按照从上层(shngcng)(shngcng)到下层、到下层、同层从左到右的次序依次给他们编以从同层从左到右的次序依次给他们编以从1
8、1开始的连续自然开始的连续自然数。数。5.1 树树的的逻逻辑辑(lu j)结构结构树的基本树的基本(jbn)术语术语第10页/共202页第十一页，共202页。有序树、无序树：如果一棵树中结点的各子树从左到有序树、无序树：如果一棵树中结点的各子树从左到右是有次序右是有次序(cx)(cx)的，称这棵树为有序树；反之，称的，称这棵树为有序树；反之，称为无序树。为无序树。数据结构数据结构(sh j ji u)(sh j ji u)中讨论的中讨论的一般都是有序树一般都是有序树 5.1 树树的的逻逻辑辑(lu j)结构结构树的基本术语树的基本术语ACBGFEDACBGFED第11页/共202页第十二页，共
9、202页。CBDEFKLHJ森林：森林：m(m0)棵互不相交棵互不相交(xingjio)的树的集合。的树的集合。5.1 树树的的逻逻辑辑(lu j)结构结构树的基本树的基本(jbn)术语术语A第12页/共202页第十三页，共202页。同同构构：对对两两棵棵树树，若若通通过过对对结结点点(ji din)适适当当地地重重命命名名，就就可可以以使使这这两两棵棵树树完完全全相相等等（结结点点(ji din)对对应应相相等等，结结点点(ji din)对应关系也相等），则称这两棵树同构。对应关系也相等），则称这两棵树同构。5.1 树树的的逻逻辑辑(lu j)结构结构树的基本树的基本(jbn)术语术语ACB
10、GFEDDAECFBG第13页/共202页第十四页，共202页。树结构树结构(jigu)和线性结构和线性结构(jigu)的比较的比较线性结构线性结构线性结构线性结构(jigu)(jigu)树结构树结构树结构树结构第第一一个数据元素个数据元素根结点（只有根结点（只有一一个）个）无前驱无前驱(qinq)无双亲无双亲最后最后一一个数据元素个数据元素叶子结点叶子结点(可以有可以有多多个个)无后继无后继无孩子无孩子其它数据元素其它数据元素其它结点其它结点一个前驱一个前驱,一个后继一个后继一个双亲一个双亲,多个孩子多个孩子一对一一对一一对一一对一 一对多一对多一对多一对多5.1 树的逻辑结构树的逻辑结构第
11、14页/共202页第十五页，共202页。树的遍历树的遍历(bin l)(bin l)操作操作 树的遍历：从根结点出发，按照某种次序访问树的遍历：从根结点出发，按照某种次序访问(fngwn)树中所有结树中所有结点，使得每个结点被访问点，使得每个结点被访问(fngwn)一次且仅被访问一次且仅被访问(fngwn)一次。一次。如何理解如何理解访问访问?抽象操作，可以抽象操作，可以(ky)是对结点进行的各种处理，这里简化为输出结点是对结点进行的各种处理，这里简化为输出结点的数据。的数据。如何理解如何理解次序次序?树树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三通常有前序（根）遍历、后序（根）遍
12、历和层序（次）遍历三种方式。种方式。5.1 树的逻辑结构树的逻辑结构树结构（非线性结构）树结构（非线性结构）线性结构。线性结构。遍历的实质遍历的实质?第15页/共202页第十六页，共202页。前序遍历前序遍历(bin l)(bin l)树树的的前前序序遍遍历历操操作作定定义义(dngy)为：为：若树为空，则空操作返回；否则若树为空，则空操作返回；否则 访问根结点；访问根结点；按按照照从从左左到到右右的的顺顺序序前前序序遍遍历历根结点的每一棵子树。根结点的每一棵子树。5.1 树树的的逻逻辑辑(lu j)结构结构前序遍历序列：前序遍历序列：A B D E H I F C GACBGFEDHI第16
13、页/共202页第十七页，共202页。后序后序(hu x)(hu x)遍历遍历 树的后序遍历操作定义为：树的后序遍历操作定义为：若树为空，则空操作返回；否则若树为空，则空操作返回；否则 按按照照从从左左到到右右的的顺顺序序后后序序遍遍历历根结点根结点(ji din)的每一棵子树；的每一棵子树；访问根结点访问根结点(ji din)。5.1 树树的的逻逻辑辑(lu j)结构结构后序遍历序列：后序遍历序列：D H I E F B G C AACBGFEDHI第17页/共202页第十八页，共202页。层序遍历层序遍历(bin l)(bin l)树的层序遍历树的层序遍历(bin l)操作定义为：操作定义为
14、：从从树树的的第第一一层层（即即根根结结点点）开开始始，自自上上而而下下逐逐层层遍遍历历(bin l)，在在同同一一层层中中，按按从从左左到到右右的的顺顺序序对对结结点点逐逐个个访访问。问。5.1 树树的的逻逻辑辑(lu j)结构结构层序遍历序列：层序遍历序列：A B C D E F G H IACBGFEDHI第18页/共202页第十九页，共202页。5.2 树树的的存存储储(cn ch)结构结构实现树的存储结构，关键是什么实现树的存储结构，关键是什么?树中结点之间的逻辑关系是什么树中结点之间的逻辑关系是什么?一对多的关系一对多的关系存储结构存储结构(jigu)的关键：如何表示结点的双亲和孩
15、子的关键：如何表示结点的双亲和孩子如何表示如何表示(biosh)树中结点之间的逻辑关系。树中结点之间的逻辑关系。第19页/共202页第二十页，共202页。双亲双亲双亲双亲(shungqn)(shungqn)表示法表示法表示法表示法基本思想：基本思想：用一维数组来存储树的各个结点（一般按层序存储），用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素数组中的一个元素(yun s)对应树中的一个结点，对应树中的一个结点，每个结点记录两类信息：结点的数据信息以及该结点的双每个结点记录两类信息：结点的数据信息以及该结点的双亲在数组中的下标。亲在数组中的下标。5.2 树树的的存存储储(cn
16、ch)结构结构 data parentdata：存储树中结点的数据信息存储树中结点的数据信息parent：存储该结点的双亲在数组中的下标存储该结点的双亲在数组中的下标第20页/共202页第二十一页，共202页。template struct PNode T data;/数据域数据域 int parent;/指针域，双亲指针域，双亲(shungqn)在数组中的下标在数组中的下标;data parent5.2 树树的的存存储储(cn ch)结构结构树的双亲树的双亲(shungqn)(shungqn)表示法实质上是一个静态表示法实质上是一个静态链表。链表。双亲表示法中结点数据类型的定义双亲表示法中结
17、点数据类型的定义双亲表示法中结点数据类型的定义双亲表示法中结点数据类型的定义第21页/共202页第二十二页，共202页。下下标标(xi bio)data parent012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 5.2 树树的的存存储储(cn ch)结构结构如何查找如何查找双亲双亲结点？时间性能？结点？时间性能？双亲双亲双亲双亲(shungqn)(shungqn)表示法表示法表示法表示法ACBHFEDGI第22页/共202页第二十三页，共202页。5.2 树树的的存存储储(cn ch)结构结构双亲双亲双亲双亲(shungqn)(shungqn)表
18、示法表示法表示法表示法ACBHFEDGI如何查找如何查找孩子孩子结点？时间性能？结点？时间性能？下下标标(xi bio)data parentfirstchild 1 3 6-1 8-1-1-1-1012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 第23页/共202页第二十四页，共202页。下下标标(xi bio)data parent rightsib-1 2-1 4 5-17-1-15.2 树树的的存存储储(cn ch)结构结构双亲双亲双亲双亲(shungqn)(shungqn)表示法表示法表示法表示法012345678 A -1 B 0 C 0
19、 D 1 E 1 F 1 G 2 H 2 I 4 ACBHFEDGI如何查找如何查找兄弟兄弟结点？时间性能？结点？时间性能？第24页/共202页第二十五页，共202页。链表中的每个结点包括一个数据域和多个链表中的每个结点包括一个数据域和多个(du)指针域，指针域，每个指针域指向该结点的一个孩子结点。每个指针域指向该结点的一个孩子结点。如何确定链表中的结点结构？如何确定链表中的结点结构？5.2 树树的的存存储储(cn ch)结构结构孩子孩子(hi zi)表示法表示法-多重链表表示多重链表表示法法方案一：方案一：指针域的个数等于树的度指针域的个数等于树的度data child1 child2 ch
20、ildd其中：其中：data：数据域，存放该结点的数据信息；数据域，存放该结点的数据信息；child1childd：指针域，指向该结点的孩子。指针域，指向该结点的孩子。第25页/共202页第二十六页，共202页。5.2 树树的的存存储储(cn ch)结构结构缺缺点点(qudin)：浪浪费空间费空间ACBHFEDGIABCDEFGHI 第26页/共202页第二十七页，共202页。链表中的每个结点包括一个数据域和多个链表中的每个结点包括一个数据域和多个(du)指针域，每指针域，每个指针域指向该结点的一个孩子结点。个指针域指向该结点的一个孩子结点。如何确定链表中的结点结构？如何确定链表中的结点结构？
21、5.2 树树的的存存储储(cn ch)结构结构方案二：方案二：指针指针(zhzhn)域的个数等于该结点的度域的个数等于该结点的度 data degree child1 child2 childd其中：其中：data：数据域，存放该结点的数据信息；数据域，存放该结点的数据信息；degree：度域，存放该结点的度；度域，存放该结点的度；child1childd：指针域，指向该结点的孩子。指针域，指向该结点的孩子。孩子表示法孩子表示法-多重链表表示法多重链表表示法第27页/共202页第二十八页，共202页。5.2 树树的的存存储储(cn ch)结构结构缺缺点点：结结点点(ji din)结结构构不一致
22、不一致ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0第28页/共202页第二十九页，共202页。基本思想：基本思想：把每个结点的孩子排列把每个结点的孩子排列(pili)起来，看成是一个线性表，且以单链表存起来，看成是一个线性表，且以单链表存储，则储，则n个结点共有个结点共有 n 个孩子链表。个孩子链表。这这 n 个单链表共有个单链表共有 n 个头指针，这个头指针，这 n 个头指针又组成了一个线性表。个头指针又组成了一个线性表。为了便于进行查找采用顺序存储。为了便于进行查找采用顺序存储。最后，将存放最后，将存放 n 个头指针的数组和存放个头指针的数组和存放n个结点的数组
23、结合起来，构成孩个结点的数组结合起来，构成孩子链表的表头数组。子链表的表头数组。5.2 树树的的存存储储(cn ch)结构结构特点特点(tdin)：将每个结点的所有孩子放在一起，构成线性表。：将每个结点的所有孩子放在一起，构成线性表。孩子表示法孩子表示法-孩子链表表示法孩子链表表示法第29页/共202页第三十页，共202页。ACBHFEDGI012345678下标下标(xi bio)data firstchild A B C D E F G H I 5.2 树树的的存存储储(cn ch)结构结构12 345 7 68 第30页/共202页第三十一页，共202页。child next孩子结点孩子
24、结点struct CTNode int child;CTNode*next;5.2 树树的的存存储储(cn ch)结构结构template struct CBNode T data;CTNode*firstchild;孩子孩子(hi zi)链表表示法链表表示法Data firstchild表头结点表头结点第31页/共202页第三十二页，共202页。ACBHFEDGI012345678下标下标(xi bio)data firstchild A B C D E F G H I 5.2 树树的的存存储储(cn ch)结构结构如如何何查查找找孩孩子子结结点？点？12 345 7 68 第32页/共20
25、2页第三十三页，共202页。ACBHFEDGI012345678下标下标(xi bio)data firstchild A B C D E F G H I 5.2 树树的的存存储储(cn ch)结构结构12 345 7 68 如如何何查查找找双双亲亲结点？结点？第33页/共202页第三十四页，共202页。ACBHFEDGI012345678下标下标(xi bio)data firstchild A B C D E F G H I 5.2 树树的的存存储储(cn ch)结构结构12 345 7 68 如如何何查查找找兄兄弟弟结点？结点？第34页/共202页第三十五页，共202页。孩子孩子孩子孩子
26、(hi zi)(hi zi)兄弟表示法兄弟表示法兄弟表示法兄弟表示法5.2 树树的的存存储储(cn ch)结构结构ACBHFEDGI某结点的第一个孩子是惟一某结点的第一个孩子是惟一(wiy)的的某结点的右兄弟是惟一某结点的右兄弟是惟一(wiy)的的设置两个分别指向该结点的设置两个分别指向该结点的第一个孩子和右兄第一个孩子和右兄弟的指针弟的指针 第35页/共202页第三十六页，共202页。template struct TNode T data;TNode *firstchild,*rightsib;5.2 树树的的存存储储(cn ch)结构结构结点结点(ji din)结构结构firstchil
27、d data rightsibdata：数据域，存储该结点的数据信息；：数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子：指针域，指向该结点第一个孩子(hi zi)；rightsib：指针域，指向该结点的右兄弟结点。：指针域，指向该结点的右兄弟结点。孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法第36页/共202页第三十七页，共202页。5.2 树树的的存存储储(cn ch)结构结构孩子孩子孩子孩子(hi zi)(hi zi)兄弟表示法兄弟表示法兄弟表示法兄弟表示法ACBHFEDGI A B C D E F G H I如如何何查查找找兄兄弟弟结结点点？
28、第37页/共202页第三十八页，共202页。5.2 树树的的存存储储(cn ch)结构结构孩子孩子孩子孩子(hi zi)(hi zi)兄弟表示法兄弟表示法兄弟表示法兄弟表示法ACBHFEDGI A B C D E F G H I如如何何查查找找孩孩子子结结点点？第38页/共202页第三十九页，共202页。树的存储树的存储(cn ch)结构小结结构小结n n顺序存储：本质上是静态指针顺序存储：本质上是静态指针顺序存储：本质上是静态指针顺序存储：本质上是静态指针n n双亲表示法双亲表示法双亲表示法双亲表示法n n链式存储：链式存储：链式存储：链式存储：n n多重链表示法多重链表示法多重链表示法多重
29、链表示法n n孩子孩子孩子孩子(hi zi)(hi zi)链表表示法链表表示法链表表示法链表表示法n n孩子孩子孩子孩子(hi zi)(hi zi)兄弟表示法兄弟表示法兄弟表示法兄弟表示法第39页/共202页第四十页，共202页。二叉树的定义二叉树的定义二叉树的定义二叉树的定义(dngy)(dngy)(dngy)(dngy)二叉树是二叉树是n（n0）个结点的有限集合，该集合或者为空集）个结点的有限集合，该集合或者为空集(kn j)（称为空二叉树），或者由一个根结点和两棵互不相交的、分别（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。称为根结点的左
30、子树和右子树的二叉树组成。5.3 二二叉叉树树的的逻逻辑辑(lu j)结结构构结构简单，适合于计算机处理结构简单，适合于计算机处理结构简单，适合于计算机处理结构简单，适合于计算机处理问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。题。题。题。研究二叉树的意义？研究二叉树的意义？第40页/共202页第四十一页，共202页。二叉树的特点二叉树的特点(tdin)：每个结点最多有两棵子树；每个结点最多有两棵子树；二叉树是有序
31、的，其次序不能任二叉树是有序的，其次序不能任意意(rny)颠倒。颠倒。5.3 二二叉叉树树的的逻逻辑辑(lu j)结结构构注意：二叉树和树是两种树结构。注意：二叉树和树是两种树结构。ABCDEFGABAB第41页/共202页第四十二页，共202页。二叉树的基本二叉树的基本(jbn)形态形态空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子根结点同时有左右子树树5.3 二二叉叉树树的的逻逻辑辑(lu j)结构结构第42页/共202页第四十三页，共202页。5.3 二二叉叉树
32、树的的逻逻辑辑(lu j)结构结构具有具有3 3个结点个结点(ji din)(ji din)的树和具有的树和具有3 3个结点个结点(ji din)(ji din)的二叉树的形态的二叉树的形态v二叉树和树是两种树结构。二叉树和树是两种树结构。第43页/共202页第四十四页，共202页。特殊特殊(tsh)的二叉树的二叉树斜树斜树1.所有结点所有结点(ji din)都只有左子树都只有左子树的二叉树称为左斜树；的二叉树称为左斜树；2.所有结点所有结点(ji din)都只有右子树都只有右子树的二叉树称为右斜树；的二叉树称为右斜树；斜树。斜树。1.在斜树中，每一层只有在斜树中，每一层只有(zhyu)一个结
33、点；一个结点；2.斜树的结点个数与其深度相同。斜树的结点个数与其深度相同。5.3 二叉树的逻辑结构二叉树的逻辑结构斜树的特点：斜树的特点：ABCABC第44页/共202页第四十五页，共202页。满二叉树满二叉树在一棵二叉树中，如果所有分支在一棵二叉树中，如果所有分支结点结点(ji din)都存在左子树和右都存在左子树和右子树，并且所有叶子都在同一层子树，并且所有叶子都在同一层上。上。满二叉树的特点满二叉树的特点(tdin)：叶子叶子(y zi)只能出现在最下一层；只能出现在最下一层；只有度为只有度为0和度为和度为2的结点。的结点。5.3 二叉树的逻辑结构二叉树的逻辑结构特殊的二叉树特殊的二叉树
34、A15234678910BCDEFGHIJKLM NO1112 13 14 15第45页/共202页第四十六页，共202页。满二叉树满二叉树5.3 二二叉叉树树的的逻逻辑辑(lu j)结结构构不是满二叉树，虽然不是满二叉树，虽然所有分支结点都有左所有分支结点都有左右右(zuyu)子树，子树，但叶子不在同一层上。但叶子不在同一层上。满二叉树在同样深度满二叉树在同样深度(shnd)的二叉树中结点个数最多的二叉树中结点个数最多满二叉树在同样深度满二叉树在同样深度(shnd)的二叉树中叶子结点个数最多的二叉树中叶子结点个数最多A1523467BCDEFGLM89特殊的二叉树特殊的二叉树第46页/共20
35、2页第四十七页，共202页。完全二叉树完全二叉树对一棵具有对一棵具有(jyu)n个结点个结点的二叉树按层序编号，如果的二叉树按层序编号，如果编号为编号为i（1in）的结点与同）的结点与同样深度的满二叉树中编号为样深度的满二叉树中编号为i的结点在二叉树中的位置完的结点在二叉树中的位置完全相同。全相同。5.3 二二叉叉树树的的逻逻辑辑(lu j)结构结构特殊特殊(tsh)的二叉树的二叉树A15234678910BCDEFGHIJKLM NO1112 13 14 15A15234678910BCDEFGHIJ第47页/共202页第四十八页，共202页。在满二叉树中，从最后一在满二叉树中，从最后一个个
36、(y)结点开始，连续结点开始，连续去掉任意个结点，即是一去掉任意个结点，即是一棵完全二叉树。棵完全二叉树。5.3 二二叉叉树树的的逻逻辑辑(lu j)结构结构A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ不是不是(b shi)完全二叉完全二叉树，结点树，结点10与满二叉树与满二叉树中的结点中的结点10不是不是(b shi)同一个结点同一个结点特殊的二叉树特殊的二叉树第48页/共202页第四十九页，共202页。1.叶子结点只能叶子结点只能(zh nn)出现出现在最下两层，且最下层的叶子结在最下两层，且最下层的叶子结点都集中在二叉
37、树的左部；点都集中在二叉树的左部；2.完全二叉树中如果有度为完全二叉树中如果有度为1的的结点，只可能有一个，且该结点结点，只可能有一个，且该结点只有左孩子。只有左孩子。3.深度为深度为k的完全二叉树在的完全二叉树在k-1层层上一定是满二叉树。上一定是满二叉树。完全完全(wnqun)二叉树的二叉树的特点特点5.3 二二叉叉树树的的逻逻辑辑(lu j)结结构构特殊的二叉树特殊的二叉树A15234678910BCDEFGHIJ第49页/共202页第五十页，共202页。二叉树的基本二叉树的基本二叉树的基本二叉树的基本(jbn)(jbn)(jbn)(jbn)性质性质性质性质 性质性质(xngzh)5-1
38、 二叉树的第二叉树的第i层上最多有层上最多有2i-1个结点个结点（i1）。）。证明：当证明：当i=1时，第时，第1层只有一个根结点，而层只有一个根结点，而 2i-1=20=1，结论显然成立。，结论显然成立。假定假定i=k（1ki）时结论成立，即第）时结论成立，即第k层上至多层上至多(zhdu)有有2k-1个结点，个结点，则则 i=k+1时，因为第时，因为第k+1层上的结点是第层上的结点是第k层上结点的孩子，而层上结点的孩子，而二叉树中每个结点最多有二叉树中每个结点最多有2个孩子，故在第个孩子，故在第k+1层上最大结点个层上最大结点个数为第数为第k层上的最大结点个数的二倍，即层上的最大结点个数的
39、二倍，即22k-12k。结论成。结论成立。立。5.3 二叉树的逻辑结构二叉树的逻辑结构第50页/共202页第五十一页，共202页。性质性质5-2 一棵深度一棵深度(shnd)为为k的二叉树中，最多有的二叉树中，最多有2k-1个结点，个结点，最少有最少有k个结点。个结点。证明：由性质证明：由性质1 1可知，深度为可知，深度为k k的二叉树中结点的二叉树中结点(ji din)(ji din)个数最多个数最多=2k-1=2k-1；每一层至少要有一个结点每一层至少要有一个结点(ji din)(ji din)，因此深度为，因此深度为k k的二叉树，的二叉树，至少有至少有k k个结点个结点(ji din)
40、(ji din)。5.3 二二叉叉树树的的逻逻辑辑(lu j)结构结构深度为深度为k且具有且具有2k-1个结点的二叉树个结点的二叉树一定是一定是满二叉树，满二叉树，深度为深度为k且具有且具有k个结点的二叉树个结点的二叉树不一定不一定是斜树。是斜树。二叉树的基本性质二叉树的基本性质二叉树的基本性质二叉树的基本性质 第51页/共202页第五十二页，共202页。性质性质(xngzh)5-3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为，度为2的结点数为的结点数为n2，则有，则有:n0n21。证明证明(zhngmng):设设n为二叉树的结点总数，为二叉树的结点总数，n1为
41、二叉树中度为为二叉树中度为1的结的结点数，则有：点数，则有：nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为于这些分枝是由度为1和度为和度为2的结点射出的，一个度为的结点射出的，一个度为1的结点射出一的结点射出一个分枝，一个度为个分枝，一个度为2的结点射出两个分枝，所以有：的结点射出两个分枝，所以有：nn12n21因此可以得到：因此可以得到：n0n21。5.3 二二叉叉树树的的逻逻辑辑(lu j)结结构构二叉树的基本性质二叉树的基本性质二叉树的基本性质二叉树的基本性质 第52页/共202页
42、第五十三页，共202页。5.3 二二叉叉树树的的逻逻辑辑(lu j)结结构构在有在有n个结点的满二叉树中，有多少个叶子结点？个结点的满二叉树中，有多少个叶子结点？因为在满二叉树中没有度为因为在满二叉树中没有度为1的结点，只有度为的结点，只有度为0的叶子结点的叶子结点和度为和度为2的分支结点，所以，的分支结点，所以，n n0+n2n0n2+1 即叶子结点即叶子结点n0（n+1）/2 二叉树的基本二叉树的基本二叉树的基本二叉树的基本(jbn)(jbn)(jbn)(jbn)性性性性质质质质 性质性质5-3 在一棵二叉树中，如果在一棵二叉树中，如果(rgu)叶子结点数为叶子结点数为n0，度为，度为2的
43、的结点数为结点数为n2，则有，则有:n0n21。第53页/共202页第五十四页，共202页。性质性质(xngzh)5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。5.3 二二叉叉树树的的逻逻辑辑(lu j)结构结构证证明明：假假设设具具有有n个个结结点点的的完完全全二二叉叉树树的的深深度度为为k，根根据据(gnj)完完全全二二叉叉树树的的定定义义和和性性质质2，有有下下式式成成立立 2k-1 n 2k 2k-1-12k-12k-1第第k-1层层第第k层层最少结点数最少结点数最多结点数最多结点数完全二叉树的基本性质完全二叉树的基本性质完全二叉树的基本性质
44、完全二叉树的基本性质 第54页/共202页第五十五页，共202页。5.3 二二叉叉树树的的逻逻辑辑(lu j)结结构构证证明明：假假设设具具有有n个个结结点点的的完完全全二二叉叉树树的的深深度度为为k，根根据据完完全全二二叉叉树的定义树的定义(dngy)和性质和性质2，有下式成立，有下式成立 2k-1 n 2k完全完全完全完全(wnqun)(wnqun)(wnqun)(wnqun)二叉树的基二叉树的基二叉树的基二叉树的基本性质本性质本性质本性质 性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。对不等式取对数，有：对不等式取对数，有：k-1log
45、2nk即：即：log2nklog2n+1由于由于k是整数，故必有是整数，故必有k log2n+1。第55页/共202页第五十六页，共202页。性质性质5-5 对一棵具有对一棵具有n个结点的完全个结点的完全(wnqun)二叉树中从二叉树中从1开始按层序编开始按层序编号，则对于任意的序号为号，则对于任意的序号为i（1in）的结点（简称为结点）的结点（简称为结点i），有：），有：（1）如果）如果i1，则结点，则结点i的双亲结点的序号为的双亲结点的序号为 i/2；如果；如果i1，则结点，则结点i是是根结点，无双亲结点。根结点，无双亲结点。(2)如果如果2in，则结点，则结点i的左孩子的序号为的左孩子的
46、序号为2i；如果如果2in，则结点，则结点i无左孩子。无左孩子。(3)如果如果2i1n，则结点，则结点i的右孩子的序号为的右孩子的序号为2i1；如果；如果2i1n，则结，则结点点 i无右孩子。无右孩子。5.3 二二叉叉树树的的逻逻辑辑(lu j)结结构构完全完全完全完全(wnqun)(wnqun)(wnqun)(wnqun)二叉树的基二叉树的基二叉树的基二叉树的基本性质本性质本性质本性质 第56页/共202页第五十七页，共202页。18910456723对一棵具有对一棵具有n个结点的完全个结点的完全(wnqun)二叉树中从二叉树中从1开开始按层序编号，则始按层序编号，则 结点结点i的双亲结点为
47、的双亲结点为 i/2；结点结点i的左孩子为的左孩子为2i；结点结点i的右孩子为的右孩子为2i1。5.3 二二叉叉树树的的逻逻辑辑(lu j)结构结构性质性质5表明，在完全表明，在完全(wnqun)二叉树中，结点的层二叉树中，结点的层序编号反映了结点之间的逻辑关系。序编号反映了结点之间的逻辑关系。第57页/共202页第五十八页，共202页。二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历(bin l)(bin l)(bin l)(bin l)操作操作操作操作 二叉树的遍历是指从根结点出发二叉树的遍历是指从根结点出发(chf)，按照某种次序访问二，按照某种次序访问二叉树中的所有结点，使得每个结点被
48、访问一次且仅被访问一次。叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。二叉树遍历二叉树遍历(bin l)操作的目的操作的目的？非线性结构线性化非线性结构线性化5.3 二叉树的逻辑结构二叉树的逻辑结构抽象操作，抽象操作，可以是对结点进行的各种处理，可以是对结点进行的各种处理，这里这里简化为输出结点的数据。简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 第58页/共202页第五十九页，共202页。二叉树的遍历二叉树的遍历(bin l)(bin l)方式：方式：DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLD RLD 如果
49、限定如果限定(xindng)先左后右，则二叉树遍历方式有三种：先左后右，则二叉树遍历方式有三种：前序：前序：DLR中序：中序：LDR后序：后序：LRD层序遍历：按二叉树的层序编号的次序访问层序遍历：按二叉树的层序编号的次序访问(fngwn)(fngwn)各结点。各结点。5.3 二叉树的逻辑结构二叉树的逻辑结构考虑二叉树的组成：考虑二叉树的组成：根结点根结点D左子树左子树L右子树右子树R二二叉叉树树第59页/共202页第六十页，共202页。前序（根）遍历前序（根）遍历(bin l)(bin l)若二叉树为空，则空操作返回；否则：若二叉树为空，则空操作返回；否则：访问根结点；访问根结点；前序遍历前
50、序遍历(bin l)(bin l)根结点的左子树；根结点的左子树；前序遍历前序遍历(bin l)(bin l)根结点的右子树。根结点的右子树。5.3 二二叉叉树树的的逻逻辑辑(lu j)结构结构前前序序遍遍历历(bin l)序序列列：A B D G C E FABCDEFG二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 第60页/共202页第六十一页，共202页。中序（根）遍历中序（根）遍历(bin l)若二叉树为空，则空操作返回；否则：若二叉树为空，则空操作返回；否则：中序遍历中序遍历(bin l)根结点的左子树；根结点的左子树；访问根结点；访问根结点；中序遍历中序遍历(b