为m(m>0)个互不相交的有限集T1,T2，?，Tm，其中每一个集合本身又是一棵树，并且称为根的子树。如图3-1树的示例。它是有13个结点的树，其中A是根，其余结点分成3个互不相交的子集:T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}；T 1,T2和T3都是根为A的子树，且本身也是一棵树。例如T1其根为B，其余结点分为两个互不相交的子集。T11={E,K,L}和T12={F}都是B的子树。而T11中E是根，{K}和{L}是E的两棵互不相交的子树，其本身又是只有一个根结点的树，如图3-1所示。
A B C D E F G H I J K L 图3-1 树的示例 Fig. 3-1 illustration of tree M 树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它道出了树的固有特性:分支分层。树的结点包含一个数据元素及若干指向其子树的分支。
结点拥有的子树数称为结点的度。例如在树的示例中，A的度为3, C的度为1，F的度为0。结点的子树的根称为该结点的孩子，相应的，该结点称为该子的双亲。
例如，在树的示例所示的树中，D为A的子树，同时又是T3的根，则D是A的孩子，而A则是D的双亲，同一个双亲的孩子之间互称兄弟。例如，H, I和J互为兄弟。结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度或高度。如A树的深度为4。如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的孩子称为最后一个孩子。 3.3.3 发动机故障树与树状数据结构
发动机故障树完全符合树的各种思想特点。
- 9 -
如图3-2所示，发动机起动困难故障树，A:表示发动机系统,第一层表示十大确定性功能故障现象；B:表示发动机起动困难；C: 表示功率不足；D: 表示排气不正常；E: 表示运转不稳；F: 表示运转中有不正常响声；J: 表示机油压力不足等等。
第二层表示上一级故障现象下的一级故障原因，N: 表示燃油供给系统不正常；O: 表示气缸压力不足；P: 表示配气机构工作不正常；Q: 表示配气机构不正常；R：表示燃油系工作不正常；S: 表示润滑系工作不正常等等。
A B C D E F ????? J N O P Q R S T U V ????? 图3-2 发动机起动困难故障树 Fig. 3-2 the tree of difficulty in engine starting 图3-2为发动机起动困难的故障树，B表示发动机起动困难，为故障树的根结点，下一层N, O, P为故障树的子树结点即为一级原因，再下一层则是二级原因的树叉，二级原因下边又包含三级原因，即故障树的第三层，由于故障树比较大，在这里就不详细叙述了。对于发动机的故障来说有好多，根据此种数据结构可以构成多棵故障树，即为故障森林。
森林是m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
3.3.4 二叉树及其操作
在数据结构当中有一种特殊树的抽象数据类型——二叉树。二叉树是另一种树状结构，它的特点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。对于二叉树重点讨论它的存储结构及操作。二叉树的存储结构一般采用双链式存储结构来存储，因为在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这里提出一个遍历二叉树的问题，即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，表现在数据库当中一般为检索、插入和删除等操作。
- 10 -
遍历对线性结构来说，是一个容易解决的问题。而对二叉树则不然，由于二叉树是一种非线性结构，每个结点都只能有两棵子树，因而需要寻找一种存储规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于某种操作的产生。分析表明，二叉树采用双向链表的存储结构对于各种操作都是比较便利的。表示二叉的链表中的结点至少包含4个域:数据域和左、右孩子域，及父亲结点域。利用这两种结点结构所得二叉树的存储结构称之为三叉链表或双向链表。
在二叉树的双向链表的存储结构基础上进行的操作，通过遍历根结点和其左右子树，便是遍历了整个二叉树。假如以L, D, R分别表示遍历左子树、访问根结点和遍历右子树，则可能有DLR, LDR, LRD, DRL, RDL, RLD等六种遍历二叉树的方案。若限定先左后右，则只有前3种情况，分别称之为先(根)序遍历、中(根)序遍历和后(根)序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。
先序遍历二叉树的操作定义为:
若二叉树为空，则空操作；否则访问根结点；先序遍历左子树；先序遍历右子树。 中序遍历二叉树的操作定义为:若二叉树为空，则空操作；否则中序遍历左子树；访问根结点；中序遍历右子树。
后序遍历二叉树的操作定义为:若二叉树为空，则空操作；否则后序遍历左子树；后序遍历右子树；访问根结点。
算法1给出了先序遍历二叉树基本操作的递归算法在三叉链表上实现。
Status PreOrderTraverse(BiTeree T,Status(* Visit)(TElemType e)) //定义树T及访问函数
{ //采用二叉连表存储结构，Visit是对数据元素操作的应用函数， //先序遍立二叉数T的递归算法，对每个数据元素调用函数visit. //最简单的Visit函数是: //Status PrintElement(TelemType e // { //输出元素e的值
// printf(e)； //使用时，加上格式串 // return OK； // }
//调用实例：PreOrderTavese(T,PrintElement)；
if(T) { //函数体，当树T不为空时进入下面的遍历 if(Visit(T->data))
//访问根结点，当访问成功时进入下面的递归遍历
- 11 -
if(PreOrderTraverse(_>Ishild,Visit)) //递归调用自身访问左子树
if(PreOrderTraverse(T_>Ishild,Visit)) return OK； //调用自身访问右子树
return ERROR； //访问不成功时，返回ERROR }
else return OK； }//PeeOrderTraverse
根据上述思路，可类似的实现中序遍历和后序遍历的递归算法，此处不再一一列举，如图3-3所示。
a ＋ － ＋ ≠ e f b c － d 图3-3 算法图
Fig. 3-3 illustration of calculation
二叉树表示下述表达式：
a+b*(c-d)-e/f
则根据上述算法先序遍历二又树，按访问结点的先后次序将结点排列起来，可得到二叉树的先序序列为:
- + a * b – c d / e f
中序遍历此二又树，则可得此二叉树的中序序列为：
a + b * ( c – d ) – e / f
后序遍历此二叉树，则可得此二叉树的后序序列为：
a b c d - * + e f / -
依照递归算法执行过程中递归工作栈的状态变化情况可直接写出相应的非递归算
- 12 -
法。例如，从中序遍历递归算法执行中递归工作栈的状态可见:(1)工作记录中包含两项，其一是递归调用的语句编号，其二是指向根结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈；(2)若栈顶的记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶记录中指针所指的根结点；(3)若是从右子树返回，则表明当前层的遍历结束，应继续退栈。从另一角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。由此可得中序遍历二叉数的非递归算法:
Status inordertraverse(bitree T,Status(* Visit)(TelemType e)) {
//采用二叉链表存储结构，Visit是对时局元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个元素调用函数Visit. InitStack(s)； //建立空栈 Pust(S,T)； //根指针进栈
While(！StackEmpty(s) //当栈不为空的时候进入循环 {
While(GetTop(s,p)&&p) //取得栈顶元素并且不为0时 Pusth(s,p_>Ichild)； //向左走到尽头 Pop(s,p)； //空指针退栈
If (！Stacktmpty(s)) //当栈不为空时 { //访问结点，向右一步 Pop(s,p)； //栈顶元素出栈
If (!Visit(p_>data)) return error; //如果访问失败则返回错误 Push(s,p_>Ichild)； //右子树进栈 } //if } //while return ok；
} //InOrderTraverse
上面详细论述了二叉树的存储结构及其三种遍历的方法，那二叉树和故障森林有什么联系呢？经过上述分析，发动机故障采用故障树的结构来组织，多个故障就意味着一个故障森林，由上述分析可知，对于多个故障树的操作是相当的困难的，所以我们必须把故障森林转化成一棵故障树，这就是森林转化为二叉树的操作。
- 13 -