还剩7页未读,继续阅读
文本内容:
全国计算机等级考试二级公共基础之树与二叉树
1.6树与二叉树
1.
6.1树的基本概念树是一种简单的非线性结构在树这种结构中,所有元素之间的关系具有明显的层次关系用图形表示树这种数据结构时,就象自然界中的倒长的树,这种结构就用“树”来命名如图在树结构中,每个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称为树的根(如R)在树结构中,每一个结点可以有多个后件,它们都称为该结点的子结点没有后件的结点称为叶子结点(如W,Z,A,L,B,N,O,T,H,X)在树结构中,一个结点拥有的后件个数称为结点的度(如R的度为4,KPQDEC结点度均为2)树的结点是层次结构,一般按如下原则分层根结点在第1层;同一个层所有结点的所有子结点都在下一层树的最大层次称为树的深度如上图中的树深度为4R结点有4棵子树,KPQDEC结占各有两棵子树;叶子没有子树在计算机中,可以用树结构表示算术运算在算术运算中,一个运算符可以有若干个运算对象如取正(+)与取负(-)运算符只有一个运算对象,称为单目运算符;加(+)、减(-)、乘(*)、除(/)、乘幂(**)有两个运算对象,称为双目运算符;三元函数fxyz为f函数运算符,有三个运算对象,称为三目运算符多元函数有多个运算对象称多目运算符用树表示算术表达式原则是1表达式中的每一个运算符在树中对应一个结点,称为运算符结点2运算符的每一个运算对象在树中为该运算结点的子树在树中的顺序从左到右3运算对象中的单变量均为叶子结点根据上面原则,可将表达式a*b+c/d+c*h-g*f表示如下的树树在计算机中通常用多重链表表示,多重链表的每个结点描述了树中对应结点的信息,每个结点中的链域(指针域)个数随树中该结点的度而定
1.
6.2二叉树及其基本性质
1.什么是二叉树二叉树是很有用的非线性结构它与树结构很相似,树结构的所有术语都可用到二叉树这种结构上二叉树具有以下两个特点
(1)非空两叉树只有一个根结点
(2)每个结点最多有两棵子树,且分别称该结点的左子树与右子树也就是说,在二叉树中,每一个结点的度最大为2,而且所有子树也均为二叉树二叉树中的每一个结点可以有左子树没有右子树,也可以有右子树没有左子树,甚至左右子树都没有
2.二叉树的基本性质二叉树性质有性质1在二叉树的第K层上,最多有2k-1k=1个结点性质2深度为m的二叉树最多有2m-1个结点性质3在任意一棵二叉树中,度为0的结点(即叶子结点)总比度为2的结点多一个性质4具有n个结占的二叉树,其深度至少为[log2n]+1其中[log2n]表示取log2n的整数部分
3.满二叉树与完全二叉树
(1)满二叉树满两叉树是除了最后一层外,每一层上的所有结点都有两个子结点即在满二叉树中,每一层上的结点数都达到最大值在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点如图深度为2的满二叉树深度为3的满二叉树深度为4的满二叉树
(2)完全二叉树完全二叉树除最后一层外,每一层上的结点数均达到最大数;最后一层只缺少右边的若干结点如图深度为3的完全二叉树 深度为4的完全二叉树完全二叉树具有以下两个性质性质5具有n个结点的完全二叉树的深度为[log2n]+1性质6设完全[log2n]+1有n个结点如右图10个结点编号如图如果从根结点开始,按层序用自然数12…n给结点进行编号,则对于编号为kk=12…n的结点有以下结论
(1)若k=1,则该结点为根结点,它没有父结点;若k1,则该结点的父结点编号为INTk/2如结点D的编号K=4,则它的父结点B的编号为2
(2)若2k=n,则编号为k的结点的左子结点编号为2k,否则该结点无左子结点(也无右子结点),如结点D的编号K=4,则8=10,它的左子结点H编号为8
(3)若2k+1=n,则编号为k的结点的右子结点编号为2k+1,否则该结点无右子结点如结点D的编号K=4,则9=10,它的右左子结点H编号为
91.
6.3二叉树的存储结构在计算机中,二叉树通常采用链式存储结构与线性链表类似,用于存储二叉树中各元素的存储结点也由两部分组成数据域与指针域但在二叉树中,由于每一个元素可以有两个后件(即两个子结点),因此,用于存储二叉树的存储结点的指针域有两个一个用于指向结点的左子树结构的存储地址,称为左指针域;另一个用于指向右子树结点的存储地址,称为右指针域由于二叉树的存储结构中每一个存储结点有两个指针域,因此二叉树的链式存储结构也称为二叉链表二叉树存储结构如图二叉树二叉链表的逻辑状态
1.
6.4二叉树的遍历二叉树的遍历是指不重复的访问二叉树中的所有结点由于二叉树是一种非线性结构,因此对二叉树的遍历要比遍历线性表复杂很多在遍历二叉树过程中,当访问到某个结点时,再往下访问可能有两个分支,应访问哪一个分支呢?对于二叉树来说需要访问根结点、左子树所有结点、右子树所有结点,在这三者中,应访问哪一个?也就是说,遍历二叉树实际是要确定访问各结点的顺序以便不重复又不能丢掉访问结点,直到访问到所有结点在遍历二叉树的过程中,一般选遍历左子树,然后再遍历右子树,在先左后右原则下根据访问结点次序,二叉树的遍历分为三种方法方法如下
1.前序遍历(DLR)前序遍历首先访问根结点然后遍历左子树,最后遍历右子树在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树即若二叉树为空则结束返回,否则
(1)访问根结点
(2)前序遍历左子树
(3)前序遍历右子树注意的是遍历左右子树时仍然采用前序遍历方法例如图二叉树,则前序遍历结果是ABDECF
2.中序遍历(LDR)中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树即若二叉树为空则结束返回,否则
(1)中序遍历左子树
(2)访问根结点
(3)中序遍历右子树注意的是遍历左右子树时仍然采用中序遍历方法例如图二叉树,则中序遍历结果是DBEAFC
3.后序遍历(LRD)后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点即若二叉树为空则结束返回,否则
(1)后序遍历左子树,
(2)后序遍历右子树
(3)最后访问根结点注意的是遍历左右子树时仍然采用后序遍历方法例如图二叉树,则中序遍历结果是DEBFCA。