程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 二叉樹迭代器算法

二叉樹迭代器算法

編輯:C++入門知識

二叉樹(Binary Tree)的前序、中序和後續遍歷是算法和數據結構中的基本問題,基於遞歸的二叉樹遍歷算法更是遞歸的經典應用。

假設二叉樹結點定義如下:

  1. struct Node { 
  2.     int value; 
  3.     Node *left; 
  4.     Node *right; 

  1. void inorder_traverse(Node *node) { 
  2.     if (NULL != node->left) { 
  3.         inorder_traverse(node->left); 
  4.     } 
  5.     do_something(node); 
  6.     if (NULL != node->right) { 
  7.         inorder_traverse(node->right); 
  8.     } 
  9.  

前序和後序遍歷算法類似。

但是,僅有遍歷算法是不夠的,在許多應用中,我們還需要對遍歷本身進行抽象。假如有一個求和的函數sum,我們希望它能應用於鏈表,數組,二叉樹等等不同的數據結構。這時,我們可以抽象出迭代器(Iterator)的概念,通過迭代器把算法和數據結構解耦了,使得通用算法能應用於不同類型的數據結構。我們可以把sum函數定義為:

  1. int sum(Iterator it) 

鏈表作為一種線性結構,它的迭代器實現非常簡單和直觀,而二叉樹的迭代器實現則不那麼容易,我們不能直接將遞歸遍歷轉換為迭代器。究其原因,這是因為二叉 樹遞歸遍歷過程是編譯器在調用棧上自動進行的,程序員對這個過程缺乏足夠的控制。既然如此,那麼我們如果可以自己來控制整個調用棧的進棧和出棧不是就達到 控制的目的了嗎?我們先來看看二叉樹遍歷的非遞歸算法:

  1. void inorder_traverse_nonrecursive(Node *node) { 
  2.     Stack stack; 
  3.     do { 
  4.         // node代表當前准備處理的子樹,層層向下把左孩子壓棧,對應遞歸算法的左子樹遞歸 
  5.         while (NULL != node) { 
  6.             stack.push(node); 
  7.             node = node->left; 
  8.         } 
  9.         do { 
  10.             Node *top = stack.top(); 
  11.             stack.pop(); //彈出棧頂,對應遞歸算法的函數返回 
  12.             do_something(top); 
  13.             if (NULL != top->right) { 
  14.                 node = top->right; //將當前子樹置為剛剛遍歷過的結點的右孩子,對應遞歸算法的右子樹遞歸 
  15.                 break; 
  16.             } 
  17.         } 
  18.         while (!stack.empty()); 
  19.     } 
  20.     while (!stack.empty()); 

通過基於棧的非遞歸算法我們獲得了對於遍歷過程的控制,下面我們考慮如何將其封裝為迭代器呢? 這裡關鍵在於理解遍歷的過程是由棧的狀態來表示的,所以顯然迭代器內部應該包含一個棧結構,每次迭代的過程就是對棧的操作。假設迭代器的接口為:

  1. class Iterator { 
  2.     public: 
  3.         virtual Node* next() = 0; 
  4. }; 

下面是一個二叉樹中序遍歷迭代器的實現:

  1. class InorderIterator : public Iterator { 
  2.     public: 
  3.         InorderIterator(Node *node) { 
  4.             Node *current = node; 
  5.             while (NULL != current) { 
  6.                 mStack.push(current); 
  7.                 current = current->left; 
  8.             } 
  9.         } 
  10.         virtual Node* next() { 
  11.             if (mStack.empty()) { 
  12.                 return NULL; 
  13.             } 
  14.             Node *top = mStack.top(); 
  15.             mStack.pop(); 
  16.             if (NULL != top->right) { 
  17.                 Node *current = top->right; 
  18.                 while (NULL != current) { 
  19.                     mStack.push(current); 
  20.                     current = current->left; 
  21.                 } 
  22.             } 
  23.             return top; 
  24.          } 
  25.     private: 
  26.         std::stack<Node*> mStack; 
  27. }; 

下面我們再來考察一下這個迭代器實現的時間和空間復雜度。很顯然,由於棧中最多需要保存所有的結點,所以其空間復雜度是O(n)的。那麼時間復雜度 呢?一次next()調用也最多會進行n次棧操作,而整個遍歷過程需要調用n次next(),那麼是不是整個迭代器的時間復雜度就是O(n^2)呢?答案 是否定的!因為每個結點只會進棧和出棧一次,所以整個迭代過程的時間復雜度依然為O(n)。其實,這和遞歸遍歷的時空復雜度完全一樣。

除了上面顯式利用棧控制代碼執行順序外,在支持yield語義的語言C#, Python等)中,還有更為直接的做法。下面基於yield的二叉樹中序遍歷的Python實現:

  1. // Python 
  2. def inorder(t): 
  3.     if t: 
  4.         for x in inorder(t.left): 
  5.             yield x 
  6.         yield t.label 
  7.         for x in inorder(t.right): 
  8.             yield x 

yield與return區別的一種通俗解釋是yield返回時系統會保留函數調用的狀態,下次該函數被調用時會接著從上次的執行點繼續執行,這是一種與 棧語義所完全不同的流程控制語義。我們知道Python的解釋器是C寫的,但是C並不支持yield語義,那麼解釋器是如何做到對yield的支持的呢? 有了上面把遞歸遍歷變換為迭代遍歷的經驗,相信你已經猜到Python解釋器一定是對yield代碼進行了某種變換。如果你已經能夠實現遞歸變非遞歸,不 妨嘗試一下能否寫一段編譯程序將yield代碼變換為非yield代碼。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved