欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++基于遞歸算法解決漢諾塔問題與樹的遍歷功能示例

 更新時間:2017年11月07日 11:06:26   作者:侯凱  
這篇文章主要介紹了C++基于遞歸算法解決漢諾塔問題與樹的遍歷功能,簡單描述了遞歸算法的原理,并結(jié)合實例形式分析了基于遞歸算法解決漢諾塔問題與數(shù)的遍歷相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了C++基于遞歸算法解決漢諾塔問題與樹的遍歷功能。分享給大家供大家參考,具體如下:

遞歸是把問題轉(zhuǎn)化為規(guī)??s小的同類問題,然后迭代調(diào)用函數(shù)(或過程)求得問題的解。遞歸函數(shù)就是直接或間接調(diào)用自身的函數(shù)。

遞歸兩要素:遞歸關(guān)系遞歸邊界(終止條件),遞歸關(guān)系確定了迭代的層次結(jié)構(gòu),需要深入了解并分解問題;終止條件保證了程序的有窮性。

遞歸的應(yīng)用有很多,常見的包括:階乘運(yùn)算、斐波那契數(shù)列、漢諾塔、數(shù)的遍歷,還有大名鼎鼎的快排等等。理論上,遞歸問題都可以由多層循環(huán)來實現(xiàn)。遞歸的每次調(diào)用都會消耗一定的??臻g,效率要稍低于循環(huán)實現(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');
}

這樣程序便十分簡潔的實現(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)了遞歸的思想,算法實現(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è)計有所幫助。

相關(guān)文章

  • Qt利用QState狀態(tài)機(jī)實現(xiàn)控件互斥操作詳解

    Qt利用QState狀態(tài)機(jī)實現(xiàn)控件互斥操作詳解

    這篇文章主要為大家詳細(xì)介紹了Qt如何利用QState狀態(tài)機(jī)實現(xiàn)控件互斥操作,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2022-12-12
  • 利用C語言玩轉(zhuǎn)魔方陣實例教程

    利用C語言玩轉(zhuǎn)魔方陣實例教程

    這篇文章主要給大家介紹了關(guān)于利用C語言玩轉(zhuǎn)魔方陣的相關(guān)資料,文中詳細(xì)介紹了關(guān)于奇數(shù)魔方陣和4N 魔方陣的實現(xiàn)方法,通過示例代碼讓大家更好的參考學(xué)習(xí),需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2017-11-11
  • C++多態(tài)實現(xiàn)方式詳情

    C++多態(tài)實現(xiàn)方式詳情

    這篇文章主要介紹了C++多態(tài)實現(xiàn)方式詳情,多態(tài)是一種面向?qū)ο蟮脑O(shè)計思路,本身和C++不是強(qiáng)綁定的,其他語言當(dāng)中一樣有多態(tài),只不過實現(xiàn)的方式可能有所不同。下面來一起了解更多詳細(xì)內(nèi)容吧
    2022-01-01
  • C++ COM編程之接口背后的虛函數(shù)表

    C++ COM編程之接口背后的虛函數(shù)表

    這篇文章主要介紹了C++ COM編程之接口背后的虛函數(shù)表,COM的背后,就是接口,而接口的背后,就是虛函數(shù)表,需要的朋友可以參考下
    2014-10-10
  • 如何實現(xiàn)一定概率選中某一個字母

    如何實現(xiàn)一定概率選中某一個字母

    本篇文章是對如何實現(xiàn)一定概率選中某一個字母的解決方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • C語言實現(xiàn)線性表的基本操作詳解

    C語言實現(xiàn)線性表的基本操作詳解

    線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。一個線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列,這篇文章帶你學(xué)習(xí)如何通過C語言實現(xiàn)線性表的順序存儲和鏈?zhǔn)酱鎯?/div> 2021-11-11
  • C++手?jǐn)]智能指針的教程分享

    C++手?jǐn)]智能指針的教程分享

    在前文中小編為大家介紹了C++智能指針的一些使用方法和基本原理,所以本文就來自己動手,從0到1實現(xiàn)一下自己的unique_ptr和shared_ptr吧
    2023-05-05
  • C語言字符串函數(shù)操作(strlen,strcpy,strcat,strcmp)詳解

    C語言字符串函數(shù)操作(strlen,strcpy,strcat,strcmp)詳解

    大家好,本篇文章主要講的是C語言字符串函數(shù)操作(strlen,strcpy,strcat,strcmp)詳解,感興趣的同學(xué)趕快來看一看吧
    2021-12-12
  • C++重載輸入和輸出運(yùn)算符詳解

    C++重載輸入和輸出運(yùn)算符詳解

    在C++中,標(biāo)準(zhǔn)庫本身已經(jīng)對左移運(yùn)算符<<和右移運(yùn)算符>>分別進(jìn)行了重載,使其能夠用于不同數(shù)據(jù)的輸入輸出,本節(jié)以前面的?complex?類為例來演示輸入輸出運(yùn)算符的重載,需要的朋友可以參考下
    2023-09-09
  • C語言編寫基于TCP和UDP協(xié)議的Socket通信程序示例

    C語言編寫基于TCP和UDP協(xié)議的Socket通信程序示例

    這篇文章主要介紹了C語言編寫基于TCP和UDP協(xié)議的Socket通信程序示例,其中TCP的客戶端與服務(wù)器端采用多線程實現(xiàn),需要的朋友可以參考下
    2016-03-03

最新評論