C++基于遞歸算法解決漢諾塔問題與樹的遍歷功能示例
本文實(shí)例講述了C++基于遞歸算法解決漢諾塔問題與樹的遍歷功能。分享給大家供大家參考，具體如下：
遞歸是把問題轉(zhuǎn)化為規(guī)模縮小的同類問題，然后迭代調(diào)用函數(shù)（或過程）求得問題的解。遞歸函數(shù)就是直接或間接調(diào)用自身的函數(shù)。
遞歸兩要素：遞歸關(guān)系和遞歸邊界(終止條件)，遞歸關(guān)系確定了迭代的層次結(jié)構(gòu)，需要深入了解并分解問題；終止條件保證了程序的有窮性。
遞歸的應(yīng)用有很多，常見的包括：階乘運(yùn)算、斐波那契數(shù)列、漢諾塔、數(shù)的遍歷，還有大名鼎鼎的快排等等。理論上，遞歸問題都可以由多層循環(huán)來實(shí)現(xiàn)。遞歸的每次調(diào)用都會消耗一定的?？臻g，效率要稍低于循環(huán)實(shí)現(xiàn)，但遞歸使函數(shù)更加簡潔，極大地增加了程序的可讀性。這里介紹漢諾塔和樹的遍歷兩種應(yīng)用。
漢諾塔（hanoi）
有三根相鄰的柱子，標(biāo)號為A,B,C，A柱子上從下到上按金字塔狀疊放著n個不同大小的圓盤，要把所有盤子一個一個移動到柱子C上，并且每次移動同一根柱子上都不能出現(xiàn)大盤子在小盤子上方。
遞歸規(guī)則：先把a(bǔ)上的n-1個搬到b上，再把a(bǔ)上第n個搬到c，然后把b上的n-1個搬到c上；終止條件是n=0。
/*
*作者：侯凱
*說明：目標(biāo)：把n個盤子從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');
}
這樣程序便十分簡潔的實(shí)現(xiàn)了看似復(fù)雜的功能，下面再看一個經(jīng)典的問題：
遍歷二叉樹
二叉樹的遍歷是指從根節(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中的所有結(jié)點(diǎn)，使得每個結(jié)點(diǎn)被訪問一次且僅被訪問一次。遍歷方法有四種：前序遍歷（先訪問根節(jié)點(diǎn)，然后前序遍歷左子樹，最后前序遍歷右子樹）、中序遍歷（左子樹->根節(jié)點(diǎn)->右子樹）、后序遍歷（左子樹->右子樹->根節(jié)點(diǎn)）和層序遍歷（每一層自左向右，各層自上向下訪問）。
可見前三種遍歷方法的定義就體現(xiàn)了遞歸的思想，算法實(shí)現(xiàn)如下：
//前序遍歷
void PreorderTra(BiTree T)
{
if(T == NULL)
{
return;
}
printf("%c",T->data);//輸出結(jié)點(diǎn)數(shù)據(jù)，可更改為其他對結(jié)點(diǎn)的操作
PreorderTra(T->lchild);//前序遍歷左子樹
PreorderTra(T->rchild);//前序遍歷右子樹
}
//中序遍歷
void InorderTra(BiTree T)
{
if(T == NULL)
{
return;
}
InorderTra(T->lchild);//中序遍歷左子樹
printf("%c",T->data);//輸出結(jié)點(diǎn)數(shù)據(jù)，可更改為其他對結(jié)點(diǎn)的操作
InorderTra(T->rchild);//中序遍歷右子樹
}
//后序遍歷
void PostorderTra(BiTree T)
{
if(T == NULL)
{
return;
}
PostorderTra(T->lchild);//后序遍歷左子樹
PostorderTra(T->rchild);//后序遍歷右子樹
printf("%c",T->data);//輸出結(jié)點(diǎn)數(shù)據(jù)，可更改為其他對結(jié)點(diǎn)的操作
}
其中二叉樹的結(jié)構(gòu)如下：
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BitNode,*BiTree;
希望本文所述對大家C++程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要介紹了使用c語言獲取直播吧最近一周nba比賽信息的方法,需要的朋友可以參考下2014-04-04
這篇文章主要介紹了C++無法打開源文件bits/stdc++.h的問題以及解決方案,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要介紹了C++引用和結(jié)構(gòu)體，結(jié)構(gòu)體是我們自定義的復(fù)合類型，本質(zhì)上也是一種變量類型，所以一樣可以使用引用，下面來看看文章內(nèi)容詳細(xì)介紹,需要的朋友可以參考一下2021-11-11
QT中QTableWidget加載大量數(shù)據(jù)不卡頓的解決
本文主要介紹了QT中QTableWidget加載大量數(shù)據(jù)不卡頓的解決，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
這篇文章主要為大家詳細(xì)介紹了C語言圖書管理系統(tǒng)課程設(shè)計(jì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C++常用語句簡介，文章將要介紹的常用語句有聲明變量、賦值語句、cin、cout語句、庫函數(shù)、自定義函數(shù),需要的朋友可以參考一下，希望對你有所幫助2021-11-11
C++空指針void是一種通用指針類型，可以指向任何類型的數(shù)據(jù)或?qū)ο蟆Ｋ魂P(guān)心指向的數(shù)據(jù)或?qū)ο蟮念愋?，只關(guān)心指針本身的地址，在使用void指針時，需要將其轉(zhuǎn)換為特定類型的指針，以便對其進(jìn)行操作或訪問其值，本文就給大家介紹一下C++空指針void的使用方法2023-06-06
Qt通過三種形式提供了對線程的支持，本文主要介紹了Qt5多線程編程的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
下面小編就為大家?guī)硪黄獪\談C語言函數(shù)調(diào)用參數(shù)壓棧的相關(guān)問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-10-10
std::sort函數(shù)是C++標(biāo)準(zhǔn)庫中常用的排序函數(shù)之一,它可以對各種類型的序列進(jìn)行排序,本文就來介紹一下C++中std::sort函數(shù)介紹和使用場景,感興趣的可以了解一下2024-02-02