7-17 漢諾塔的非遞歸實(shí)現(xiàn) (25分)

7-17 漢諾塔的非遞歸實(shí)現(xiàn) (25分)

借助堆棧以非遞歸（循環(huán)）方式求解漢諾塔的問題（n, a, b, c），即將N個(gè)盤子從起始柱（標(biāo)記為“a”）通過借助柱（標(biāo)記為“b”）移動(dòng)到目標(biāo)柱（標(biāo)記為“c”），并保證每個(gè)移動(dòng)符合漢諾塔問題的要求。

輸入格式:

輸入為一個(gè)正整數(shù)N，即起始柱上的盤數(shù)。

輸出格式:

每個(gè)操作（移動(dòng)）占一行，按柱1 -> 柱2的格式輸出。

輸入樣例:

3

輸出樣例:

a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

解釋：數(shù)字代表盤的大小。

對(duì)盤子的操作順序，就是中序遍歷這個(gè)完全二叉樹，可以通過遍歷普通的鏈接存儲(chǔ)的二叉樹那樣的非遞歸遍歷。那我們繼續(xù)分析，如何才能使用堆棧做一種更簡(jiǎn)單的遍歷。
以上面的圖片作為例子，我們做如下思考。
1、在這棵完全二叉樹種，葉子節(jié)點(diǎn)都是1。
2、3進(jìn)入堆棧之后出棧不能直接輸出，需要等待其子樹都產(chǎn)生結(jié)束，并且左子樹都輸出，方可輸出。同理2也是，只有1為葉子節(jié)點(diǎn)不需要產(chǎn)生后代。要實(shí)現(xiàn)產(chǎn)生后代并且等左子樹輸出之后再輸出本節(jié)點(diǎn)，必須讓其產(chǎn)生后代進(jìn)棧（進(jìn)棧的原因：因?yàn)楹蟠?jié)點(diǎn)可能依然不是葉子節(jié)點(diǎn)），并且本節(jié)點(diǎn)也得進(jìn)棧，因?yàn)槠漭敵鲰樞蚴牵鹤?---根—右，其進(jìn)展順序應(yīng)該是：右—根---左，并且我們得標(biāo)記其已經(jīng)產(chǎn)生過后代，等再次出棧到本節(jié)點(diǎn)時(shí)直接輸出。
3、根據(jù)第一、二條我們知道，如果碰到葉子節(jié)點(diǎn)（不能產(chǎn)生后代）或者已經(jīng)產(chǎn)生過后代的節(jié)點(diǎn)，我們直接輸出即可，那么我們就可以節(jié)省存儲(chǔ)空間不需要單獨(dú)設(shè)置其blag，來標(biāo)記是否產(chǎn)生過子節(jié)點(diǎn)，直接將產(chǎn)生子節(jié)點(diǎn)的節(jié)點(diǎn)層數(shù)修改為1即可。
4、再跟據(jù)上面例子的圖片，對(duì)于根節(jié)點(diǎn)n=3，我們需要做的是a->c，根據(jù)遞歸結(jié)構(gòu)的代碼我們可以知道其左子樹上的2節(jié)點(diǎn)應(yīng)該是a->b，右子樹上的2節(jié)點(diǎn)應(yīng)該是b->c。同理我們分析一下當(dāng)遍歷到左子樹上的2節(jié)點(diǎn)時(shí)，其目的是a->b,那么左邊的1節(jié)點(diǎn)就應(yīng)該是a->c,右邊的節(jié)點(diǎn)時(shí)c->b。也就是當(dāng)我們遍歷到某節(jié)點(diǎn)時(shí)，假設(shè)本節(jié)點(diǎn)應(yīng)該做的操作是：起點(diǎn)柱->終點(diǎn)柱。那么其左子節(jié)點(diǎn)就應(yīng)該是：起點(diǎn)柱->借助柱；其右子節(jié)點(diǎn)就應(yīng)該是：借助柱->終點(diǎn)柱。如此，在產(chǎn)生子代的過程并修改子代所要做的移動(dòng)即可。

非遞歸代碼：

#include <iostream>
#include <bits/stdc++.h>
using namespace std; 
typedef struct node
{
    int layer;
    char start;
    char mid;
    char des;
}Node;
node N,t;
int main()
{
    int n;
    cin>>n;
    stack<Node> St;
    N.layer=n;N.start='a';N.mid='b';N.des='c';
    St.push(N);
    while(!St.empty())
    {
        N=St.top();St.pop();
	if(N.layer==1)
	    printf("%c -> %c\n",N.start,N.des);
	else
	{
	    t.layer=N.layer-1;t.start=N.mid;t.des=N.des;t.mid=N.start;
	    St.push(t);
	    t.layer=1;t.start=N.start;t.mid=N.mid;t.des=N.des;
	    St.push(t);
	    t.layer=N.layer-1;t.start=N.start;t.des=N.mid;t.mid=N.des;
	    St.push(t);
	}
    } 
    return 0;
}

遞歸代碼：

#include<stdio.h>
void han(int n,char a,char b,char c)
{
	if(n==1)
                printf("%c -> %c\n",a,c);
	else
	{
		han(n-1,a,c,b);
		printf("%c -> %c\n",a,c);
		han(n-1,b,a,c);
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	han(n,'a','b','c');
	return 0;
}