C++基于遞歸算法解決漢諾塔問(wèn)題與樹(shù)的遍歷功能示例
本文實(shí)例講述了C++基于遞歸算法解決漢諾塔問(wèn)題與樹(shù)的遍歷功能。分享給大家供大家參考，具體如下：
遞歸是把問(wèn)題轉(zhuǎn)化為規(guī)?？s小的同類問(wèn)題，然后迭代調(diào)用函數(shù)（或過(guò)程）求得問(wèn)題的解。遞歸函數(shù)就是直接或間接調(diào)用自身的函數(shù)。
遞歸兩要素：遞歸關(guān)系和遞歸邊界(終止條件)，遞歸關(guān)系確定了迭代的層次結(jié)構(gòu)，需要深入了解并分解問(wèn)題；終止條件保證了程序的有窮性。
遞歸的應(yīng)用有很多，常見(jiàn)的包括：階乘運(yùn)算、斐波那契數(shù)列、漢諾塔、數(shù)的遍歷，還有大名鼎鼎的快排等等。理論上，遞歸問(wèn)題都可以由多層循環(huán)來(lái)實(shí)現(xiàn)。遞歸的每次調(diào)用都會(huì)消耗一定的?？臻g，效率要稍低于循環(huán)實(shí)現(xiàn)，但遞歸使函數(shù)更加簡(jiǎn)潔，極大地增加了程序的可讀性。這里介紹漢諾塔和樹(shù)的遍歷兩種應(yīng)用。
漢諾塔（hanoi）
有三根相鄰的柱子，標(biāo)號(hào)為A,B,C，A柱子上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤，要把所有盤子一個(gè)一個(gè)移動(dòng)到柱子C上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤子在小盤子上方。
遞歸規(guī)則：先把a(bǔ)上的n-1個(gè)搬到b上，再把a(bǔ)上第n個(gè)搬到c，然后把b上的n-1個(gè)搬到c上；終止條件是n=0。
/*
*作者：侯凱
*說(shuō)明：目標(biāo)：把n個(gè)盤子從a往c搬
*/
void hanoi(int n, char a,char b,char c)
{
if(n>0)
{
hanoi(n-1,a,c,b);
cout<<a<<"->"<<c<<endl;
hanoi(n-1,b,a,c);
}
}
void main()
{
hanoi(4,'A','B','C');
}
這樣程序便十分簡(jiǎn)潔的實(shí)現(xiàn)了看似復(fù)雜的功能，下面再看一個(gè)經(jīng)典的問(wèn)題：
遍歷二叉樹(shù)
二叉樹(shù)的遍歷是指從根節(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。遍歷方法有四種：前序遍歷（先訪問(wèn)根節(jié)點(diǎn)，然后前序遍歷左子樹(shù)，最后前序遍歷右子樹(shù)）、中序遍歷（左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)）、后序遍歷（左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)）和層序遍歷（每一層自左向右，各層自上向下訪問(wèn)）。
可見(jiàn)前三種遍歷方法的定義就體現(xiàn)了遞歸的思想，算法實(shí)現(xiàn)如下：
//前序遍歷
void PreorderTra(BiTree T)
{
if(T == NULL)
{
return;
}
printf("%c",T->data);//輸出結(jié)點(diǎn)數(shù)據(jù)，可更改為其他對(duì)結(jié)點(diǎn)的操作
PreorderTra(T->lchild);//前序遍歷左子樹(shù)
PreorderTra(T->rchild);//前序遍歷右子樹(shù)
}
//中序遍歷
void InorderTra(BiTree T)
{
if(T == NULL)
{
return;
}
InorderTra(T->lchild);//中序遍歷左子樹(shù)
printf("%c",T->data);//輸出結(jié)點(diǎn)數(shù)據(jù)，可更改為其他對(duì)結(jié)點(diǎn)的操作
InorderTra(T->rchild);//中序遍歷右子樹(shù)
}
//后序遍歷
void PostorderTra(BiTree T)
{
if(T == NULL)
{
return;
}
PostorderTra(T->lchild);//后序遍歷左子樹(shù)
PostorderTra(T->rchild);//后序遍歷右子樹(shù)
printf("%c",T->data);//輸出結(jié)點(diǎn)數(shù)據(jù)，可更改為其他對(duì)結(jié)點(diǎn)的操作
}
其中二叉樹(shù)的結(jié)構(gòu)如下：
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BitNode,*BiTree;
希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。
相關(guān)文章
Qt利用QState狀態(tài)機(jī)實(shí)現(xiàn)控件互斥操作詳解
這篇文章主要為大家詳細(xì)介紹了Qt如何利用QState狀態(tài)機(jī)實(shí)現(xiàn)控件互斥操作，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-12-12
利用C語(yǔ)言玩轉(zhuǎn)魔方陣實(shí)例教程
這篇文章主要給大家介紹了關(guān)于利用C語(yǔ)言玩轉(zhuǎn)魔方陣的相關(guān)資料,文中詳細(xì)介紹了關(guān)于奇數(shù)魔方陣和4N 魔方陣的實(shí)現(xiàn)方法，通過(guò)示例代碼讓大家更好的參考學(xué)習(xí)，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-11-11
這篇文章主要介紹了C++多態(tài)實(shí)現(xiàn)方式詳情，多態(tài)是一種面向?qū)ο蟮脑O(shè)計(jì)思路，本身和C++不是強(qiáng)綁定的，其他語(yǔ)言當(dāng)中一樣有多態(tài)，只不過(guò)實(shí)現(xiàn)的方式可能有所不同。下面來(lái)一起了解更多詳細(xì)內(nèi)容吧2022-01-01
這篇文章主要介紹了C++ COM編程之接口背后的虛函數(shù)表,COM的背后,就是接口,而接口的背后，就是虛函數(shù)表,需要的朋友可以參考下2014-10-10
如何實(shí)現(xiàn)一定概率選中某一個(gè)字母
本篇文章是對(duì)如何實(shí)現(xiàn)一定概率選中某一個(gè)字母的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C語(yǔ)言實(shí)現(xiàn)線性表的基本操作詳解
線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列，這篇文章帶你學(xué)習(xí)如何通過(guò)C語(yǔ)言實(shí)現(xiàn)線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)2021-11-11![C++手?jǐn)]智能指針的教程分享](http://img.jbzj.com/images/xgimg/bcimg6.png)
在前文中小編為大家介紹了C++智能指針的一些使用方法和基本原理，所以本文就來(lái)自己動(dòng)手，從0到1實(shí)現(xiàn)一下自己的unique_ptr和shared_ptr吧2023-05-05
C語(yǔ)言字符串函數(shù)操作(strlen,strcpy,strcat,strcmp)詳解
大家好，本篇文章主要講的是C語(yǔ)言字符串函數(shù)操作（strlen,strcpy,strcat,strcmp）詳解，感興趣的同學(xué)趕快來(lái)看一看吧2021-12-12
在C++中,標(biāo)準(zhǔn)庫(kù)本身已經(jīng)對(duì)左移運(yùn)算符<<和右移運(yùn)算符>>分別進(jìn)行了重載,使其能夠用于不同數(shù)據(jù)的輸入輸出,本節(jié)以前面的?complex?類為例來(lái)演示輸入輸出運(yùn)算符的重載,需要的朋友可以參考下2023-09-09
C語(yǔ)言編寫基于TCP和UDP協(xié)議的Socket通信程序示例
這篇文章主要介紹了C語(yǔ)言編寫基于TCP和UDP協(xié)議的Socket通信程序示例,其中TCP的客戶端與服務(wù)器端采用多線程實(shí)現(xiàn),需要的朋友可以參考下2016-03-03