资源描述：
《组合数学-输出所有路径-路径数问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、组介数学■输出所冇路径一.程序#include#ineludeintnuml=l;〃全局变量主要是为了在遍历二叉树的时候，只对无禁止线段的路径数计数。typedefstructPoint{intx,y;}；typedefstructnode//二叉树{Pointdata;//二叉树的点坐标intnum;//主要是为了求经过此结点的次数C(x+y,y);structnode*lchl,*rchl;}*NODE;structLine//禁止线段的结构体{Pointsta
2、rt;Pointend;}；boolbelongTo(Linel,Lineline[],intn)〃判断I是否属于禁止经过的线段，是则返回true;{inti;for(i=0;ivn;i++){if(l.start.x==line[i].start.x&&l.start.y==line[i].start.y&&l.end.x==line[i].end.x&&l.end.y==line[i].end.y)returntrue;}returnfalse;}intC(intm,intn)〃返回组合数C(m,n
3、){doublea=1.0,b=1.0;intc;inti;for(i=0;ivn;i++)a=a*(double)(m-i);for(i=n;i〉0;iTb=b*(double)i;c=a/b;returnc;}voidcreate(NODE&t,Pointa)//创建二叉树,父结点坐标为(x,y),左子树结点坐标为(x,y・l),右子树结点坐标为(x-l,y)o宜到所有叶了结点为(0,0)为止。{Pointr,l;〃左结点，右结点数据r.x=a.x;r.y=a.y・l;l.x=a.x-l;Ly=a.
4、y;t=(node*)malloc(sizeof(node));t->data=a;t->num=C(a.x+a.y,a.y);if(r.x<0
5、
6、r.y<0)〃当x,y都小于0时停止创建结点t->rchl=NULL;elsecreate(t->rchl,r);//递归创建右结点if(l.x<0
7、
8、l.y<0)t->lchl=NULL;elsecreate(t->lchl,l);}voidprints(NODET)〃打印结点坐标(x,y){if(T){printf("(%d/"/T->data.x);p
9、rintf("%d)",T->data.y);}}voidErgodicfNODET,intn,Lineline[])〃一次遍历，从根结点到叶子结点，找出其中一条路径{intb,i;//b为此二叉树的层数Linel,p;〃父结点与子结点的一条线段，为了判断此线段是否属于禁止线段。b=T->data.x+T->data.y；if(T)//结时点不为{numl++;〃上面的全局变量，如果此路径不含禁止线段，那么就直接加1,for(i=0;inum>=l)//此
10、结点的遍历次数>=：!■才继续遍历T->num・・;//此结点的遍历次数・1prints(T);//打印此结点信息p.end=T->data;l.end=T->data;if(T->rchl&&T・>rchl・>num>=l)〃如果左子树存在，而l=L可以继续遍历此接结l.start=T->rchl->data;讦(!belongTo(l,line,n))〃父子结点构成的线段与禁止线段进行比较，不同,则继续{T=T->rchl;}else//含有禁止线段，中断{prints含有禁止路径”);numl—；
11、break;}}elseif(T->lchl&&T->lchl->num>=l){p.start=T->lchl->data;if(!belongTo(p川ne,n)){T=T->lchl;}else{printfC*含有禁止路径”);numl"；break;}}}}}}voidmain(){intx二5,y二3,i,h,j;//x,y终点坐标Pointdata;//终点坐标结点data.x=x;data.y=y;NODEroot;//数的根结点create(root,data);〃以根结点(x,y)仓
12、ij建二叉树h=root->num;//总的路径数intn=3;〃禁止线段条数Line*line二newLine[n];line[O].start.x=2;line[0].start.y=2;line[0].end.x=3;line[0].end.y=2;line[l].start.x=4;line[l].start.y=2;line[l].end.x=5;line[l].end.y=2;line[2].start.x=6;line[2].
