本文實(shí)例講述了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)來實(shí)現(xiàn)。遞歸的每次調(diào)用都會(huì)消耗一定的棧空間，效率要稍低于循環(huán)實(shí)現(xià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。

/*
 *作者：侯凱
 *說明：目標(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');
}

這樣程序便十分簡潔的實(shí)現(xiàn)了看似復(fù)雜的功能，下面再看一個(gè)經(jīng)典的問題：

遍歷二叉樹

二叉樹的遍歷是指從根節(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(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ù)，可更改為其他對(duì)結(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ù)，可更改為其他對(duì)結(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ù)，可更改為其他對(duì)結(jié)點(diǎn)的操作
}

其中二叉樹的結(jié)構(gòu)如下：

typedef struct BiTNode
{
  ElemType data;
  struct BiTNode *lchild,*rchild;
}BitNode,*BiTree;

希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。