电脑基础知识第2章基本数据结构及其运算ppt课件

《电脑基础知识第2章基本数据结构及其运算ppt课件》由会员分享，可在线阅读，更多相关《电脑基础知识第2章基本数据结构及其运算ppt课件（45页珍藏版）》请在装配图网上搜索。

1、第第2章章 根本数据构造及其运算根本数据构造及其运算(5)特点：非线性构造，一个直接前驱特点：非线性构造，一个直接前驱(前件前件)，但能够有多个直，但能够有多个直接后继接后继(后件后件)。2.5.1 树的根本概念树的根本概念2.5.2 二叉树及其根本性质二叉树及其根本性质2.5.3 二叉树遍历二叉树遍历一对多或一对多或1:n1:n 树是一类以分支关系定义的层次构造，现实世界中，能用树树是一类以分支关系定义的层次构造，现实世界中，能用树的构造表示的例子：的构造表示的例子：学校的行政关系、书的层次构造、人类的家族血缘关系等。学校的行政关系、书的层次构造、人类的家族血缘关系等。2.5.4 二叉树的存

2、储构造二叉树的存储构造2.5.5 穿线二叉树穿线二叉树2.5.6 表达式的线性化表达式的线性化 树在计算机领域中也有着广泛的运用，例如在编译程序中，树在计算机领域中也有着广泛的运用，例如在编译程序中，用树来表示源程序的语法构造；在数据库系统中，可用树来组用树来表示源程序的语法构造；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描画其执行过程等等。织信息；在分析算法的行为时，可用树来描画其执行过程等等。注注1：过去许多书籍中都定义树为：过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是树的说法，但如今树的定义已修正。树的说法，但如今树的定义已修正。注注2：树的定义具有

3、递归性，即：树的定义具有递归性，即“树中还有树。树中还有树。A只需根的树只需根的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树即子结点的上层结点即子结点的上层结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点孩子之间互称兄弟同一双亲下的同层结点孩子之间互称兄弟即双亲位于同一层的结点但并非同一双亲即双亲位于同一层的结点但并非同一双亲即从根到该结点所经分支的一切结点即从根到该结点所经分支的一切结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJFLK 根根 叶子叶子 森林森林即根结点即根结点(没有前驱没

4、有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)从根到该结点的层数根结点算第一层从根到该结点的层数根结点算第一层即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点也称为内部结点的结点也称为内部结点一切结点度中的最大值一切结点度中的最大值Max各结点的度各结点的度指

5、一切结点中最大的层数指一切结点中最大的层数Max各结点的层次各结点的层次问：右上图中的结点数问：右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4(有几个直接后继就是几度，亦称有几个直接后继就是几度，亦称“次数次数)ABCGEIDHFJFLKABCDEFGHIJKLM结点结点A、D的度：的度：3结点结点B、E的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的子：的子：B,C,D结点结点B的子：的子：E,F结点结点I的父：的父：D结点结点L的父：的父：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结

6、点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点A是结点是结点F，G的祖先的祖先一对多一对多1:n1:n，有多个直接后继如家谱，有多个直接后继如家谱树、目录树等等，但只需一个根结点，树、目录树等等，但只需一个根结点，且子树之间互不相交。且子树之间互不相交。特点：特点：普通树即多叉树的物理构造比较复杂，而普通树即多叉树的物理构造比较复杂，而且运算也很难实现。且运算也很难实现。处理方法：处理方法：为何要重点研讨每结点最多只需两个为何要重点研讨每结点最多只需两个“叉叉 的树？的树？二叉树的构造最简单，规律性最强；二叉树的构造最简单，规律性最强；二叉树在树构造的运用中起

7、着非常重要的作用，由于二叉树在树构造的运用中起着非常重要的作用，由于对二叉树的许多操作算法简单，而任何树都可以对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就处理了树的存储构造与二叉树相互转换，这样就处理了树的存储构造及其运算中存在的复杂性。及其运算中存在的复杂性。1.什么是二叉树什么是二叉树2.二叉树的根本性质二叉树的根本性质 定义：是定义：是nn0个结点的有限集合，或者是个结点的有限集合，或者是n=0，或者，或者是由一个根结点以及两棵互不相交的、分别称为左子树和是由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成右子树的二叉树组成。逻辑构造：一对二逻辑构造

8、：一对二1:2 根本特征根本特征:每个结点最多只需两棵子树不存在度大于每个结点最多只需两棵子树不存在度大于2的结点；的结点；左子树和右子树次序不能颠倒。左子树和右子树次序不能颠倒。根本形状：根本形状：讨论讨论1 1：第：第k k层的结点数最多是多少？层的结点数最多是多少？利用二进制性质可轻利用二进制性质可轻松求出松求出 再提问：第再提问：第i i层上至少有层上至少有 个结点？个结点？1讨论讨论2 2：深度为：深度为m m的二叉树，最多有多少个结点？的二叉树，最多有多少个结点？利用二进制性质可利用二进制性质可轻松求出轻松求出讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数

9、之间有关系吗？的结点数之间有关系吗？AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树完全二叉树完全二叉树ABCGEIDHFJ为何要研讨为何要研讨这两种特殊这两种特殊方式？方式？满二叉树和完全二叉树有什么区别？满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边短少延续假设干个结点。层是满的，但最底层却允许在右边短少延续假设干个结点。满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。t有两种特殊方式的二叉树满二叉树和完全二叉树有两种特殊方式的二

10、叉树满二叉树和完全二叉树1231145891213671014151231145891267101234567123456以下图中为完全二叉树的是？以下图中为完全二叉树的是？可根据归纳法证明。可根据归纳法证明。对于两种特殊方式的二叉树满二叉树和完全二叉树，还对于两种特殊方式的二叉树满二叉树和完全二叉树，还特别具备以下特别具备以下2个性质：个性质：一、顺序存储构造一、顺序存储构造按二叉树的结点按二叉树的结点“自上而自上而下、从左至右编号，用下、从左至右编号，用一组延续的存储单元存储。一组延续的存储单元存储。ABCDEFGHI123456789ABCGEIDHFT0T0普普通不用通不用讨论：不是完

11、全二叉树怎样办？讨论：不是完全二叉树怎样办？答：一概转为完全二叉树！答：一概转为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点，其虚结点，其内容为空。内容为空。12345678916ABECD缺陷：浪费空间；插入、删除不便缺陷：浪费空间；插入、删除不便 二叉树的链式存储二叉树的链式存储 结点定义：结点定义：struct BinTreeNode ElemType data;BinTreeNode*leftChild,*rightChild;这里这里leftChild和和rightChild分别为某一结点指向其左孩子分别为某一结点指向其左孩子和右孩子的指针。对

12、于叶子结点或一个新生成的结点而和右孩子的指针。对于叶子结点或一个新生成的结点而言，其左孩子和右孩子指针都应为空值。言，其左孩子和右孩子指针都应为空值。二叉树的链式存储二叉树的链式存储ABCDE利用这种结点方式存储的树普通称为二叉链表。利用这种结点方式存储的树普通称为二叉链表。从根结点出发，可以访问二叉树的任何结点。为了可以访问从根结点出发，可以访问二叉树的任何结点。为了可以访问二叉树，必需保管指向根结点的指针。这和单链表必需保管二叉树，必需保管指向根结点的指针。这和单链表必需保管头指针的道理一样。头指针的道理一样。二叉树的链式存储构造二叉树的链式存储构造二叉树链式存储举例：二叉树链式存储举例：

13、ABECDAB DCE优点：不浪费空间；插入、删除方便优点：不浪费空间；插入、删除方便 二叉树的常用算法包括：获取根结点指针、判别树能否为二叉树的常用算法包括：获取根结点指针、判别树能否为空、插入或删除结点、插入或删除子树、二叉树遍历等。空、插入或删除结点、插入或删除子树、二叉树遍历等。Traversing Binary Tree遍历定义遍历定义遍历用途遍历用途遍历方法遍历方法指按某条搜索道路遍访每个结点且不反复指按某条搜索道路遍访每个结点且不反复又称周游。又称周游。它是树构造插入、删除、修正、查找和排它是树构造插入、删除、修正、查找和排序运算的前提，是二叉树一切运算的根底序运算的前提，是二叉

14、树一切运算的根底和中心。和中心。对每个结点的查看通常都是对每个结点的查看通常都是“先左后右先左后右 。遍历规那么遍历规那么二叉树由根、左子树、右子树构成，定义为二叉树由根、左子树、右子树构成，定义为D、L、R以根结点为参照系以根结点为参照系注：注：“先、中、后的意思是指访问的结点先、中、后的意思是指访问的结点D是先于子树出是先于子树出现还是后于子树出现。现还是后于子树出现。v D、L、R的组合定义了六种能够的遍历方案：的组合定义了六种能够的遍历方案：v LDR,LRD,DLR,DRL,RDL,RLDv 假设限定先左后右，那么有三种实现方案：假设限定先左后右，那么有三种实现方案：DLR LDR

15、LRD先序遍历先序遍历 中序遍历中序遍历 后序遍历后序遍历 先序遍历的结果是：先序遍历的结果是：中序遍历的结果是：中序遍历的结果是：后序遍历的结果是：后序遍历的结果是：A B CD E口诀：口诀：DLR先序遍历，即先根再左再右先序遍历，即先根再左再右LDR中序遍历，即先左再根再右中序遍历，即先左再根再右LRD后序遍历，即先左再右再根后序遍历，即先左再右再根AHGDEFBC先序序列：先序序列：ABDGCEFH中序序列：中序序列：DGBAECHF后序序列：后序序列：GDBEHFCA 例：知一棵二叉树的中序序列和后序序列分别是例：知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和和 DECB

16、HGFA，请画出这棵二叉树。，请画出这棵二叉树。分析：分析：由后序遍历特征，根结点必在后序序列尾部即由后序遍历特征，根结点必在后序序列尾部即A；由中序遍历特征，根结点必在其中间，而且其左部必全部由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙即是左子树的子孙即BDCE，其右部必全部是右子树的子孙，其右部必全部是右子树的子孙即即FHG；继而，根据后序中的继而，根据后序中的DECB子树可确定子树可确定B为为A的左孩子，根的左孩子，根据据HGF子串可确定子串可确定F为为A的右孩子；以此类推。的右孩子；以此类推。知中序遍历：知中序遍历：B D C E A F H G知后序遍历：知后序遍

17、历：D E C B H G F AB D C E F H GA D C EBFGHCD EABBACCD C E1先序遍历先序遍历 对一颗非空二叉树进展先序遍历时，首先访问对一颗非空二叉树进展先序遍历时，首先访问根结点，然后按先序遍历方式访问左子树，最后按根结点，然后按先序遍历方式访问左子树，最后按先序遍历方式访问右子树。先序遍历算法如下：先序遍历方式访问右子树。先序遍历算法如下：void BinTree:PreOrder(BinTreeNode*t)if(t)Visit(t);/访问根结点访问根结点 PreOrder(t-leftChild);/遍历左子树遍历左子树 PreOrder(t-r

18、ightChild);/遍历右子树遍历右子树 2中序遍历中序遍历 对一颗非空二叉树进展中序遍历时，首先按对一颗非空二叉树进展中序遍历时，首先按中序遍历方式访问左子树，然后访问根结点，最中序遍历方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。中序遍历算法如后按中序遍历方式访问右子树。中序遍历算法如下：下：void BinTree:InOrder(BinTreeNode*t)if(t)InOrder(t-leftChild);/遍历左子树遍历左子树 Visit(t);/访问根节点访问根节点 InOrder(t-rightChild);/遍历右子树遍历右子树 3后序遍历后序遍历对一颗非

19、空二叉树进展中序遍历时，首先按后对一颗非空二叉树进展中序遍历时，首先按后序遍历方式访问左子树，然后按后序遍历方式访问序遍历方式访问左子树，然后按后序遍历方式访问右子树，最后访问根结点。后序遍历算法如下：右子树，最后访问根结点。后序遍历算法如下：void BinTree:PostOrder(BinTreeNode*t)if(t)PostOrder(t-leftChild);/遍历左子遍历左子树树PostOrder(t-rightChild);/遍历右子遍历右子树树Visit(t);/访问根节点访问根节点 1.从前面的三种遍历算法可以知道：假设将输出语句抹去，从前面的三种遍历算法可以知道：假设将输

20、出语句抹去，从递归的角度看，这三种算法是完全一样的，或者说这三种从递归的角度看，这三种算法是完全一样的，或者说这三种遍历算法的访问途径是一样的，只是访问结点的时机不同。遍历算法的访问途径是一样的，只是访问结点的时机不同。从虚线的出发点到终点的途径从虚线的出发点到终点的途径上，每个结点经过上，每个结点经过3次。次。AFEDCBG第第1次经过时访问，是先序遍历次经过时访问，是先序遍历第第2次经过时访问，是中序遍历次经过时访问，是中序遍历第第3次经过时访问，是后序遍历次经过时访问，是后序遍历2.二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率：时间效率：O(n)/每个结点只访问一

21、次每个结点只访问一次空间效率：空间效率：O(n)/栈占用的最大辅助空栈占用的最大辅助空间间准确值：树深为准确值：树深为k k的递归遍历需求的递归遍历需求k+1k+1个辅助单元个辅助单元u遍历二叉树本质上是对一个非线性构造进展线遍历二叉树本质上是对一个非线性构造进展线性化操作。性化操作。u当以二叉链表作为存储构造时当以二叉链表作为存储构造时,只能找到结点的只能找到结点的左右孩子的信息，而不能直接得到结点在任一左右孩子的信息，而不能直接得到结点在任一序列中的前驱与后继信息，这种信息只需在遍序列中的前驱与后继信息，这种信息只需在遍历的动态过程中才干得到。历的动态过程中才干得到。u为了能保管遍历过程中

22、得到的信息，可为每个为了能保管遍历过程中得到的信息，可为每个结点添加两个指针域结点添加两个指针域fwd和和bkwd，分别指示结，分别指示结点在任一次遍历得到的前驱和后继信息，但这点在任一次遍历得到的前驱和后继信息，但这样做使得构造的存储密度大大降低。样做使得构造的存储密度大大降低。q有有n个结点的二叉链表中有个结点的二叉链表中有n+1个空链域，可利个空链域，可利用这些空链域来存放结点的前驱和后继信息。用这些空链域来存放结点的前驱和后继信息。q规定：假设结点有左子树，那么规定：假设结点有左子树，那么Lchild域指示其域指示其左孩子，否那么令左孩子，否那么令Lchild指示其前驱；假设结点指示其

23、前驱；假设结点有右子树，那么其有右子树，那么其Rchild域指示其右孩子，否域指示其右孩子，否那么令那么令Rchild指示其后继。指示其后继。q为了防止混淆，其结点构造可添加标志域为了防止混淆，其结点构造可添加标志域Lchild LflagdataRflag Rchildv以这种结点构造构成的二叉链表作为二叉树的存储构造以这种结点构造构成的二叉链表作为二叉树的存储构造,叫做线索链表叫做线索链表,其中指向结点前驱与后继的指针叫做线索其中指向结点前驱与后继的指针叫做线索,加上线索的二叉树称之为穿线二叉树线索二叉树。加上线索的二叉树称之为穿线二叉树线索二叉树。v对二叉树以某种次序遍历使其变为线索二叉

24、树的过程称对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。为线索化。abcdfegabcdfeg么它的中序后继是其右子树的么它的中序后继是其右子树的“最左结点。最左结点。abcdefgabcdefgabcdefgabcdefgabcdefghiabcdefghiabcdefghiabcdefghi的连的连线。线。abdecfghiabdecfghiabdecfghiabdecfghi2.5.6 表达式的线性化表达式的线性化1.有序树的二叉树表示有序树的二叉树表示有序树：结点的一切子结点从左到右次序不能颠倒有序树：结点的一切子结点从左到右次序不能颠倒将有序树转化成二叉树的原那么：将有序

25、树转化成二叉树的原那么：(1)有序树有序树T中的结点与二叉树中的结点与二叉树BT中的结点一一对中的结点一一对应；应；(2)有序树有序树T中某个结点中某个结点N的第一个子结点即最左的第一个子结点即最左边的子边的子 结点结点N1，在二叉树，在二叉树BT中为对应结点中为对应结点N的左子结点；的左子结点；(3)有序树有序树T中某个结点中某个结点N的第一个子结点以后的其的第一个子结点以后的其他子结他子结 点，在二叉树点，在二叉树BT中被依次链接成一串中被依次链接成一串起始于起始于N1的右子结点。的右子结点。a*(bc/d)e*hg*f(s，t，xy)2.表达式的线性化波兰表示表达式的线性化波兰表示(1)

26、将表达式用有序树表示，即构造表达式树。将表达式用有序树表示，即构造表达式树。(2)将表达式树化为二叉树。将表达式树化为二叉树。(3)对相应的二叉树进展中序遍历，其遍历序列即为对相应的二叉树进展中序遍历，其遍历序列即为表达式的波兰表示式。表达式的波兰表示式。表达式表达式 a*(bc/d)e*hg*f(s，t，xy)的波兰表示式为的波兰表示式为 a b c d/*e h*g s t x y f*1、定义和性质、定义和性质2、存储构造、存储构造3、遍历、遍历顺序构造顺序构造链式构造链式构造二叉链表二叉链表三叉链表三叉链表1:2，性质有性质有3+2条条中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历第第4节终了节终了1:n相关术语相关术语