|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 >
|
被考次数：4次
被考频率：中频率
总体答错率：37%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
相关知识点：27个
|
|
|
|
|
|
|
树（tree）是n（n≥0）个结点的有限集。n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：
|
|
|
|
|
|
（2）其余结点分成m （m≥0）个互不相交的有限集合T1,T2,…,Tm，其中每一个集合又都是一棵树，称T1,T2,…，Tm为根结点的子树。
|
|
|
|
以上定义是一个递归定义，它反映了树的固有特性，因为一棵树是由根和它的子树构成，而子树又是由子树的根和更小的子树构成。如下图所示的树中，A是根结点，其余结点分成三个互不相交的子集：S1=｛B，E，F｝, S2=｛C｝，S3=｛D, G，H，I，J，K｝,这三个集合分别构成了A的三棵子树；在S3构成的子树中，D是根结点，D又具有三棵子树，这三棵子树的根结点分别是G，H和I；对于结点G和I，它们的子树均为空。
|
|
|
|
|
|
|
|
图中树的表示类似于自然界中一棵倒长的树，“树型结构”由此得名，这种表示方法比较形象、直观，因而容易为人们所接受，是树的一种最常用的表示方法。树型结构除以上表示方法外，还有括号表示法、凹入表示法和嵌套集合表示形式。下图给出了上图中树的这三种表示形式。
|
|
|
|
|
|
|
|
在下图的树中，采用线段连接两个相关联的结点，如A和B，D和H等。其中A和D是上端结点，B和H是下端结点。称A、D分别是B、H的双亲（或父母或前件），B和H分别为A和D的子女（或孩子或后件）。由于E和F的双亲为同一结点，称E和F互为兄弟。在任何一棵树中，除根结点外，其他任何一个结点有且仅有一个双亲，有0个或多个子女，且它的子女恰巧为其子树的根结点。将一结点拥有的子女数称为该结点的度，树中所有结点度的最大值称为树的度。称树中连接两个结点的线段为树枝。在树中，若从结点Ki开始沿着树枝自上而下能到达结点Kj，则称从Ki到Kj存在一条路径，路径的长度等于所经过的树枝的条数。在下图中，从结点A到结点J存在一条路径，路径的长度为3；从D到K也存在一条路径，路径的长度为2。将从树根到某一结点Ki的路径中Ki前所经过的所有结点称为Ki的祖先；反之，以某结点Ki为根的子树中的任何一个结点都称为Ki的子孙。下图中，A、D、H均为J和K的祖先，而G、H、I、J和K均为D的子孙。
|
|
|
|
树中结点的层次：从树根开始定义，根结点为第一层，根的子女结点构成第二层，依次类推，若某结点Kj位于第i层，则其子女就位于第i+1层。称树中结点的最大层次数为树的深度或高度。下图中，A结点位于第一层，B、C、D位于第2层，E、F、G、H和I位于第三层等，整棵树的高度为4。
|
|
|
|
|
|
|
|
如果树中任意结点的子树均看成是从左到右有次序的，不能随意交换，则称该树是有序树；否则称之为无序树。如下图所示的两棵树，若看成是有序树，它们是不等价的；若看成是无序树，两者相等。
|
|
|
|
|
|
|
|
由m（m≥0）棵互不相交的树构成的集合称为森林。森林和树的概念十分相近，每个结点的子树的集合即为一个森林；而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。
|
|
|
|
二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树，在二叉树中不存在度大于2的结点，并且二叉树的子树有左右之分，它的次序是不能任意颠倒的。
|
|
|
|
|
|
存储结构的选择不仅要考虑数据元素如何存储，更重要的是要考虑数据元素之间的关系如何体现。根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。本节主要讨论树的双亲表示法，如下图所示。
|
|
|
|
|
|
|
|
在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。因此，根据树的这种性质，存储树中结点时，应该包含两个信息：结点的值data和体现结点之间相互关系的属性——该结点的双亲parent。借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为双亲表示法，为了查找方便，可以将树中所有结点存放在一个一维数组中，具体类型定义如下。
|
|
|
|
|
|
其中datatype应根据结点值的具体类型给出定义，在此假设为字符型。这里值得一提的是，根结点在树中有着与其他结点不同的地位，树根的位置是非常关键的，正如单链表中抓住了表头指针，就掌握了整个链表一样，树中只要知道树根在哪里，便可以访问到树中所有的结点，因此树的存储结构中要特别考虑根结点的存储。
|
|
|
|
其中parent的值为-1表示结点的双亲不存在。本树中root域的值为0,表示树的根结点存放在数组的第一个元素中。
|
|
|
|
|
|
所谓树的遍历，指按某种规定的顺序访问树中的每一个结点一次，且每个结点仅被访问一次。根据根结点的访问位置不同，树的遍历可以分为前序遍历和后序遍历；又由于树具有层次性，遍历树中结点时可以按层次自上而下访问每个结点，因此树的遍历方式分为以下三种：
|
|
|
|
|
|
首先访问根结点，再依次按前序遍历的方式访问根结点的每一棵子树。
|
|
|
|
|
|
首先按后序遍历的方式访问根结点的每一棵子树，然后再访问根结点。
|
|
|
|
|
|
首先访问第一层上的根结点，然后从左到右依次访问第二层上的所有结点，再以同样的方式访问第三层上的所有结点……最后访问树中最低一层的所有结点。
|
|
|
|
如下图所示的树对其进行三种遍历的结果分别为：前序遍历的结果——ABCEFHIGD；后序遍历的结果——BEHIFGCDA；层次遍历的结果——ABCDEFGHI。
|
|
|
|
|
|
|
|
显然，树的前序遍历和后序遍历的定义具有递归性，因此采用递归方式实现树的前、后序遍历算法十分方便，只要按照其各自规定的顺序，访问根结点时就输出根结点的值，访问子树时进行递归调用即可。以下以指针方式的孩子表示法作为树的存储结构，分别给出树的前序遍历和后序遍历算法的实现。
|
|
|
|
|
|
|
|
|
|
|
