第08讲第9章程序设计基础课件.ppt

第九章程序设计基础2020/8/31计算机基础知识第九章,现实中的许多事物的关系并非这样简单,如人类社会的族谱、各种社会组织机构以及城市交通、通讯等,这些事物之间的联系都是非线性的,要用到树形(或图形)这种非线性数据结构。在这类结构中至少存在一个数据元素,有两个或两个以上的直接前驱(或直接后继)元素。树形结构就是一种十分重要的非线性结构,可以用来描述客观世界中广泛存在的层次结构关系,这种结构的特点是:有一个特定的结点称为根结点,它没有前趋,其它结点可以有多个后继,但只有唯一的前驱结点。二叉树是应用最广泛、最有代表性的树型结构。**树结构(除了一个称为根的结点外)每个元素都有且仅有一个直接前趋,有零个或多个直接后继。在树的图形表示中,总是认为在用直线连接起来的两端结点中,上端结点是前趋,下端结点是后继。**具有层次关系的数据都可以用树这种结构来描述。在所有的层次关系中人们最熟悉的是血缘关系,按血缘关系可以很直观地理解树结构中各数据元素结点之间的关系。在树的结构中,每一个结点只有一个前趋,称为父结点;没有前趋的结点只有一个,称为树的根结点,简称为树的根。在树的结构中,每一个结点可以有多个后继,它们都称为该结点的子结点。没有后继的结点称为叶子结点。**(BinaryTree)是个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。二叉树是有序的,即若将其左、右子树颠倒,就成为另一棵不同的二叉树。即使某个结点只有一棵子树,也要区分它是左子树还是右子树。因此二叉树具有五种基本形态,如图所示。****左子树右子树左子树右子树(a)(b)(c)(d)(e)Ф二叉树重要的二个特点:①非空二叉树只有一个根结点;②每一个结点最多有两棵子树,且分别称为结点的左子树与右子树。特别注意:二叉树中的每个结点的子树被明显地分为左子树与右子树。在二叉树中可以只有左子树而没有右子树,也可以只有右子树而没有左子树。⑴结点所拥有的子树的个数称为该结点的度⑵度为0的结点称为叶结点,度不为0的结点称为分支结点⑶树中一个结点的子树的根结点称为这个结点的孩子,这个结点称为它孩子结点的双亲,具有同一个双亲的孩子结点互称为兄弟。**⑷如果一棵树的一串结点n1,n2,…,nk有如下关系:结点ni是ni+1的父结点(1≤i<k),就把n1,n2,…,nk称为一条由n1至nk的路径,这条路径的长度是k-1。如果有一条路径从结点M到结点N,那么M就称为N的祖先,而N称为M的子孙。⑸规定树的根结点的层数为1,其余结点的层数等于它的双亲结点的层数加1,树中所有结点的最大层数称为树的深度,树中各结点度的最大值称为该树的度。⑹在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子结点都在同一层上,这样的一棵二叉树称作满二叉树。**