鏁版嵁緇撴瀯絎叚绔犵畻娉曡璁￠[3]_璺ㄨ€冪綉

1錛庣紪紼嬫眰浠ュ瀛愨€斿厔寮熻〃紺烘硶瀛樺偍鐨勬．鏋楃殑鍙跺瓙緇撶偣鏁般€傝姹傛弿榪扮粨鏋勩€傘€?a target="_blank">鍖椾含宸ヤ笟澶у2000浜?/span>(10鍒?/span>)銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€[棰樼洰鍒嗘瀽]褰撴．鏋楋紙鏍?wèi)锛変互瀛╁瓙鍏勫紵琛ńC烘硶瀛樺偍鏃訛紝鑻ョ粨鐐規(guī)病鏈夊瀛愶紙fch=null錛?/span>,鍒欏畠蹇呮槸鍙跺瓙錛屾€葷殑鍙跺瓙緇撶偣涓暟鏄瀛愬瓙鏍?wèi)锛?/span>fch錛変笂鐨勫彾瀛愭暟鍜屽厔寮燂紙nsib錛夊瓙鏍?wèi)涓婂彾缁撶偣涓曨C箣鍜屻€?/span>

銆€銆€typedef struct node

銆€銆€{ElemType data;//鏁版嵁鍩?/span>

銆€銆€struct node *fch, *nsib;//瀛╁瓙涓庡厔寮熷煙 }*Tree;

銆€銆€int Leaves (Tree t)

銆€銆€//璁＄畻浠ュ瀛?/span>-鍏勫紵琛ㄧず娉曞瓨鍌ㄧ殑媯灄鐨勫彾瀛愭暟

銆€銆€{if(t)

銆€銆€if(t->fch==null) //鑻ョ粨鐐規(guī)棤瀛╁瓙錛屽垯璇ョ粨鐐瑰繀鏄彾瀛?/span>

銆€銆€return(1+Leaves(t->nsib)); //榪斿洖鍙跺瓙緇撶偣鍜屽叾鍏勫紵瀛愭爲(wèi)涓殑鍙跺瓙緇撶偣鏁?/span>

銆€銆€else return (Leaves(t->fch)+Leaves(t->nsib)); //瀛╁瓙瀛愭爲(wèi)鍜屽厔寮熷瓙鏍?wèi)涓彾瀛愭曨C箣鍜?/span>

銆€銆€}//緇撴潫Leaves

銆€銆€

銆€銆€

銆€銆€2錛庡亣瀹氱敤涓や釜涓€緇存暟緇?/span>L[N]鍜?/span>R[N]浣滀負(fù)鏈?/span>N涓粨鐐?/span>1錛?/span>2,鈥︼紝 N鐨勪簩鍏冩爲(wèi)鐨勫瓨鍌ㄧ粨鏋勩€?/span>L[i]鍜?/span>R[i]鍒嗗埆鎸囩ず緇撶偣 i鐨勫乏鍎垮瓙鍜屽彸鍎垮瓙錛?/span>L[i]=0錛?/span>R[i]=0錛夎〃紺?/span>i鐨勫乏錛堝彸錛夊効瀛愪負(fù)絀恒€傝瘯鍐欎竴涓畻娉曪紝鐢?/span>L鍜?/span>R寤虹珛涓€涓竴緇存暟緇?/span>T[n]錛屼嬌T[i]瀛樻斁緇撶偣i鐨勭埗浜詫紱鐒跺悗鍐嶅啓涓€涓垽鍒粨鐐?/span>U鏄惁涓虹粨鐐?/span>V鐨勫悗浠ｇ殑綆楁硶銆傘€?a target="_blank">鍝堝皵婊ㄥ伐涓氬ぇ瀛?/a> 1999 涓?/span> (14鍒?/span>)銆?/span>

聽聽聽 銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€[棰樼洰鍒嗘瀽]鐢辨寚紺虹粨鐐?/span>i 宸﹀効瀛愬拰鍙沖効瀛愮殑涓や釜涓€緇存暟緇?/span>L[i]鍜?/span>R[i]錛屽緢瀹規(guī)槗寤虹珛鎸囩ず緇撶偣i 鐨勫弻浜茬殑涓€緇存暟緇?/span>T[i]錛屾牴鎹?/span>T鏁扮粍錛屽垽鏂粨鐐?/span>U鏄惁鏄粨鐐?/span>V鍚庝唬鐨勭畻娉曪紝杞負(fù)鍒ゆ柇緇撶偣V鏄惁鏄粨鐐?/span>U鐨勭鍏堢殑闂銆?/span>

銆€銆€int Generation (int U,V,N,L[],R[],T[])

銆€銆€//L[]鍜?/span>R[]鏄惈鏈?/span>N涓厓绱犱笖鎸囩ず浜屽弶鏍?wèi)缁撶?/span>i宸﹀効瀛愬拰鍙沖効瀛愮殑涓€緇存暟緇勶紝

銆€銆€//鏈畻娉曟嵁姝ゅ緩绔嬬粨鐐?/span>i鐨勫弻浜叉暟緇?/span>T錛屽茍鍒ゆ柇緇撶偣U鏄惁鏄粨鐐?/span>V鐨勫悗浠ｃ€?/span>

銆€銆€{for(i=1;i<=N;i++) T[i]=0; //T鏁扮粍鍒濆鍖?/span>

銆€銆€for (i=1;i<=N;i++) //鏍規(guī)嵁L鍜?/span>R濉啓T

銆€銆€if(L[i]!=0) T[L[i]]=i; //鑻ョ粨鐐?/span>i鐨勫乏瀛愬コ鏄?/span>L錛屽垯緇撶偣L鐨勫弻浜叉槸緇撶偣i

銆€銆€for(i=1;i<=N;i++)

銆€銆€if (R[i]!=0) T[R[i]]=i; //i鐨勫彸瀛愬コ鏄?/span>r錛屽垯r鐨勫弻浜叉槸i

銆€銆€int parent=U; //鍒ゆ柇U鏄惁鏄?/span>V鐨勫悗浠?/span>

銆€銆€while (parent!=V && parent!=0) parent=T[parent];

銆€銆€if (parent==V){printf(鈥滅粨鐐?/span>U鏄粨鐐?/span>V鐨勫悗浠ｂ€?/span>);return(1);}

銆€銆€else{ printf(鈥滅粨鐐?/span>U涓嶆槸緇撶偣V 鐨勫悗浠ｂ€?/span>);return(0);}

銆€銆€}緇撴潫Generation