數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)C++——二叉樹(shù)

2019-11-17 05:47:57

字體：大中小

供稿：網(wǎng)友

      這些天參與了CSDN論壇的討論，改變了我以前的一些看法。回頭看我以前的東西，我雖對(duì)這本書(shū)很不滿(mǎn)，但我還是按照它的安排在一點(diǎn)點(diǎn)的寫(xiě)；這樣就導(dǎo)致了，我過(guò)多的在意書(shū)中的偏漏，我寫(xiě)的更多是說(shuō)“這本書(shū)怎樣”，而偏離了我寫(xiě)這些的初衷——給正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人一些幫助。正像我在前面所說(shuō)的，雖然現(xiàn)有的教科書(shū)都不是很合理，但假如僅僅是抱怨這點(diǎn)，那無(wú)異于潑婦罵街。雖然本人的水平連初級(jí)都?jí)虿簧希辽傧葟奈易鲆稽c(diǎn)嘗試，以后這門(mén)課的教授方法必將一點(diǎn)點(diǎn)趨于合理。

      因此，后面不在按照書(shū)上的次序，將本著“實(shí)際應(yīng)用（算法）決定數(shù)據(jù)結(jié)構(gòu)”的思想來(lái)講解，常見(jiàn)教科書(shū)上有的，基本不再重點(diǎn)敘述（除了重點(diǎn)，例如AVL樹(shù)的平衡旋轉(zhuǎn)），——因此，在看本文的同時(shí)，一定要有一本教科書(shū)。這只是一個(gè)嘗試，希望大家多提寶貴意見(jiàn)。

樹(shù)

      因?yàn)楝F(xiàn)實(shí)世界中存在這“樹(shù)”這種結(jié)構(gòu)——族譜、等級(jí)制度、目錄分類(lèi)等等，而為了研究這類(lèi)問(wèn)題，必須能夠?qū)?shù)儲(chǔ)存，而如何儲(chǔ)存將取決于所需要的操作。這里有個(gè)問(wèn)題，是否答應(yīng)存在空樹(shù)。有些書(shū)認(rèn)為樹(shù)都是非空的，因?yàn)闃?shù)表示的是一種現(xiàn)實(shí)結(jié)構(gòu)，而0不是自然數(shù)；我用過(guò)的教科書(shū)都是說(shuō)可以有空樹(shù)，當(dāng)然是為了和二叉樹(shù)統(tǒng)一。這個(gè)沒(méi)有什么原則上的差別，反正就是一種習(xí)慣。

二叉樹(shù)

      二叉樹(shù)可以說(shuō)是人們假想的一個(gè)模型，因此，答應(yīng)有空的二叉樹(shù)是無(wú)爭(zhēng)議的。二叉樹(shù)是有序的，左邊有一個(gè)孩子和右邊有一個(gè)的二叉樹(shù)是不同的兩棵樹(shù)。做這個(gè)規(guī)定，是因?yàn)槿藗冑x予了左孩子和右孩子不同的意義，在二叉樹(shù)的各種應(yīng)用中，你將會(huì)清楚的看到。下面只講解鏈?zhǔn)浇Y(jié)構(gòu)。看各種講數(shù)據(jù)結(jié)構(gòu)的書(shū)，你會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象：在二叉樹(shù)這里，基本操作有計(jì)算樹(shù)高、各種遍歷，就是沒(méi)有插入、刪除——那樹(shù)是怎么建立起來(lái)的？其實(shí)這很好理解，對(duì)于非線(xiàn)性的樹(shù)結(jié)構(gòu)，插入刪除操作不在一定的法則規(guī)定下，是毫無(wú)意義的。因此，只有在具體的應(yīng)用中，才會(huì)有插入刪除操作。

節(jié)點(diǎn)結(jié)構(gòu)

      數(shù)據(jù)域、左指針、右指針肯定是必須的。除非很少用到節(jié)點(diǎn)的雙親，或者是資源緊張，建議附加一個(gè)雙親指針，這將會(huì)給很多算法帶來(lái)方便，尤其是在這個(gè)“空間換時(shí)間”的時(shí)代。

template

strUCt BTNode

{
      BTNode(T data = T(), BTNode* left = NULL, BTNode* right = NULL, BTNode* parent = NULL)

        : data(data), left(left), right(right), parent(parent) {}

      BTNode *left, *right, *parent;

      T data;
};

基本的二叉樹(shù)類(lèi)

template

class BTree

{

public:

    BTree(BTNode *root = NULL) : root(root) {}

    ~BTree()

    void MakeEmpty()

PRotected:

    BTNode *root；

private:

    void destroy(BTNode* p)

    {

        if (p)

        {

            destroy(p->left);

            destroy(p->right);

            delete p;

        }

    }

}

二叉樹(shù)的遍歷

      基本上有4種遍歷方法，先、中、后根，逐層。當(dāng)初我對(duì)這個(gè)很迷惑，搞這么多干什么？到了后面才明白，這是不同的應(yīng)用需要的。例如，判定兩個(gè)二叉樹(shù)是否相等，只要子樹(shù)根節(jié)點(diǎn)不同，那么就不等，顯然這時(shí)要用先序遍歷；而刪除二叉樹(shù)，必須先刪除左右子樹(shù)，然后才能刪除根節(jié)點(diǎn)，這時(shí)就要用后序遍歷。

      實(shí)際上，搞這么多遍歷方法，根本原因是在內(nèi)存中儲(chǔ)存的樹(shù)是非線(xiàn)性結(jié)構(gòu)。對(duì)于用數(shù)組儲(chǔ)存的二叉樹(shù)，這些名目繁多的方法都是沒(méi)有必要的。利用C++的封裝和重載特性，這些遍歷方法能很清楚的表達(dá)。

1.         前序遍歷

public:

      void PreOrder(void (*visit)(T &data) = print)
      {
            PreOrder(root, visit);
      }

private:

      void PreOrder(BTNode* p, void (*visit)(T &data))
      {
            if (p)
            {
                  visit(p->data);
                  PreOrder(p->left, visit);
                  PreOrder(p->right, visit);
            }
      }

2.         中序遍歷

public:

       void InOrder(void (*visit)(T &data) = print)
      {
            InOrder(root, visit);
      }

private:

void InOrder(BTNode* p, void (*visit)(T &data))
{
       if (p)
      {
            InOrder(p->left, visit);
            visit(p->data);
            InOrder(p->right, visit);
      }
}

3.         后序遍歷

public:

       void PostOrder(void (*visit)(T &data) = print)
      {
            PostOrder(root, visit);
      }

private:

void PostOrder(BTNode* p, void (*visit)(T &data))
{
       if (p)
      {
            PostOrder(p->left, visit);
            PostOrder(p->right, visit);
            visit(p->data);
      }
}

4.         層次遍歷

void LevelOrder(void (*visit)(T &data) = print)
{
      queue< BTNode* > a;
      BTNode* p = root;//記得#include

       while (p)
      {
            visit(p->data);

            if (p->left)
                  a.push(p->left);
            if (p->right)
                  a.push(p->right);

            if (a.empty())
                  break;
            p = a.front();
            a.pop();
      }
}

附注：缺省的visit函數(shù)print如下

private:

       static void print(T &data)
      {
            cout << data << ' ';
      }

5.         不用棧的非遞歸中序遍歷

      當(dāng)有parent指針時(shí)，可以不用棧實(shí)現(xiàn)非遞歸的中序遍歷，書(shū)上提到了有這種方法，但沒(méi)給出例程。

public:

BTNode* next()
{
      if(!current)
            return NULL;

      if (current->right)
      {
            current = current->right;
            while (current->left)
                  current = current->left;
      }
      else
      {
            BTNode* y = current->parent;
            while (y && current == y->right)
            {
                  current = y;
                  y = y->parent;
            }
            current = y;
      }
      return current;
}

private:

BTNode* current;

      上面的函數(shù)能使current指針向前移動(dòng)一個(gè)位置，假如要遍歷整棵二叉樹(shù)，需要使current指向中序序列的第一個(gè)節(jié)點(diǎn)，例如下面的成員函數(shù)：

public:

void first()
{
      current = root;
      while (current->left)
            current = current->left;
}

線(xiàn)索化二叉樹(shù)

這是數(shù)據(jù)結(jié)構(gòu)課程里第一個(gè)碰到的難點(diǎn)，不知道你是不是這樣看，反正我當(dāng)初是費(fèi)了不少腦細(xì)胞——當(dāng)然，惱人的矩陣壓縮和相關(guān)的加法乘法運(yùn)算不在考慮之列。我費(fèi)了不少腦細(xì)胞是因?yàn)樗伎迹核麄兏墒裁茨兀亢苄老驳目吹皆谶@本黃皮書(shū)上，這章被打了*號(hào)，雖然我不確定作者是不是跟我一個(gè)想法——線(xiàn)索化二叉樹(shù)在現(xiàn)在的PC上是毫無(wú)用處的！——不知我做了這個(gè)結(jié)論是不是會(huì)被人罵死，^_^。

為了證實(shí)這個(gè)結(jié)論，我們來(lái)看看線(xiàn)索化二叉樹(shù)提出的緣由：第一，我們想用比較少的時(shí)間，尋找二叉樹(shù)某一個(gè)遍歷線(xiàn)性序列的前驅(qū)或者后繼。當(dāng)然，這樣的操作很頻繁的時(shí)候，做這方面的改善才是有意義的。第二，二叉樹(shù)的葉子節(jié)點(diǎn)還有兩個(gè)指針域沒(méi)有用，可以節(jié)省內(nèi)存。說(shuō)真的，提出線(xiàn)索化二叉樹(shù)這樣的構(gòu)思真的很精巧，完全做到了“廢物利用”——這個(gè)人真應(yīng)該投身環(huán)保事業(yè)。但在計(jì)算機(jī)這個(gè)死板的東西身上，人們的精巧構(gòu)思往往都是不能實(shí)現(xiàn)的——為了速度，計(jì)算機(jī)的各個(gè)部件都是整潔劃一的，而構(gòu)思的精巧往往都是建立在組成的復(fù)雜上的。

我們來(lái)看看線(xiàn)索化二叉樹(shù)究竟能不能達(dá)到上面的兩個(gè)目標(biāo)。

求遍歷后的線(xiàn)性序列的前驅(qū)和后繼。前序線(xiàn)索化能依次找到后繼，但是前驅(qū)需要求雙親；中序線(xiàn)索化前驅(qū)和后繼都不需要求雙親，但是都不很直接；后序線(xiàn)索化能依次找到前驅(qū)，但是后繼需要求雙親。可以看出，線(xiàn)索化成中序是最佳的選擇，基本上算是達(dá)到了要求。

節(jié)省內(nèi)存。添加了兩個(gè)標(biāo)志位，問(wèn)題是這兩個(gè)位怎么儲(chǔ)存？即使是在支持位存儲(chǔ)的CPU上，也是不能拿位存儲(chǔ)器來(lái)存的，第一是因?yàn)榻Y(jié)構(gòu)體成員的地址是在一起的，第二是位存儲(chǔ)器的數(shù)目是有限的。因此，最少需要1個(gè)字節(jié)來(lái)儲(chǔ)存這兩個(gè)標(biāo)志位。而為了速度和移植，一般來(lái)說(shuō)，內(nèi)存是要對(duì)齊的，實(shí)際上根本就沒(méi)節(jié)省內(nèi)存！然而，當(dāng)這個(gè)空間用來(lái)儲(chǔ)存雙親指針時(shí)，帶來(lái)的方便絕對(duì)不是線(xiàn)索化所能比擬的，前面已經(jīng)給出了無(wú)棧的非遞歸遍歷。并且，在線(xiàn)索化二叉樹(shù)上插入刪除操作附加的代價(jià)太大。

綜上，線(xiàn)索化最好是中序線(xiàn)索化（前序后序線(xiàn)索化后還得用棧，何必要線(xiàn)索化呢），附加的標(biāo)志域空間至少1個(gè)字節(jié)，在32位的CPU會(huì)要求對(duì)齊到4字節(jié)，還不如存儲(chǔ)一個(gè)雙親指針，同樣能達(dá)到中序線(xiàn)索化的目的，并且能帶來(lái)其他的好處。所以，線(xiàn)索化二叉樹(shù)在現(xiàn)在的PC上是毫無(wú)用處的！

由于對(duì)其他體系不太了解，以下觀(guān)點(diǎn)姑妄聽(tīng)之。在內(nèi)存空間非常充裕的現(xiàn)在，一個(gè)節(jié)點(diǎn)省2～3個(gè)字節(jié)實(shí)在是沒(méi)什么意思（實(shí)際上由于對(duì)齊還省不出來(lái)）；而在內(nèi)存非常寶貴的地方（比如單片機(jī)），會(huì)盡量避免使用樹(shù)結(jié)構(gòu)——利用其他的方法。所以，現(xiàn)在看來(lái)，線(xiàn)索化二叉樹(shù)真的是毫無(wú)用處了。

二叉搜索樹(shù)
這恐怕是二叉樹(shù)最重要的一個(gè)應(yīng)用了。它的構(gòu)想實(shí)際是個(gè)很自然的事情——查找值比當(dāng)前節(jié)點(diǎn)小轉(zhuǎn)左，大轉(zhuǎn)右，等則查到，到頭了就是沒(méi)找著。越自然的東西越好理解，也就越不需要我廢話(huà)。在給出BST的實(shí)現(xiàn)之前，我們要在二叉樹(shù)的類(lèi)中添加一個(gè)打印樹(shù)狀結(jié)構(gòu)的成員函數(shù)，這樣，就能清楚的看出插入和刪除過(guò)程。

public:

void print()

{

       queue< BTNode* > a; queue flag; ofstream outfile("out.txt");

       BTNode* p = root; BTNode zero; bool v = true;

       int i = 1, level = 0, h = height();

       while (i < 2<
       {

              if (i == 1<
              {

                     cout << endl << setw(2 <<(h - level)); level++;

                     if (v) cout << p->data;

                     else cout << ' ';

              }

              else

              {

                     cout << setw(4 <<(h - level + 1));

                     if (v) cout << p->data;

                     else cout << "  ";

              }

              if (p->left)

              else

              if (p->right)

              else

              p = a.front(); a.pop(); v = flag.front(); flag.pop(); i++;

       }

       cout << endl;

}

打印樹(shù)狀結(jié)構(gòu)的核心是按層次遍歷二叉樹(shù)，但是，二叉樹(shù)有許多節(jié)點(diǎn)缺左或右子樹(shù)，連帶的越到下面空隙越大。為了按照樹(shù)的結(jié)構(gòu)打印，必須把二叉樹(shù)補(bǔ)成完全二叉樹(shù)，這樣下面的節(jié)點(diǎn)就知道放在什么位置了——a.push(&zero);但是這樣的節(jié)點(diǎn)不能讓它打印出來(lái)，所以對(duì)應(yīng)每個(gè)節(jié)點(diǎn)，有一個(gè)是否打印的標(biāo)志，按理說(shuō)pair結(jié)構(gòu)很合適，為了簡(jiǎn)單我用了并列的兩個(gè)隊(duì)列，一個(gè)放節(jié)點(diǎn)指針——a，一個(gè)放打印標(biāo)志——flag。這樣一來(lái)，循環(huán)結(jié)束的標(biāo)志就不能是隊(duì)列空——永遠(yuǎn)都不可能空，碰到NULL就補(bǔ)一個(gè)節(jié)點(diǎn)——而是變成了到了滿(mǎn)二叉樹(shù)的最后一個(gè)節(jié)點(diǎn)2^(height+1)-1。——黃皮書(shū)對(duì)于樹(shù)高的定義是，空樹(shù)為的高度為－1。

對(duì)于輸出格式，注重的是到了第1、2、4、8號(hào)節(jié)點(diǎn)要換行，并且在同一行中，第一個(gè)節(jié)點(diǎn)的域?qū)捠呛笮蚬?jié)點(diǎn)的一半。上面的函數(shù)在樹(shù)的層次少于等于5（height<=4）的時(shí)候能正常顯示，再多的話(huà)就必須輸出到文件中去ofstream outfile("out.txt");——假如層次再多的話(huà)，打印出來(lái)也沒(méi)什么意義了。

二叉搜索樹(shù)的實(shí)現(xiàn)
實(shí)際上就是在二叉樹(shù)的基礎(chǔ)上增加了插入、刪除、查找。

#include "BaseTree.h"

template

class BSTree : public BTree

{

public:

       BTNode* &find(const T &data)

       {

              BTNode** p = &root; current = NULL;

              while(*p)

              {

                     if ((*p)->data == data) break;

                     if ((*p)->data < data)

                     else

              }

              return *p;

       }

       bool insert(const T &data)

       {

              BTNode* &p = find(data); if (p) return false;

              p = new BTNode(data, NULL, NULL, current); return true;

       }

       bool remove(const T &data)

       {

              return remove(find(data));

       }

private:

bool remove(BTNode* &p)

{

       if (!p) return false; BTNode* t = p;

       if (!p->left  !p->right)

       {

              if (!p->left) p = p->right; else p = p->left;

              if (p) p->parent = current;

              delete t; return true;

       }

       t=p->right;while(t->left) t=t->left;p->data=t->data;current=t->parent;

       return remove(current->left==t?current->left:current->right);

       }

};

以上代碼有點(diǎn)費(fèi)解，有必要說(shuō)明一下——非線(xiàn)性鏈?zhǔn)浇Y(jié)構(gòu)操作的實(shí)現(xiàn)都是很讓人費(fèi)神。insert和remove都是以find為基礎(chǔ)的，因此必須讓find能最大限度的被這兩個(gè)操作利用。

l         對(duì)于insert，需要修改查找失敗時(shí)的指針內(nèi)容，顯然這是個(gè)內(nèi)部指針（在雙親節(jié)點(diǎn)的內(nèi)部，而不是象root和current那樣在節(jié)點(diǎn)外面指向節(jié)點(diǎn)），這就要求find返回一個(gè)內(nèi)部指針的引用。但是C++的引用綁定到一個(gè)對(duì)象之后，就不能再改變了，因此在find內(nèi)部的實(shí)現(xiàn)是一個(gè)二重指針。insert操作還需要修改插入的新節(jié)點(diǎn)的parent指針域，因此在find中要產(chǎn)生一個(gè)能被insert訪(fǎng)問(wèn)的指向find返回值所在節(jié)點(diǎn)的指針，這里用的是current。實(shí)際上find返回的指針引用不是current->left就是current->right。這樣一來(lái)，insert的實(shí)現(xiàn)就非常簡(jiǎn)單了。

l         對(duì)于remove，需要修改查找成功時(shí)的指針內(nèi)容，同樣是個(gè)內(nèi)部指針。在find的基礎(chǔ)上，很輕易就能得到這個(gè)內(nèi)部指針的引用(BTNode* &p = find(data)。

Ø         在p->left和p->right中至少有一個(gè)為NULL的情況下，假如p->left ==NULL，那么就重連右子樹(shù)p = p->right，反之，重連左子樹(shù)p = p->left。注重，左右子樹(shù)全空的情況也包含在這兩個(gè)操作中了——在p->left ==NULL的時(shí)候重連右子樹(shù)，而這時(shí)p->right也是NULL——因此不必列出來(lái)。假如重連后p不為空，需要修改p->parent = current。

Ø         若p->left和p->right都不為空，可以轉(zhuǎn)化為有一個(gè)為空。例如一個(gè)中序有序序列[1,2,3,4,5]，假設(shè)3既有左子樹(shù)又有右子樹(shù)，那么它的前驅(qū)2一定缺右子樹(shù)，后繼4一定缺少左子樹(shù)。【注1】這樣一來(lái)刪除節(jié)點(diǎn)3就等效成從[1,2,3(4),4,5]刪除節(jié)點(diǎn)4。這樣就可以利用上面的在p->left和p->right中至少有一個(gè)為NULL的情況下的方法了。還是由于C++的引用不能改變綁定對(duì)象，這里是用利用遞歸來(lái)解決的，還好最多只遞歸一次。假如用二重指針又是滿(mǎn)天星星了，這就是明明是尾遞歸卻沒(méi)有消去的原因。

【注1】這是因?yàn)椋偃?既有左子樹(shù)又有右子樹(shù)，那么2一定在3的左子樹(shù)上，4一定在3的右子樹(shù)上；假如2有右子樹(shù)，那么在2和3之間還應(yīng)該有一個(gè)節(jié)點(diǎn)；假如4有左子樹(shù)，那么3和4之間也應(yīng)該還有一個(gè)節(jié)點(diǎn)。

【閑話(huà)】上面關(guān)于remove操作p->left和p->right都不為空的處理方法的講解，源于嚴(yán)蔚敏老師的課件，看完后我豁然開(kāi)朗，真不知道為什么她自己那本《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》這里寫(xiě)的那么難懂，我是死活沒(méi)看明白。

遞歸遍歷與非遞歸遍歷
前面寫(xiě)過(guò)一些關(guān)于遞歸的文章，因?yàn)槟菚r(shí)還沒(méi)有寫(xiě)到樹(shù)，因此也舉不出更有說(shuō)服力的例子，只是闡述了“遞歸是一種思想”，正像網(wǎng)友評(píng)價(jià)的，“一篇入門(mén)的文章”。但只要能能讓你建立“遞歸是一種思想”這個(gè)觀(guān)念，我的努力就沒(méi)有白費(fèi)。現(xiàn)在，講完了二叉搜索樹(shù)，終于有了能說(shuō)明問(wèn)題的例子了。按照前面提供的代碼，應(yīng)該能調(diào)試通過(guò)下面的程序。

#include

using namespace std;

#include

#include

#include "BSTree.h"

#include "Timer.h"

#define random(num)     (rand() % (num))

#define randomize()     srand((unsigned)time(NULL))

#define NODENUM 200000//node number

int data[NODENUM];

void zero(int &t)

int main()

{

       BSTree a; Timer t; randomize(); int i;

       for (i = 0; i < NODENUM; i++) data[i] = i;

       for (i = 0; i < NODENUM; i++) swap(data[i], data[random(NODENUM)]);//random swap

       t.start(); for (i = 0; i < NODENUM; i++) a.insert(data[i]);

       cout << "Insert time: " << t.GetTime() << " Node number: " << NODENUM << endl;

       t.start(); for (a.first(); a.get() != NULL; a.next()) a.get()->data = 0;

       cout << "Non-Stack time: " << t.GetTime() << endl;

       t.start(); a.LevelOrder(zero); cout << "LevlOrder time: " << t.GetTime() << endl;

       t.start(); a.PreOrder(zero); cout << " PreOrder time: " << t.GetTime() << endl;

       t.start(); a.InOrder(zero); cout << "  InOrder time: " << t.GetTime() << endl;

       t.start(); a.PostOrder(zero); cout << "PostOrder time: " << t.GetTime() << endl;

       return 0;

}

以下是timer.h的內(nèi)容

#ifndef Timer_H

#define Timer_H

#include

class Timer

{

public:

       Timer()

       inline void start()

       inline double GetTime()

       {

              QueryPerformanceCounter(&timerE);

              return (double)(timerE.QuadPart - timerB.QuadPart) / (double)Frequency.QuadPart * 1000.0;

       }

private:

       LARGE_INTEGER timerB, timerE, Frequency;

};

#endif

上面的程序中，層次遍歷用到的是隊(duì)列，這應(yīng)該可以代表用棧消解遞歸的情況，在我的機(jī)器C500上運(yùn)行的結(jié)果是：

Insert time: 868.818    Node number: 200000

Non-Stack time: 130.811

LevlOrder time: 148.438

PreOrder time: 125.47

  InOrder time: 129.125

PostOrder time: 130.914

以上是VC6的release版的結(jié)果，時(shí)間單位是ms，不說(shuō)明會(huì)有人認(rèn)為是死機(jī)了，^_^。可以看出，遞歸遍歷實(shí)際上并不慢，相反，更快一些，而debug版的結(jié)果是這樣的：

Insert time: 1355.69    Node number: 200000

Non-Stack time: 207.086

LevlOrder time: 766.023

PreOrder time: 183.287

  InOrder time: 179.835

PostOrder time: 190.674

遞歸遍歷的速度是最快的
這恐怕是上面結(jié)果得出的最直接的結(jié)論。不知從哪聽(tīng)來(lái)的觀(guān)點(diǎn)“遞歸的速度慢，為了提高速度，應(yīng)該用棧消解遞歸”，證據(jù)就是斐波那契數(shù)列的計(jì)算，遺憾的是斐波那契數(shù)列的非遞歸算法是循環(huán)迭代，不是棧消解；假如他真的拿棧來(lái)模擬，他就會(huì)發(fā)現(xiàn)，其實(shí)用棧的更慢。

我們來(lái)看看為什么。遞歸的實(shí)現(xiàn)是將參數(shù)壓棧，然后call自身，最后按層返回，一系列的動(dòng)作是在堆棧上操作的，用的是push、pop、call、ret之類(lèi)的指令。而用ADT棧來(lái)模擬遞歸調(diào)用，實(shí)現(xiàn)的還是上述指令的功能，不同的是那些指令對(duì)照的ADT實(shí)現(xiàn)可就不只是一條指令了。誰(shuí)都明白模擬的執(zhí)行效率肯定比真實(shí)的差，怎么會(huì)在這個(gè)問(wèn)題上就犯糊涂了呢？

當(dāng)然，你非要在visit函數(shù)中加入類(lèi)似這樣的istream file1(“input.txt”)，然后在用棧模擬的把這個(gè)放在循環(huán)的外面，最后你說(shuō)，棧模擬的比遞歸的快，我也無(wú)話(huà)可說(shuō)——曾經(jīng)就見(jiàn)過(guò)一個(gè)人，http://www.csdn.net/Develop/Read_Article.asp?Id=18342將數(shù)據(jù)庫(kù)連接放在visit函數(shù)里面，然后說(shuō)遞歸的速度慢。

假如一個(gè)遞歸過(guò)程用非遞歸的方法實(shí)現(xiàn)后，速度提高了，那只是因?yàn)檫f歸做了一些無(wú)用功。比如用循環(huán)消解的尾遞歸，是多了無(wú)用的壓棧和出棧才使速度受損的；斐波那契數(shù)列計(jì)算的遞歸改循環(huán)迭代所帶來(lái)的速度大幅提升，是因?yàn)楦牡袅酥貜?fù)計(jì)算的毛病。假使一個(gè)遞歸過(guò)程必須要用棧才能消解，那么，完全模擬后的結(jié)果根本就不會(huì)對(duì)速度有任何提升，只會(huì)減慢；假如你改完后速度提升了，那只證實(shí)你的遞歸函數(shù)寫(xiě)的有問(wèn)題，例如多了許多重復(fù)操作——打開(kāi)關(guān)閉文件、連接斷開(kāi)數(shù)據(jù)庫(kù)，而這些完全可以放到遞歸外面。遞歸方法本身是簡(jiǎn)潔高效的，只是使用的人不注重使用方法。

這么看來(lái)，研究遞歸的棧消解似乎是無(wú)用的，其實(shí)不然，用棧模擬遞歸還是有點(diǎn)意義的，只是并不大，下面將給出示例來(lái)說(shuō)明。

棧模擬遞歸的好處是節(jié)省了堆棧
將上面的程序//node number那行的數(shù)值改為15000——不改沒(méi)反應(yīng)了別找我，將//random swap那行注釋掉，運(yùn)行debug版，耐心的等30秒，就會(huì)拋異常了，最后的輸出結(jié)果是這樣的：

Insert time: 27555.5    Node number: 15000

Non-Stack time: 16.858

LevlOrder time: 251.036

這只能說(shuō)明堆棧溢出了。你可以看到層次遍歷還能工作（由此類(lèi)推，棧模擬的也能工作），但是遞歸的不能工作了。這是因?yàn)楹涂偟膬?nèi)存空間比起來(lái)，堆棧空間是很少的，假如遞歸的層次過(guò)深，堆棧就溢出了。所以，假如你預(yù)先感到遞歸的層次可能過(guò)深，你就要考慮用棧來(lái)消解了。

然而，假如你必須用遞歸，而遞歸的層次深到連堆棧都溢出了，那肯定是你的算法有問(wèn)題，或者是那個(gè)程序根本不適合在PC上運(yùn)行——運(yùn)行起來(lái)就象死機(jī)了，這樣的程序誰(shuí)敢用？所以說(shuō)用棧模擬遞歸是有意義的，但是不大，因?yàn)楹苌儆玫健?br />
對(duì)于樹(shù)結(jié)構(gòu)來(lái)說(shuō)，假如沒(méi)有雙親指針，那么遍歷時(shí)的遞歸是必須的，與其搞什么棧消解不如添加一個(gè)雙親指針，這實(shí)際上也是用堆空間換取堆棧空間的一個(gè)方法，只是比ADT棧來(lái)得直接、高效罷了。

綜上，遞歸的棧消解，實(shí)際上只能節(jié)省堆棧空間，不僅不會(huì)提高速度，相反卻會(huì)降低——天下哪有白吃的午餐，既省了堆棧空間還能提高速度。那些“棧消解遞歸能提高速度”的謠傳只是對(duì)“消除尾遞歸能提高速度”的不負(fù)責(zé)任的引申，然而一群人以訛傳訛，真就像是那么回事了，這就叫三人成虎。等我這時(shí)候再回過(guò)頭看教科書(shū)，竟然沒(méi)看見(jiàn)一本書(shū)上寫(xiě)著“棧消解遞歸能提高速度”。真的，以前一直被誤導(dǎo)了，還不知道是被誰(shuí)誤導(dǎo)的——書(shū)上根本就沒(méi)有寫(xiě)。

另外的結(jié)論
對(duì)比上面兩組結(jié)果，可以看到插入15000個(gè)節(jié)點(diǎn)比200000個(gè)節(jié)點(diǎn)消耗的時(shí)間還多，其原因就是插入數(shù)據(jù)的順序不同，從而導(dǎo)致了find的效率不同。隨機(jī)的順序大致能保證樹(shù)的左右子樹(shù)分布均勻，而有序的序列將使樹(shù)退化成單支的鏈表，從而使得O(logN)的時(shí)間復(fù)雜度變成了O(N)。同時(shí)，這也是為什么200000個(gè)節(jié)點(diǎn)的樹(shù)遞歸遍歷還能工作，而遞歸遍歷15000個(gè)節(jié)點(diǎn)的樹(shù)堆棧就溢出了——遞歸的每一層對(duì)應(yīng)的節(jié)點(diǎn)太少了。

為了提高find的效率，同時(shí)也是使樹(shù)的遞歸遍歷方法的使用更為寬泛，有必要研究如何能使樹(shù)的高度降低，這就是下面將要講到的平衡樹(shù)的來(lái)由。

上一篇：樹(shù)的生成與遍歷

下一篇：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)C++——樹(shù)（總結(jié)）