前序遍歷的非遞歸算法

<法一>

思路：

二叉樹的前序遍歷過程：

1. 從樹根開始沿著左子樹一直深入，直到最左端無法深入時(shí)，返回；
2. 進(jìn)入最近深入時(shí)遇到結(jié)點(diǎn)的右子樹，再進(jìn)行如此的深入和返回；
3. 直到最后從根節(jié)點(diǎn)的右子樹返回到根節(jié)點(diǎn)為止；

由其深入返回的過程我們知道可以用一個(gè)棧來幫助我們消除遞歸

1.存入根結(jié)點(diǎn)：首先判斷root（根節(jié)點(diǎn)）是否為空，如果為空則直接return，不為空就將根節(jié)點(diǎn)壓入棧中。這里我隨機(jī)生成一個(gè)樹作為例子，

→

2.進(jìn)行非遞歸前序遍歷：將A彈出，打印出A結(jié)點(diǎn)存入的值，接著再依次檢查A是否有右孩子（Rson）和左孩子（Lson）（因?yàn)槭乔靶虮闅v，而棧的特點(diǎn)是先進(jìn)后出，我們需要優(yōu)先打印左孩子的值，所以先檢查是否有右孩子，如果有的話將右孩子優(yōu)先壓入棧中），如果有的話依次存入棧中，此時(shí)棧中全是第二層的元素

隨后我們?cè)購(gòu)棾鰲ｍ斀Y(jié)點(diǎn)B，打印他的值，接著依葫蘆畫瓢，分別再次檢查B的右孩子和左孩子，如果有的話分別存入，因?yàn)锽沒有左孩子，所以第三次壓棧存入D結(jié)點(diǎn)

再次彈出D結(jié)點(diǎn)，存入其右孩子和左孩子，棧更新為：

因?yàn)镚，F(xiàn)為葉子結(jié)點(diǎn)，沒有孩子，所以分別彈出F，G并打印值，目前為止打印出：ABDFG;

當(dāng)棧中只剩C時(shí)，彈出C，打印值，因?yàn)镃有右孩子，所以存入其右孩子E，棧更新為：

最后，彈出E，存入其右孩子H:

因?yàn)镚是葉子結(jié)點(diǎn)，所以彈出G后棧為空，整個(gè)樹也遍歷完畢，由此可以得到循環(huán)的條件是當(dāng)且僅當(dāng)棧不為空時(shí)

3.觀察特點(diǎn)進(jìn)行總結(jié)：只要左子樹還沒有遍歷完，就會(huì)彈出元素的同時(shí)，存入新的元素，直到左子樹全部被遍歷完沒有新的元素存入，才會(huì)開始遍歷右子樹，這也構(gòu)成我們的中序遍歷。

代碼實(shí)現(xiàn)如下：

typedef struct BiTNode
{
  char data;
  struct BiTNode *lson, *rson;
} BiTNode, *BiTree;  //二叉樹的結(jié)構(gòu)體

// 二叉樹的前序遍歷算法1基于STL stack
void PreOrder1(BiTree bt)
{
  stack<BiTree> Stack;
  if (bt == NULL)    //如果根結(jié)點(diǎn)為空，直接return
    return;
  Stack.push(bt);    //根結(jié)點(diǎn)不為空將其壓入棧中
  while (!Stack.empty())  //循環(huán)條件：當(dāng)棧不為空時(shí)
  {
    BiTree Cur = Stack.top();  
    cout << Cur->data << endl; 
    Stack.pop();           //取出并打印棧頂元素
    if (Cur->rson)             
      Stack.push(Cur->rson);
    if (Cur->lson)
      Stack.push(Cur->lson);   //分別將棧頂元素的右孩子和左孩子壓入棧中
  }
}

<法二>

思路：

1.連續(xù)將結(jié)點(diǎn)的左孩子壓入棧中：此處我仍用這個(gè)生成的樹進(jìn)行演示，法二的主要思路是只要當(dāng)前節(jié)點(diǎn)指向左孩子的指針不為NULL，就一直打印當(dāng)前節(jié)點(diǎn)值并壓入棧中。

→

打?。篈B

2.彈出棧頂元組：直到一個(gè)結(jié)點(diǎn)沒有左孩子時(shí)，此時(shí)退出循環(huán)，此時(shí)只有從B的右孩子D進(jìn)行入手，所以我們彈出棧頂元素B，并將指針指向該節(jié)點(diǎn)的右孩子D，重復(fù)第一步的操作：

3.重復(fù)1，2步：循環(huán)到F時(shí)又退出了，我們?cè)僦貜?fù)第二步的操作，彈出F，而F也沒有右孩子，所以繼續(xù)彈出D，將節(jié)點(diǎn)指針指向D的右孩子G，繼續(xù)循環(huán)：

→

→→

注意：由于C，E，H只有右孩子沒有左孩子所以只能彈出C后E才能進(jìn)棧，彈出E后C才能進(jìn)棧

3.循環(huán)結(jié)束條件：如果初始的根結(jié)點(diǎn)為空，則循環(huán)直接退出，進(jìn)入循環(huán)后如果棧中沒有新增元素，并且沒有新增元素即將入棧（即當(dāng)前指向的結(jié)點(diǎn)為空），代表遍歷完成，此時(shí)退出循環(huán)。

代碼實(shí)現(xiàn)如下：

// 二叉樹的前序遍歷算法2基于STL stack
void PreOrder2(BiTree bt)
{
  stack<BiTree> Stack;
  BiTree Cur;
  while (!Stack.empty() || bt != NULL)  //循環(huán)終止條件
  {
    while (bt != NULL)   
    {
      cout << bt->data << endl;
      Stack.push(bt);
      bt = bt->lson;
    }
    if (!Stack.empty())   
    {
      Cur = Stack.top();
      Stack.pop();
      bt = Cur->rson;
    }
  }
}

?文章來源地址http://www.zghlxwxcb.cn/news/detail-413225.html

到了這里，關(guān)于二叉樹先序，中序，后序遍歷的非遞歸算法（一）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！