事故二叉树计算机算法.docx

事故二叉树计算机算法 【摘 要】 根据数据结构中的二叉树算法,结合 事故树算法的特点,提出事故二叉树算法。该算法是对事故 树求解算法的有益补充和发展，具有广阔的应用前景和现 实意义。 【关键词】 事故树 二叉树 二叉树遍历 事故二 叉树 二叉树结点分裂法 Algorithm of Fault Binary Tree Yu Xiangqian Cai Sijing (School of Resources Engineering, the University of Science 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，然后计算方法和上面所述的顶上事件发生概 率的计算方法相同。 作者地址：XX 市海淀区；XX 科技大学资源工程学院； 邮编：1