全国计算机等级考试二级公共基础之树与二叉树1

1、全国运算机等级考试二级公共基础之树与二叉树1.6 树与二叉树1.6.1 树的基本概念树是一种简洁的非线性结构；在树这种结构中， 全部元素之间的关系具有明显的层次关系；用图形表示树这种数据结构时，就象自然界中的倒长的树，这种结构就用“树”来命名；如图：在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根（如r）；在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点；没有后件的结点称为叶子结点（如w，z， a ， l， b， n， o， t，h， x）；在树结构中，一个结点拥有的后件个数称为结点的度（如 r 的度为 4，kpqdec结点度均为

2、 2）；树的结点是层次结构，一般按如下原就分层：根结点在第1 层；同一个层全部结点的全部子结点都在下一层；树的最大层次称为树的深度 ；如上图中的树深度为 4；r结点有 4 棵子树， kpqde结c 占各有两棵子树；叶子没有子树；在运算机中，可以用树结构表示算术运算；在算术运算中，一个运算符可以 有如干个运算对象；如取正（+）与取负（ - ）运算符只有一个运算对象，称为单目运算符；加（ +）、减（ - ）、乘（ * ）、除（ / ）、乘幂（ * ）有两个运算对象，称为双目运算符； 三元函数 fx,y,z为 f函数运算符， 有三个运算对象，称为三目运算符；多元函数有多个运算对象称多目运算符；用树表

3、示算术表达式原就是：(1) 表达式中的每一个运算符在树中对应一个结点，称为运算符结点(2) 运算符的每一个运算对象在树中为该运算结点的子树 在树中的次序从左到右 (3) 运算对象中的单变量均为叶子结点依据上面原就，可将表达式：a*b+c/d+c*h-g*f表示如下的树；树在运算机中通常用多重链表表示，多重链表的每个结点描述了树中对应结点的信息，每个结点中的链域（指针域）个数随树中该结点的度而定；1.6.2 二叉树及其基本性质1. 什么是二叉树二叉树是很有用的非线性结构；它与树结构很相像， 树结构的全部术语都可用到二叉树这种结构上；二叉树具有以下两个特点：（1）非空两叉树只有一个根结点（2）每个

4、结点最多有两棵子树，且分别称该结点的左子树与右子树；也就是说，在二叉树中，每一个结点的度最大为2，而且全部子树也均为二叉树；二叉树中的每一个结点可以有左子树没有右子树，也可以有右子树没有左子树，甚至左右子树都没有；2. 二叉树的基本性质二叉树性质有：性质 1：在二叉树的第k 层上，最多有 2k-1 k>=1 个结点性质 2：深度为 m 的二叉树最多有2m-1 个结点性质 3：在任意一棵二叉树中，度为0 的结点（即叶子结点）总比度为2 的结点多一个性质 4：具有 n 个结占的二叉树，其深度至少为log 2n+1,其中log 2n 表示取 log 2 n 的整数部分；3. 满二叉树与完全二叉

5、树（1） 满二叉树满两叉树是除了最终一层外， 每一层上的全部结点都有两个子结点； 即在满二叉树中，每一层上的结点数都达到最大值；在满二叉树的第 k 层上有 2k-1 个结点，且深度为 m的满二叉树有 2m -1 个结点；如图：深度为 2 的满二叉树深度为 3 的满二叉树深度为 4 的满二叉树（2） 完全二叉树完全二叉树除最终一层外，每一层上的结点数均达到最大数；最终一层只缺少右边的如干结点；如图深度为 3 的完全二叉树深度为 4 的完全二叉树完全二叉树具有以下两个性质：性质 5：具有 n 个结点的完全二叉树的深度为log 2 n+1性质 6：设完全 log 2n+1 有 n 个结点 如右图 1

6、0 个结点 , 编号如图 ；假如从根结点开头，按层序用自然数1,2,n 给结点进行编号，就对于编号为 kk=1,2,n 的结点有以下结论：（1）如 k=1，就该结点为根结点，它没有父结点；如k>1，就该结点的 父结点编号为 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

7、=4，就 9<=10，它的右左子结点h 编号为 91.6.3 二叉树的储备结构在运算机中，二叉树通常采纳链式储备结构；与线性链表类似，用于储备二叉树中各元素的储备结点也由两部分组成：数据域与指针域；但在二叉树中， 由于每一个元素可以有两个后件（即两个子结点），因此，用于储备二叉树的储备结点的指针域有两个：一个用于指向结点的左子树结构的储备地址，称为左指针域；另一个用于指向右子树结点的储备地址，称为右指针域；由于二叉树的储备结构中每一个储备结点有两个指针域，因此二叉树的链式储备结构也称为二叉链表；二叉树储备结构如图：二叉树1.6.4 二叉树的遍历二叉链表的规律状态二叉树的遍历是指不重复的拜

8、访二叉树中的全部结点；由于二叉树是一种非线性结构， 因此对二叉树的遍历要比遍历线性表复杂许多；在遍历二叉树过程中，当拜访到某个结点时，再往下拜访可能有两个分支， 应拜访哪一个分支呢？对于二叉树来说需要拜访根结点、左子树全部结点、右 子树全部结点，在这三者中，应拜访哪一个？也就是说，遍历二叉树实际是要 确定拜访各结点的次序；以便不重复又不能丢掉拜访结点，直到拜访到全部结 点；在遍历二叉树的过程中，一般选遍历左子树，然后再遍历右子树，在先左后右原就下依据拜访结点次序，二叉树的遍历分为三种方法；方法如下：1. 前序遍历（ dlr）前序遍历第一拜访根结点然后遍历左子树，最终遍历右子树；在遍历左、右子树

9、时，仍旧先拜访根结点，然后遍历左子树，最终遍历右子树；即：如二叉树为空就终止返回，否就：（1）拜访根结点（2）前序遍历左子树（3）前序遍历右子树留意的是：遍历左右子树时仍旧采纳前序遍历方法；例：如图二叉树，就前序遍历结果是： a b d e c f2. 中序遍历（ ldr）中序遍历第一遍历左子树，然后拜访根结点，最终遍历右子树；在遍历左、右子树时，仍旧先遍历左子树，再拜访根结点，最终遍历右子树；即：如二叉树为空就终止返回，否就：（1）中序遍历左子树（2）拜访根结点（3）中序遍历右子树；留意的是：遍历左右子树时仍旧采纳中序遍历方法；例：如图二叉树，就中序遍历结果是： d b e a f c3. 后序遍历（ lrd）后序遍历第一遍历左子树，然后遍历右子树，最