树的基本概念 树是一种简单的非线性结构。在树这种结构中,所有元素之间的关系具有明显的层次关系。用图形 表示树这种数据结构时,就象自然界中的倒长的树,这种结构就用“树”来命名。如图: 在树结构中,每个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点, 简称为树的根(如R)。 在树结构中,每一个结点可以有多个后件,它们都称为该结点的子结点。没有后件的结点称为叶子 结点(如W,Z,A ,L,B,N,O,T,H,X)。 在树结构中,一个结点拥有的后件个数称为结点的度(如R的度为4,KPQDEC结点度均为 2)。 树的结点是层次结构,一般按如下原则分层:根结点在第1层;同一个层所有结点的所有子结点都 在下一层。树的最大层次称为树的深度。如上图中的树深度为4。R结点有4棵子树,KPQDEC结占各有两棵子树;叶子没有子树。 在计算机中,可以用树结构表示算术运算。在算术运算中,一个运算符可以有若干个运算对象。如 取正(+)与取负(-)运算符只有一个运算对象,称为单目运算符;加(+)、减(-)、乘(*)、除(/)、乘幂(**)有两个运算对象,称为双目运算 符;三元函数f(x,y,z)为 f函数运算符,有三个运算对象,称为三目运算符。多元函数有多个运算对象称多目运算符。 用树表示算术表达式原则是: (1)表达式中的每一个运算符在树中对应一个结点,称为运算符结点 (2)运算符的每一个运算对象在树中为该运算结点的子树(在树中的顺序从左到右) (3)运算对象中的单变量均为叶子结点 根据上面原则,可将表达式:a*(b+c/d)+c*h-g*f表示如下的树。 树在计算机中通常用多重链表表示,多重链表的每个结点描述了树中对应结点的信息,每个结点中的链域 (指针域)个数随树中该结点的度而定。 1.6.2 二叉树及其基本性质 1. 什么是二叉树 二叉树是很有用的非线性结构。它与树结构很相似,树结构的所有术语都可用到二叉树这种结构 上。 二叉树具有以下两个特点: (1)非空两叉树只有一个根结点 (2)每个结点最多有两棵子树,且分别称该结点的左子树与右子树。 2. 二叉树的基本性质 二叉树性质有: 性质1:在二叉树的第K层上,最多有2k-1(k>=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 (1)若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/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编号为9 1.6.3 二叉树的存储结构 在计算机中,二叉树通常采用链式存储结构。与线性链表类似,用于存储二叉树中各元素的存储结 点也由两部分组成:数据域与指针域。但在二叉树中,由于每一个元素可以有两个后件(即两个子结点),因此,用于存储二叉树的存储结点的指针域有两个:一个 用于指向结点的左子树结构的存储地址,称为左指针域;另一个用于指向右子树结点的存储地址,称为右指针域。 由于二叉树的存储结构中每一个存储结点有两个指针域,因此二叉树的链式存储结构也称为二叉链 表。二叉树存储结构如图:
二叉树 二叉链表的逻辑状态 1.6.4 二叉树的遍历 二叉树的遍历是指不重复的访问二叉树中的所有结点。 由于二叉树是一种非线性结构,因此对二叉树的遍历要比遍历线性表复杂很多。在遍历二叉树过程 中,当访问到某个结点时,再往下访问可能有两个分支,应访问哪一个分支呢?对于二叉树来说需要访问根结点、左子树所有结点、右子树所有结点,在这三者中, 应访问哪一个?也就是说,遍历二叉树实际是要确定访问各结点的顺序。以便不重复又不能丢掉访问结点,直到访问到所有结点。 在遍历二叉树的过程中,一般选遍历左子树,然后再遍历右子树,在先左后右原则下根据访问结点 次序,二叉树的遍历分为三种方法。方法如下: 1. 前序遍历(DLR) 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根 结点,然后遍历左子树,最后遍历右子树。即: 若二叉树为空则结束返回,否则: (1)访问根结点 (2)前序遍历左子树 (3)前序遍历右子树 注意的是:遍历左右子树时仍然采用前序遍历方法。 例:如图二叉树, 则前序遍历结果是:A B D E C F 2. 中序遍历(LDR) 中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历 左子树,再访问根结点,最后遍历右子树。即: 若二叉树为空则结束返回,否则: (1)中序遍历左子树 (2)访问根结点 (3)中序遍历右子树。 注意的是:遍历左右子树时仍然采用中序遍历方法。 例:如图二叉树, 则中序遍历结果是:D B E A F C 3. 后序遍历(LRD) 后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点。在遍历左、右子树时,仍然先遍历 左子树,然后遍历右子树,最后访问根结点。即: 若二叉树为空则结束返回,否则: (1)后序遍历左子树, (2)后序遍历右子树 (3)最后访问根结点。 注意的是:遍历左右子树时仍然采用后序遍历方法。 例:如图二叉树, 则中序遍历结果是:D E B F C A |
|