數據結構簡述遞歸演算法的設計步驟

㈠ Java數據結構二叉樹深度遞歸調用演算法求內部演算法過程詳解

二叉樹
1
2 3
4 5 6 7
這個二叉樹的深度是3，樹的深度是最大結點所在的層，這里是3.

應該計算所有結點層數，選擇最大的那個。

根據上面的二叉樹代碼，遞歸過程是：

f(1)=f(2)+1 > f(3) +1 ? f(2) + 1 : f(3) +1

f(2) 跟f(3)計算類似上面，要計算左右結點，然後取大者

所以計算順序是f(4.left) = 0, f(4.right) = 0

f(4) = f(4.right) + 1 = 1

然後計算f(5.left) = 0,f(5.right) = 0

f(5) = f(5.right) + 1 =1

f(2) = f(5) + 1 =2

f(1.left) 計算完畢，計算f(1.right) f(3) 跟計算f(2)的過程一樣。

得到f(3) = f(7) +1 = 2

f(1) = f(3) + 1 =3

if(depleft>depright){
returndepleft+1;
}else{
returndepright+1;
}

只有left大於right的時候採取left +1，相等是取right

㈡ 鏁版嵁緇撴瀯涓庣畻娉曞ぇ瀛︽病瀛︽槑鐧界殑鏉

鏁版嵁緇撴瀯澶у︾敓鎬庝箞瀛︽暟鎹緇撴瀯?浜斿ぇ鑴夌粶鍥

鏁版嵁緇撴瀯

鏁版嵁緇撴瀯鏄璁＄畻鏈哄瓨鍌ㄣ佺粍緇囨暟鎹鐨勬柟寮忋傛暟鎹緇撴瀯鏄鎸囩浉浜掍箣闂村瓨鍦ㄤ竴縐嶆垨澶氱嶇壒瀹氬叧緋葷殑鏁版嵁鍏冪礌鐨勯泦鍚堛傞氬父鎯呭喌涓嬶紝綺懼績閫夋嫨鐨勬暟鎹緇撴瀯鍙浠ュ甫鏉ユ洿楂樼殑榪愯屾垨鑰呭瓨鍌ㄦ晥鐜囥

鐩稿叧鏈璇

鍦ㄦ暟鎹緇撴瀯涓庣畻娉曚腑錛屾暟鎹銆佹暟鎹瀵硅薄銆佹暟鎹鍏冪礌銆佹暟鎹欏規湁涓浜涘悓瀛︽悶涓嶆噦鍏朵腑鐨勫叧緋匯傞氳繃鐢諱竴寮犲浘鏉ユ崑涓鎹:

鏁版嵁涓夎佺礌

鏁版嵁緇撴瀯涓夎佺礌鍒嗕負:閫昏緫緇撴瀯銆佸瓨鍌ㄧ粨鏋勩佹暟鎹鐨勮繍綆椼傞昏緫緇撴瀯鍒嗕負綰挎х粨鏋勫拰闈炵嚎鎬х粨鏋;瀛樺偍緇撴瀯鍒嗕負欏哄簭瀛樺偍銆侀摼寮忓瓨鍌ㄣ佺儲寮曞瓨鍌ㄣ佹暎鍒楀瓨鍌:鏁版嵁榪愮畻鍖呮嫭瀹氫箟鍜屽疄鐜般

鏁版嵁緇撴瀯瀛︿範姝ラ

鍗曢摼琛(甯﹀ご緇撶偣銆佷笉甯﹀ご緇撶偣)璁捐′笌瀹炵幇(澧炲垹鏀規煡)錛屽弻閾捐〃璁捐′笌瀹炵幇

鏍堣捐′笌瀹炵幇(鏁扮粍鍜岄摼琛)錛岄槦鍒楄捐′笌瀹炵幇(鏁扮粍鍜岄摼琛)

浜屽張鏍戞傚康瀛︿範錛屼簩鍙堟爲鍓嶅簭銆佷腑搴忋佸悗搴忛亶鍘嗛掑綊銆侀潪閫掑綊瀹炵幇 錛屽眰搴忛亶鍘

浜屽張鎺掑簭鏍戣捐′笌瀹炵幇(鎻掑叆鍒犻櫎)

鍫(浼樺厛闃熷垪銆佸爢鎺掑簭)

AVL(騫寵)鏍戣捐′笌瀹炵幇(鍥涚嶈嚜鏃嬫柟寮忕悊瑙ｅ疄鐜)

浼稿睍鏍戙佺孩榛戞爲鍘熺悊姒傚康鐞嗚В

B銆丅+鍘熺悊姒傚康鐞嗚В

鍝堝か鏇兼爲鍘熺悊姒傚康鐞嗚В(璐蹇冪瓥鐣)

鍝堝笇(鏁ｅ垪琛)鍘熺悊姒傚康鐞嗚В(鍑犵嶈В鍐沖搱甯屽啿紿佹柟寮)

騫舵煡闆/涓嶇浉浜ら泦鍚(浼樺寲鍜岃礬寰勫帇緙)

鍥捐烘嫇鎵戞帓搴

鍥捐篸fs娣卞害浼樺厛閬嶅巻銆乥fs騫垮害浼樺厛閬嶅巻

鏈鐭璺寰凞iikstra綆楁硶銆丗loyd綆楁硶銆乻pfa綆楁硶

鏈灝忕敓鎴愭爲prim綆楁硶銆乲ruskal綆楁硶

鍏朵粬鏁版嵁緇撴瀯綰挎墊爲銆佸悗緙鏁扮粍絳夌瓑

緇忓吀綆楁硶瀛︿範姝ラ

閫掑綊綆楁硶(奼傞樁涔樸佹枑娉㈤偅濂戙佹眽璇哄旈棶棰)

浜屽垎鏌ユ壘

鍒嗘不綆楁硶(蹇鎺掋佸綊騫舵帓搴忋佹眰鏈榪戠偣瀵圭瓑闂棰)

璐蹇冪畻娉(浣跨敤杈冨氾紝鍖洪棿閫夌偣闂棰橈紝鍖洪棿瑕嗙洊闂棰)

甯歌佸姩鎬佽勫垝(LCS(鏈闀垮叕鍏卞瓙搴忓垪) LIS(鏈闀誇笂鍗囧瓙搴忓垪)鑳屽寘闂棰樼瓑絳

鍥炴函綆楁硶(緇忓吀鍏鐨囧悗闂棰樸佸叏鎺掑垪闂棰)

浣嶈繍綆楀父瑙侀棶棰(鍙傝冨墤鎸噊ffer鍜孡eetCode闂棰)

蹇閫熷籙綆楁硶(蹇閫熸眰騫備箻銆佺煩闃靛揩閫熷籙)

kmp絳夊瓧絎︿覆鍖歸厤綆楁硶

涓鍒囧叾浠栨暟璁虹畻娉(嬈у嚑閲屽緱銆佹嫇灞曟у嚑閲屽緱銆佷腑鍥藉墿浣欏畾鐞嗙瓑絳)

㈢ 在計算機演算法中，迭代和遞歸是什麼意思它們有什麼區別

舉個例子：我想求1+2+3+4+..+100的值。
迭代的做法：從1到100，順著往下累加。1+2=3,3+3=6,6+4=10,10+5=15……
程序表示，
int i=1,sum=0;
while(i<=100){
sum = sum +i;
}
遞歸的做法：我要求1到100的累加值，如果我已經得到1到99的累加值，將這個值加上100就是1到100的累加值；要得到1到99的累加值，如果已經得到1到98的累加值，將這個值加上99，就是1到99的累加值……最後我要得到1到2的累加值，我如果得到1自身累加值，再加上2即可，1自身的累加值顯然就是1了。於是現在我們得到了1到2的累加值，將這個值加3就得到了1到3的累加值，……最後直到得到1到100的累加值。
程序表示，其中函數會調用自身，這就是遞歸方法的典型特徵
int GetSum(int n)
{
if(n<=0) return 0;
else return n+GetSum(n-1);
}

上述例子中，其實遞歸最後得到結果也是用迭代方法完成的，只是在程序的處理上直觀看不出來。兩者都能很好的完成計算任務，不同之處在於思維方式上，從而導致不同的計算方法：迭代是正向思維，從頭到尾思考問題；遞歸是逆向思維，他假設我們已經得到了部分結果(假設我已經知道了1到99的累加值，把這個值加上100我們就得到了1到100的累加值了)，從尾部追溯到頭部，從而讓問題簡化(當然這個例子中看不出來，這里只是方便理解，有興趣可以參考一下http://ke..com/view/568949.htm 斐波那契數列 的構造方法)。