事故二叉树计算机算法(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　事故二叉树算法的扩展
　　对于事故树定量分析中的顶上事件发生概率的计算方法，则只需在事故二叉树的结点中再增加一个结点事件发生的概率的域和一个结点事件不发生的概率的域，然后适当改进前面提到的求事故树结点水平坐标的算法，便可计算出来。