事故二叉树计算机算法【摘要】根据《数据结构》中的二叉树算法,结合事故树算法的特点,提出事故二叉树算法。该算法是对事故树求解算法的有益补充和发展，具有广阔的应用前景和现实意义。【关键词】事故树二叉树二叉树遍历事故二叉树二叉树结点分裂法AlgorithmofFaultBinaryTreeYuXiangqianCaiSijing(SchoolofResourcesEngineering,theUniversityofScience&TechnologyBeijing)AbstractOnthebasisofthealgorithmofbinarytreeinDATASTRUCTURESandthealgorithmoffaulttree,thealgorithmoffaultbinarytreeisputforward.It’sanusefulcomplimentandstepforawrdofthealgorithmoffaulttree.Itopensupavastrangeofapplicationprospectsandhaspractcalsignificance.Keywords：BinarytreeFaulttreeTraversingbinarytreeFaultbinarytreeAlgorithmofsplittingthenodeofbinarytree1前言近年来，计算机辅助事故树分析方法发展很快，新的算法不断被提出。本论文根据《数据结构》［1］中的二叉树算法，结合事故树算法的特点，提出事故二叉树算法。通过建立事故二叉树及利用本文所介绍的一系列事故二叉树算法，不仅可以很方便地实现事故树定性分析中的最小割集和最小径集的求解,以及实现事故树定量分析中的顶上事件发生概率、各基本事件的概率重要度和临界重要度的求解，而且可以实现计算机辅助事故树绘图中的坐标计算问题。该算法是对事故树求解算法的有益的补充和发展，具有现实意义和广阔的应用前景。2事故二叉树的存储结构事故树的逻辑结构与事故二叉树的存储结构之间的对应关系，下文举例说明。事故树的逻辑结构举例：对应图1的事故二叉树的结点的存储结构如下：表1事故二叉树的结点的存储结构第一个孩子水平方向坐标垂直方向坐标结点的信息与非门标志此结点的孩子个数此结点的双亲此结点的下一兄弟*fchhoriverti*infogatechinum*pare*nsib事故二叉树的结点的存储结构的C语言定义如下：图1事故树举例structnode{structnode*fch;doublehori;intvert;char*info;intgate,chinum;structnode*pare,*nsib;……(还可以继续扩充)}；对应图1的事故二叉树的存储结构表示如图2。图2对应图1的事故二叉树的存储结构事故二叉树的存储结构建立过程很简单，只需输入那些“发生了火灾”、“在房屋火灾中受伤”等汉字信息及与非门类型及有没有孩子的yesorno选择，其它信息诸如结点水平方向坐标、结点垂直方向坐标、结点的孩子个数等信息，都可以靠编写二叉树遍历程序计算出。3事故二叉树绘图下面所示的3个函数分别为求结点的垂直坐标、水平坐标、孩子个数的函数。这对计算机辅助事故树绘图很有意义。/*求事故树的结点的垂直坐标。*/voidlevel(structnode*gen,intlev){if(gen){gen->vert=lev;level(gen->fch,lev+1);level(gen->nsib,lev);};}/*求事故树的结点的水平坐标，其中ho为全局double变量。*/voidhorizon(structnode*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);};};}/*求每个结点的孩子数目的程序*/voidchildnum(structnode*root){structnode*p;inti;图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语言定义如下：structjiedian{图5二叉树初始化structjiedian*zongxiang;char*info;structjiedian*hengxiang;………(可以继续扩充）}；图6二叉树遍历与分裂的过程一开始，得到如图5所示...
