全国计算机等级考试二级公共根底之树与二叉树1.6 树与二叉树树的根本概念树是一种简洁的非线性构造在树这种构造中，全部元素之间的关系具有明 显的层次关系用图形表示树这种数据构造时，就象自然界中的倒长的树，这种构造就用“树〞来命名如图：在树构造中，每个结点只有一个前件，称为父结点，没有前件的结点只有一 个，称为树的根结点，简称为树的根〔如 R〕在树构造中，每一个结点可以有多个后件，它们都称为该结点的子结点没 有后件的结点称为叶子结点〔如 W，Z，A ，L，B，N，O，T，H，X〕在树构造中，一个结点拥有的后件个数称为结点的度〔如 R 的度为 4，KPQDEC 结点度均为 2〕树的结点是层次构造，一般按如下分层：根结点在第1 层；同一个层全部结点的全部子结点都在下一层树的最大层次称为树的深度如上图中的树深度为 4R 结点有 4 棵子树，KPQDEC 结占各有两棵子树；叶子没有子树在计算机中，可以用树构造表示算术运算在算术运算中，一个运算符可以 有假设干个运算对象如取正〔+〕与取负〔-〕运算符只有一个运算对象，称为单目运算符；加〔+〕、减〔-〕、乘〔*〕、除〔/〕、乘幂〔**〕有两个运算对象，称为双目运算符；三元函数 f(x,y,z)为 f 函数运算符，有三个运算对象，称为三目运算符。
多元函数有多个运算对象称多目运算符用树表示算术表达式是：(1) 表达式中的每一个运算符在树中对应一个结点，称为运算符结点(2) 运算符的每一个运算对象在树中为该运算结点的子树(在树中的挨次从 左到右)(3) 运算对象中的单变量均为叶子结点依据上面，可将表达式：a*(b+c/d)+c*h-g*f 表示如下的树树在计算机中通常用多重链表表示，多重链表的每个结点描绘了树中对应结 点的信息，每个结点中的链域 〔指针域〕个数随树中该结点的度而定二叉树及其根本性质1. 什么是二叉树二叉树是很有用的非线性构造它与树构造很相像，树构造的全部术语都可 用到二叉树这种构造上二叉树具有以下两个特点：〔1〕非空两叉树只有一个根结点〔2〕每个结点最多有两棵子树，且分别称该结点的左子树与右子树也就是说，在二叉树中，每一个结点的度最大为 2，而且全部子树也均为二叉树二叉树中的每一个结点可以有左子树没有右子树，也可以有右子树没有左子树，甚至左右子树都没有2. 二叉树的根本性质二叉树性质有：性质 1：在二叉树的第 K 层上，最多有 2k-1(k>=1)个结点性质 2：深度为 m 的二叉树最多有 2m-1 个结点性质 3：在任意一棵二叉树中，度为 0 的结点〔即叶子结点〕总比度为 2 的结点多一个性质 4：具有 n 个结占的二叉树，其深度至少为[log n]+1, 其中[log n]表2 2示取 log n 的整数局部。
23. 满二叉树与完全二叉树〔1〕 满二叉树满两叉树是除了最终一层外，每一层上的全部结点都有两个子结点即在 满二叉树中，每一层上的结点数都到达最大值在满二叉树的第k 层上有 2k-1 个结点，且深度为 m 的满二叉树有 2m -1 个结点如图：深度为 2 的满二叉树深度为 3 的满二叉树深度为 4 的满二叉树〔2〕 完全二叉树完全二叉树除最终一层外，每一层上的结点数均到达最大数；最终一层 只缺少右边的假设干结点如图深度为 3 的完全二叉树深度为 4 的完全二叉树完全二叉树具有以下两共性质：性质 5：具有 n 个结点的完全二叉树的深度为[log n]+12性质 6：设完全[log n]+1 有 n 个结点(如右图 10 个结点,编号如图)假设2从根结点开头，按层序用自然数 1,2,…n 给结点进展编号，那么对于编号为k(k=1,2,…n)的结点有以下结论：〔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. 前序遍历〔DLR〕前序遍历首先访问根结点然后遍历左子树，最终遍历右子树在遍历左、右 子树时，仍旧先访问根结点，然后遍历左子树，最终遍历右子树即：假设二叉树为空那么完毕返回，否那么：〔1〕访问根结点〔2〕前序遍历左子树〔3〕前序遍历右子树留意的是：遍历左右子树时仍旧承受前序遍历方法 例：如图二叉树，那么前序遍历结果是：A B D E C F2. 中序遍历〔LDR〕中序遍历首先遍历左子树，然后访问根结点，最终遍历右子树在遍历左、 右子树时，仍旧先遍历左子树，再访问根结点，最终遍历右子树即：假设二叉树为空那么完毕返回，否那么：〔1〕中序遍历左子树〔2〕访问根结点〔3〕中序遍历右子树留意的是：遍历左右子树时仍旧承受中序遍历方法 例：如图二叉树，那么中序遍历结果是：D B E A F C3. 后序遍历〔LRD〕后序遍历首先遍历左子树，然后遍历右子树，最终访问根结点在遍历左、 右子树时，仍旧先遍历左子树，然后遍历右子树，最终访问根结点即：假设二叉树为空那么完毕返回，否那么：〔1〕后序遍历左子树，〔2〕后序遍历右子树〔3〕最终访问根结点留意的是：遍历左右子树时仍旧承受后序遍历方法 例：如图二叉树，那么中序遍历结果是：D E B F C A。