滿二叉樹的千絲萬(wàn)縷
漢諾塔(Tower of Hanoi)源于印度傳說(shuō)中，大梵天創(chuàng)造世界時(shí)造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。
漢諾塔遞歸算法
3階漢諾塔移動(dòng)步驟：
漢諾塔解法思路
一個(gè)規(guī)模為n的問(wèn)題，可以拆成互相獨(dú)立且與原問(wèn)題形式相同的子問(wèn)題的問(wèn)題，可以采用遞歸方式解決子問(wèn)題，然后將各個(gè)子問(wèn)題的解合并得到原問(wèn)題的解（分而治之思想）。
理解過(guò)程
如圖，3階的一共需要七步，
因?yàn)楸P子3是最大的，所以所有盤子都可放在它上面，所以我們可以忽略盤子3，既是把“前三步”看做一個(gè)整體，完成2階移動(dòng)即可，移動(dòng)目標(biāo)是從A移動(dòng)到B（偽C）；
接著執(zhí)行第四步，從A移到C，此時(shí)最大的盤就完成移動(dòng)了，因?yàn)槭亲畲螅运斜P子都可以移到C，可以忽略盤子3，此時(shí)，后續(xù)的操作可以將3階看成2階來(lái)處理了；
“前三步”將盤子1和2，從A移到B了，托盤A和托盤B是相對(duì)來(lái)說(shuō)的，此時(shí)的托盤B可以看做是托盤A，所以“后三步”2階移動(dòng)和普通的2階移動(dòng)步驟一樣，移動(dòng)目標(biāo)是B（偽A）到C。
從上面分析可以知道，所有的移動(dòng)都是從“A”移動(dòng)到“C”，只是第一大步和最后一大步是要交換位置，分別是C交換成B、B交換從A（看代碼不太懂時(shí)，回來(lái)看這里）
當(dāng)n=1時(shí)，只需托盤A直接移到托盤C（這是遞歸問(wèn)題的出口）； 當(dāng)n>1時(shí)，需要借助另一托盤來(lái)移動(dòng)，將n個(gè)圓盤由A移到C上可以分解為以下幾個(gè)步驟： (1) 將A上的n-1個(gè)圓盤，借助C，從A移到B上; (2) 把A上第n個(gè)圓盤，直接從A移到C上; (3) 將B上的n-1個(gè)圓盤，借助A，從B移到C上。
遞歸方式實(shí)現(xiàn)的漢諾塔（Java版）：
public class Hanoi { ? ?// 階數(shù)
? ?private static int n = 4; ? ?//驗(yàn)證漢諾塔移動(dòng)次數(shù)
? ?private static int sum=0; ? ?public static void main(String[] args) {
? ? ? ?System.out.println(String.format("%s層漢諾塔的移動(dòng)順序：", n));
? ? ? ?move(n, 'A','B','C');
? ? ? ?System.out.println("漢諾塔移動(dòng)次數(shù)："+sum);
? ?} ? ?/**
? ? * (n-1) A -> B
? ? * ? n ? A -> C
? ? * (n-1) B -> C
? ? *
? ? * 結(jié)束條件為：當(dāng)n=1 時(shí)， A -> C
? ? */
? ?public static void move(int n,char A, char B, char C) { ? ? ? ?if(n==1) {
? ? ? ? ? ?System.out.println(A + " -> " + C);
? ? ? ? ? ?sum++;
? ? ? ?} ? ? ? ?else {
? ? ? ? ? ?move(n-1, A, C, B);//每次都是輸出A->C，所以要看到A->B，就需要將B和C交換
? ? ? ? ? ?if(n==Hanoi.n)
? ? ? ? ? ? ? ?System.out.println("前面完成(n-1)層：從A移動(dòng)到B");
? ? ? ? ? ?System.out.println(A + " -> " + C);
? ? ? ? ? ?sum++; ? ? ? ? ? ?if(n==Hanoi.n)
? ? ? ? ? ? ? ?System.out.println("完成第(n)層：從A移動(dòng)到C");
? ? ? ? ? ?move(n-1, B, A, C);//每次都是輸出A->C，所以要看到B->C，就需要將A和B交換
? ? ? ? ? ?if(n==Hanoi.n)
? ? ? ? ? ? ? ?System.out.println("前面完成(n-1)層：從B移動(dòng)到C");
? ? ? ?}
? ?}
}
執(zhí)行結(jié)果：
3層漢諾塔的移動(dòng)順序：
A -> C
A -> B
C -> B
前面完成(n-1)層：從A移動(dòng)到B
A -> C
完成第(n)層：從A移動(dòng)到C
B -> A
B -> C
A -> C
前面完成(n-1)層：從B移動(dòng)到C
漢諾塔移動(dòng)次數(shù)：7
先完成(n-1)層：從A移動(dòng)到B，
再完成第(n)層：從A移動(dòng)到C，
最后完成(n-1)層：從B移動(dòng)到C。
通過(guò)數(shù)學(xué)推導(dǎo)漢諾塔移動(dòng)次數(shù)
遞歸算法可以通過(guò)遞歸式的方式去推導(dǎo)證明，現(xiàn)在通過(guò)遞歸式推導(dǎo)漢諾塔移動(dòng)次數(shù)。
假定n是盤子的數(shù)量，T(n)是移動(dòng)n個(gè)圓盤的移動(dòng)次數(shù)。
當(dāng)n=1時(shí)，T(1)=1
當(dāng)n=2時(shí)，T(2)=2T(1)+1
當(dāng)n=3時(shí)，T(3)=2T(2)+1
得漢諾塔遞歸式：
由遞歸式求n階漢諾塔移動(dòng)次數(shù)：
由遞歸式可知：
又因當(dāng)n=1時(shí)，T(1)=1，得：
解得n階漢諾塔移動(dòng)次數(shù)為：?次。
漢諾塔與二進(jìn)制
公式
這就像是n位二進(jìn)制的和，最終得到n位二進(jìn)制的最大值（全1）
所以有，n階漢諾塔移動(dòng)次數(shù)等于n位二進(jìn)制得最大值，如：4階漢諾塔移動(dòng)次數(shù)為
每個(gè)盤子的移動(dòng)次數(shù)，觀察下圖：
如圖可知，每個(gè)盤子移動(dòng)總次數(shù)剛好相反，
所以，n階漢諾塔的第i個(gè)盤子總的移動(dòng)次數(shù)為：
3階漢諾塔圖解與二進(jìn)制關(guān)系
漢諾塔與滿二叉樹
遞歸算法會(huì)有相對(duì)應(yīng)的遞歸樹，而漢諾塔的遞歸樹剛好是滿二叉樹，即所有分支結(jié)點(diǎn)都有兩個(gè)葉子結(jié)點(diǎn)。
調(diào)整漢諾塔對(duì)算法代碼的輸出信息后：
public class Hanoi { ? ?// 階數(shù)
? ?private static int n = 3; ? ?public static void main(String[] args) {
? ? ? ?System.out.println(String.format("%s層漢諾塔的移動(dòng)順序：", n)); ? ? ? ?int sum = moveTree(n, 'A','B','C');
? ? ? ?System.out.println("漢諾塔移動(dòng)次數(shù)："+sum);
? ?} ? ?/**
? ? * 漢諾塔與滿二叉樹
? ? * (n-1) A -> B
? ? * ? n ? A -> C
? ? * (n-1) B -> C
? ? *
? ? * 結(jié)束條件為：當(dāng)n=1 時(shí)， A -> C
? ? */
? ?public static int moveTree(int n,char A, char B, char C) { ? ? ? ?if(n==1)
? ? ? ? ? ?System.out.println(String.format("第 %s 層(葉子節(jié)點(diǎn))：%s -> %s",n, A, C)); ? ? ? ?else {
? ? ? ? ? ?moveTree(n-1, A, C, B);//每次都是輸出A->C，所以要看到A->B，就需要將B和C交換
? ? ? ? ? ?if(n==Hanoi.n)
? ? ? ? ? ? ? ?System.out.println(String.format("第 %s 層(根節(jié)點(diǎn))：%s -> %s", n, A, C)); ? ? ? ? ? ?else
? ? ? ? ? ? ? ?System.out.println(String.format("第 %s 層(分支結(jié)點(diǎn))：%s -> %s", n, A, C));
? ? ? ? ? ?moveTree(n-1, B, A, C);//每次都是輸出A->C，所以要看到B->C，就需要將A和B交換
? ? ? ?} ? ? ? ?//漢諾塔的移動(dòng)次數(shù)為: 2^n-1
? ? ? ?return (int) Math.pow(2, n)-1;
? ?}
}
3層漢諾塔的移動(dòng)順序：
第 1 層(葉子節(jié)點(diǎn))：A -> C
第 2 層(分支結(jié)點(diǎn))：A -> B
第 1 層(葉子節(jié)點(diǎn))：C -> B
第 3 層(根節(jié)點(diǎn))：A -> C
第 1 層(葉子節(jié)點(diǎn))：B -> A
第 2 層(分支結(jié)點(diǎn))：B -> C
第 1 層(葉子節(jié)點(diǎn))：A -> C
漢諾塔移動(dòng)次數(shù)：7
3階漢諾塔對(duì)應(yīng)的滿二叉樹：
3階漢諾塔的移動(dòng)步驟為滿二叉樹的中序遍歷：AC、AB、CB、AC、BA、BC、AC
從輸出結(jié)果可以看到，漢諾塔盤子編號(hào)對(duì)應(yīng)滿二叉樹自底向上計(jì)算的層號(hào)，如：1號(hào)盤子的移動(dòng)對(duì)應(yīng)是葉子節(jié)點(diǎn)，最底層盤子對(duì)應(yīng)根節(jié)點(diǎn)。
