【摘　要】　根據(jù)《數(shù)據(jù)結(jié)構(gòu)》中的二叉樹算法,結(jié)合事故樹算法的特點(diǎn),提出事故二叉樹算法。該算法是對(duì)事故樹求解算法的有益補(bǔ)充和發(fā)展，具有廣闊的應(yīng)用前景和現(xiàn)實(shí)意義。
【關(guān)鍵詞】　事故樹　二叉樹　二叉樹遍歷　事故二叉樹　二叉樹結(jié)點(diǎn)分裂法
Algorithm of Fault Binary Tree
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　前　言
　　近年來(lái)，計(jì)算機(jī)輔助事故樹分析方法發(fā)展很快，新的算法不斷被提出。本論文根據(jù)《數(shù)據(jù)結(jié)構(gòu)》［1］中的二叉樹算法，結(jié)合事故樹算法的特點(diǎn)，提出事故二叉樹算法。通過(guò)建立事故二叉樹及利用本文所介紹的一系列事故二叉樹算法，不僅可以很方便地實(shí)現(xiàn)事故樹定性分析中的最小割集和最小徑集的求解,以及實(shí)現(xiàn)事故樹定量分析中的頂上事件發(fā)生概率、各基本事件的概率重要度和臨界重要度的求解，而且可以實(shí)現(xiàn)計(jì)算機(jī)輔助事故樹繪圖中的坐標(biāo)計(jì)算問(wèn)題。該算法是對(duì)事故樹求解算法的有益的補(bǔ)充和發(fā)展，具有現(xiàn)實(shí)意義和廣闊的應(yīng)用前景。
2　事故二叉樹的存儲(chǔ)結(jié)構(gòu)
　　事故樹的邏輯結(jié)構(gòu)與事故二叉樹的存儲(chǔ)結(jié)構(gòu)之間的對(duì)應(yīng)關(guān)系，下文舉例說(shuō)明。
　　事故樹的邏輯結(jié)構(gòu)舉例：對(duì)應(yīng)圖1的事故二叉樹的結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如下：
表1　事故二叉樹的結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)

第一個(gè)
孩　子水平方向
坐　　標(biāo)垂直方向
坐　　標(biāo)結(jié)點(diǎn)的
信　息與非門
標(biāo)　志此結(jié)點(diǎn)的
孩子個(gè)數(shù)此結(jié)點(diǎn)的
雙　　親此結(jié)點(diǎn)的
下一兄弟
*fchhoriverti*infogatechinum*pare*nsib

　　事故二叉樹的結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言定義如下：

圖1　事故樹舉例
struct node {
　　struct node *fch;
　　double hori;
　　int vert;
　　char *info;
　　int gate,chinum;
　　struct node *pare,*nsib;
　　……(還可以繼續(xù)擴(kuò)充)
　　}；
　　對(duì)應(yīng)圖1的事故二叉樹的存儲(chǔ)結(jié)構(gòu)表示如圖2。
　　

圖2　對(duì)應(yīng)圖1的事故二叉樹的存儲(chǔ)結(jié)構(gòu)
　　事故二叉樹的存儲(chǔ)結(jié)構(gòu)建立過(guò)程很簡(jiǎn)單，只需輸入那些“發(fā)生了火災(zāi)”、“在房屋火災(zāi)中受傷”等漢字信息及與非門類型及有沒有孩子的yes
or no
選擇，其它信息諸如結(jié)點(diǎn)水平方向坐標(biāo)、結(jié)點(diǎn)垂直方向坐標(biāo)、結(jié)點(diǎn)的孩子個(gè)數(shù)等信息，都可以靠編寫二叉樹遍歷程序計(jì)算出。
3　事故二叉樹繪圖
　　下面所示的3個(gè)函數(shù)分別為求結(jié)點(diǎn)的垂直坐標(biāo)、水平坐標(biāo)、孩子個(gè)數(shù)的函數(shù)。這對(duì)計(jì)算機(jī)輔助事故樹繪圖很有意義。
　　 /*求事故樹的結(jié)點(diǎn)的垂直坐標(biāo)。*/
　　void level(struct node *gen, int lev)
　　{　
　　if(gen){ gen->vert=lev;
　　level(gen->fch,lev+1);
　　level(gen->nsib,lev);
　　};
　　　}
　　/* 求事故樹的結(jié)點(diǎn)的水平坐標(biāo)，其中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);
　　};
　　};
　　　}
　　/*求每個(gè)結(jié)點(diǎn)的孩子數(shù)目的程序*/
　　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　事故二叉樹結(jié)點(diǎn)分裂法
　　最小割集的求法很多［2］，如行列法、結(jié)構(gòu)法、布爾代數(shù)化簡(jiǎn)法、質(zhì)數(shù)代入法、矩陣法。這些方法，要么是難以用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)，要么是受數(shù)組定義的限制，影響動(dòng)態(tài)擴(kuò)充存儲(chǔ)空間。下面介紹一種二叉樹結(jié)點(diǎn)分裂法：

圖4　圖3所示事故樹的存儲(chǔ)結(jié)構(gòu)
假設(shè)有一棵事故樹，它的邏輯結(jié)構(gòu)如圖3。
　　則它的二叉樹存儲(chǔ)結(jié)構(gòu)如圖4。
　　另外，再定義一棵二叉樹，其結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言定義如下：
struct jiedian{　

圖5　二叉樹初始化
struct jiedian *zongxiang;
　　char *info;
　　struct jiedian *hengxiang;
　　………(可以繼續(xù)擴(kuò)充）
　　}；

圖6　二叉樹遍歷與分裂的過(guò)程
　　一開始，得到如圖5所示的一棵二叉樹。然后對(duì)這棵二叉樹進(jìn)行遍歷，當(dāng)遍歷所遇到的結(jié)點(diǎn)的信息代表的是或門時(shí)，對(duì)該結(jié)點(diǎn)進(jìn)行橫向分裂；當(dāng)遍歷所遇到的結(jié)點(diǎn)的信息代表的是與門時(shí)，對(duì)該結(jié)點(diǎn)進(jìn)行縱向分裂。一次二叉樹遍歷完后，緊接著進(jìn)行下一次遍歷，直到遍歷所遇到的所有的結(jié)點(diǎn)的信息都代表著葉子結(jié)點(diǎn)的信息為止。遍歷與分裂過(guò)程如圖6。
　　可以把這個(gè)結(jié)果看成是以zongxiang指針連接起來(lái)的一個(gè)鏈表，此鏈表便是圖3所示的事故樹的割集。然后對(duì)此鏈表各元素進(jìn)行比較，把應(yīng)該刪除的元素進(jìn)行刪除，最后就可以得到圖3所示的事故樹的最小割集，如圖7。
　　最小徑集的求解與最小割集的求解類似。
5　事故二叉樹算法的擴(kuò)展
　　對(duì)于事故樹定量分析中的頂上事件發(fā)生概率的計(jì)算方法，則只需在事故二叉樹的結(jié)點(diǎn)中再增加一個(gè)結(jié)點(diǎn)事件發(fā)生的概率的域和一個(gè)結(jié)點(diǎn)事件不發(fā)生的概率的域，然后適當(dāng)改進(jìn)前面提到的求事故樹結(jié)點(diǎn)水平坐標(biāo)的算法，便可計(jì)算出來(lái)。

圖7　刪除冗余結(jié)點(diǎn)后的二叉樹
　　對(duì)于事故樹定量分析中的各基本事件的概率重要度和臨界重要度的計(jì)算方法，則只需將相對(duì)無(wú)關(guān)的事件的發(fā)生概率賦值為0，然后計(jì)算方法和上面所述的頂上事件發(fā)生概率的計(jì)算方法相同。
作者地址：北京市海淀區(qū)；北京科技大學(xué)資源工程學(xué)院；郵編：100083
作者單位：北京科技大學(xué)資源工程學(xué)院
參考文獻(xiàn)
　　1　嚴(yán)蔚敏、吳偉民.數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社，1992.6：118—154.
　　2　韋冠俊.安全原理與事故預(yù)測(cè).北京：冶金工業(yè)出版社，1995.11：64—112.