【摘　要】　根據《數據結構》中的二叉樹算法,結合事故樹算法的特點,提出事故二叉樹算法。該算法是對事故樹求解算法的有益補充和發展，具有廣闊的應用前景和現實意義。
【關鍵詞】　事故樹　二叉樹　二叉樹遍歷　事故二叉樹　二叉樹結點分裂法

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

作者單位：北京科技大學資源工程學院

參考文獻