事故二叉树计算机算法

事故二叉树计算机算法事故二叉树计算机算法 摘要 根据 数据结构 中的二叉树算法 结合事故树算法的 特点 提出事故二叉树算法 该算法是对事故树求解算法的有益 补充和发展 具有广阔的应用前景和现实意义 关键词 事故树二叉树二叉树遍历事故二叉树二叉树结点分 裂法 algorithm of fault binary tree yu xiangqiancai sijing school of resources engineering the university of sciencetechnology beijing abstracton the basis of the algorithm of binary tree in data structures and the algorithm of fault tree the algorithm of fault binary tree is put forward it s an useful compliment and step forawrd of the algorithm of fault tree it opens up a vast range of application prospects and has practcal significance key words binary treefault treetraversing binary treefault binary tree algorithm of splitting the node of binary tree 1 前言 近年来 计算机辅助事故树分析方法发展很快 新的算法不断 被提出 本论文根据 数据结构 1 中的二叉树算法 结合 事故树算法的特点 提出事故二叉树算法 通过建立事故二叉 树及利用本文所介绍的一系列事故二叉树算法 不仅可以很方 便地实现事故树定性分析中的最小割集和最小径集的求解 以及 实现事故树定量分析中的顶上事件发生概率 各基本事件的概 率重要度和临界重要度的求解 而且可以实现计算机辅助事故 树绘图中的坐标计算问题 该算法是对事故树求解算法的有益 的补充和发展 具有现实意义和广阔的应用前景 2 事故二叉树的存储结构 事故树的逻辑结构与事故二叉树的存储结构之间的对应关系 下文举例说明 事故树的逻辑结构举例 对应图 1 的事故二叉树的结点的存储 结构如下 表 1 事故二叉树的结点的存储结构 第一个 孩子水平方向 坐标垂直方向 坐标结点的 信息与非门 标志此结点的 孩子个数此结点的 双亲此结点的 下一兄弟 fchhoriverti infogatechinum pare nsib 事故二叉树的结点的存储结构的 c 语言定义如下 图 1 事故树举例 struct node struct node fch double hori int vert char info int gate chinum struct node pare nsib 还可以继续扩充 对应图 1 的事故二叉树的存储结构表示如图 2 图 2 对应图 1 的事故二叉树的存储结构 事故二叉树的存储结构建立过程很简单 只需输入那些 发生了 火灾 在房屋火灾中受伤 等汉字信息及与非门类型及有没有 孩子的 yes or no 选择 其它信息诸如结点水平方向坐标 结点垂直方向坐标 结点的孩子个数等信息 都可以靠编写二叉树遍历程序计算出 3 事故二叉树绘图 下面所示的 3 个函数分别为求结点的垂直坐标 水平坐标 孩 子个数的函数 这对计算机辅助事故树绘图很有意义 求事故树的结点的垂直坐标 void level struct node gen int lev if gen gen vert lev level gen fch lev 1 level gen nsib lev 求事故树的结点的水平坐标 其中 ho 为全局 double 变量 void horizon struct node root if root if root fch root hori ho ho ho 1 if root pare root pare hori root pare hori root hori double root pare chinum horizon root nsib else horizon root fch if root pare root pare hori root pare hori root hori double root pare chinum horizon root nsib 求每个结点的孩子数目的程序 void childnum struct node root struct node p int i 图 3 事故树举例 if root p root fch i 0 while p p p nsib i root chinum i childnum root fch childnum root nsib 4 事故二叉树结点分裂法 最小割集的求法很多 2 如行列法 结构法 布尔代数化简 法 质数代入法 矩阵法 这些方法 要么是难以用计算机语 言实现 要么是受数组定义的限制 影响动态扩充存储空间 下面介绍一种二叉树结点分裂法 图 4 图 3 所示事故树的存储结构 假设有一棵事故树 它的逻辑结构如图 3 则它的二叉树存储结构如图 4 另外 再定义一棵二叉树 其结点的存储结构的 c 语言定义如 下 struct jiedian 图 5 二叉树初始化 struct jiedian zongxiang char info struct jiedian hengxiang 可以继续扩充 图 6 二叉树遍历与分裂的过程 一开始 得到如图 5 所示的一棵二叉树 然后对这棵二叉树进 行遍历 当遍历所遇到的结点的信息代表的是或门时 对该结 点进行横向分裂 当遍历所遇到的结点的信息代表的是与门时 对该结点进行纵向分裂 一次二叉树遍历完后 紧接着进行下 一次遍历 直到遍历所遇到的所有的结点的信息都代表着叶子 结点的信息为止 遍历与分裂过程如图 6 可以把这个结果看成是以 zongxiang 指针连接起来的一个链表 此链表便是图 3 所示的事故树的割集 然后对此链表各元素进 行比较 把应该删除的元素进行删除 最后就可以得到图 3 所 示的事故树的最小割集 如图 7 最小径集的求解与最小割集的求解类似 5 事故二叉树算法的扩展 对于事故树定量分析中的顶上事件发生概率的计算方法 则只 需在事故二叉树的结点中再增加一个结点事件发生的概率的域 和一个结点事件不发生的概率的域 然后适当改进前面提到的 求事故树结点水平坐标的算法 便可计算出来 图 7 删除冗余结点后的二叉树 对于事故树定量分析中的各基本事件的概率重要度和临界重要 度的计算方法 则只需将相对无关的事件的发生概率赋值为 0 然后计算方法和上面所述的顶上