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

1錛庡凡鐭ヤ竴鍏鋒湁n涓粨鐐圭殑浜屽弶鏍?wèi)鐨勪腑搴忛亶鍘嗗簭鍒椾笌鍚庡簭閬嶅巻搴忓垪鍒嗗埆瀛樻斁浜庢暟缁?/span>IN[1錛?/span>n]鍜?/span>POST[1錛?/span>n]涓紝錛堣璇ヤ簩鍙夋爲(wèi)鍚勭粨鐐圭殑鏁版嵁鍊煎潎涓嶇浉鍚岋級(jí)銆傝鍐欎竴寤虹珛璇ヤ簩鍙夋爲(wèi)鐨勪簩鍙夐摼琛ㄧ粨鏋勭殑闈為€掑綊綆楁硶銆傝浜屽弶閾捐〃鐨勯摼緇撶偣緇撴瀯涓?/span>(lchild,data,rchild)錛屽叾涓?/span>data涓烘暟鎹煙錛?/span>lchild涓?/span>rhild鍒嗗埆涓烘寚鍚戣緇撶偣宸︺€佸彸瀛╁瓙鐨勬寚閽堝煙錛堝綋瀛╁瓙緇撶偣涓嶅瓨鍦ㄦ椂錛岀浉搴旀寚閽堝煙涓虹┖錛岀敤nil琛ㄧず錛夈€傘€?a target="_blank">鍖椾含鑸┖鑸ぉ澶у 1998 鍏?/span> (15鍒?/span>)銆?/span>
銆€銆€銆愬弬鑰冪瓟妗堛€?/font>
銆€銆€[棰樼洰鍒嗘瀽]鐭ヤ簩鍙夋爲(wèi)涓簭搴忓垪涓庡悗搴忓簭鍒楋紝絎?/span>30棰樹(shù)互閫掑綊綆楁硶寤虹珛浜?jiǎn)浜屽弶鏍?wèi)錛屾湰棰樻槸闈為€掑綊綆楁硶銆?/span>
銆€銆€void InPostCreat(ElemType IN[],POST[],int l1,h1,l2,h2)
銆€銆€//鐢變簩鍙夋爲(wèi)鐨勪腑搴忓簭鍒?/span>IN[]鍜屽悗搴忓簭鍒?/span>POST[]寤虹珛浜屽弶鏍?wèi)锛?/span>l1,h1鍜?/span>l2,h2鍒嗗埆鏄腑搴忓簭鍒楀拰
銆€銆€//鍚庡簭搴忓垪絎竴鍜屾渶鍚庡厓绱犵殑涓嬫爣錛屽垵濮嬭皟鐢ㄦ椂錛?/span>l1=l2=1,h1=h2=n銆?/span>
銆€銆€{typedef struct {int l1,h1,l2,h2; BiTree t; }node;
銆€銆€node s[],p;//s涓烘爤錛屽閲忚凍澶熷ぇ
銆€銆€BiTree bt=(BiTree)malloc(sizeof(BiNode)); int top=0,i;
銆€銆€p.l1=l1; p.h1=h1; p.l2=l2; p.h2=h2; p.t=bt; s[++top]=p;//鍒濆鍖?/span>
銆€銆€while(top>0)
銆€銆€{p=s[top--]; bt=p.t; l1=p.l1; h1=p.h1; l2=p.l2; h2=p.h2;//鍙栧嚭鏍堥《鏁版嵁
銆€銆€for(i=l1;i<=h1;i++) if(IN[i]==POST[h2]) break;//鍦ㄤ腑搴忓簭鍒椾腑鏌ョ瓑浜?/span>POST[h2]鐨勭粨鐐?/span>
銆€銆€bt->data=POST[h2]; //鏍圭粨鐐圭殑鍊?/span>
銆€銆€if(i==l1) bt->lchild=null; //bt鏃犲乏瀛愭爲(wèi)
銆€銆€else //灝嗗緩绔嬪乏瀛愭爲(wèi)鐨勬暟鎹叆鏍?/span>
銆€銆€{bt->lchild=(BiTree)malloc(sizeof(BiNode)); p.t=bt->lchild;
銆€銆€p.l1=l1; p.h1=i-1; p.l2=l2; p.h2=l2+i-l1-1; s[++top]=p; }
銆€銆€if(i==h1) bt->rchild=null; //bt鏃犲彸瀛愭爲(wèi)
銆€銆€else {bt->rchild=(BiTree)malloc(sizeof(BiNode)); p.t=bt->rchild;
銆€銆€p.l1=i+1; p.h1=h1; p.l2=l2+i-l1; p.h2=h2-1; s[++top]=p; }//鍙沖瓙鏍?wèi)鏁版嵁鍏ユ?/span>
銆€銆€}// while(top>0)
銆€銆€}緇撴潫InPostCreat