事故二叉树计算机算法

【摘　要】　根据《数据结构》中的二叉树算法,结合事故树算法的特点,提出事故二叉树算法。该算法是对事故树求解算法的有益补充和发展，具有广阔的应用前景和现实意义。
【关键词】　事故树　二叉树　二叉树遍历　事故二叉树　二叉树结点分裂法

Yu Xiangqian　Cai Sijing
(School of Resources Engineering, the University of Science & Technology Beijing)

Abstract　On 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 tree　Fault tree　Traversing binary tree　Fault binary tree
Algorithm of splitting the node of binary tree

图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，然后计算方法和上面所述的顶上事件发生概率的计算方法相同。

作者地址：北京市海淀区；北京科技大学资源工程学院；邮编：100083

作者单位：北京科技大学资源工程学院

参考文献