二叉樹的非遞歸的遍歷方式

上篇博客記錄了二叉樹的遞歸遍歷方式以及根據(jù)二叉樹的遍歷結果還原二叉樹的內(nèi)容。

本篇博客記錄二叉樹的非遞歸的遍歷方式。

二叉樹的非遞歸遍歷需要借助棧來實現(xiàn)，而且三種遍歷的方式的算法難易程度并不相同。其中，先序遍歷較為簡單，中序遍歷稍難，后序遍歷最傷腦筋。下面分別說一說三種非遞歸遍歷算法的實現(xiàn)方式。

1. 非遞歸先序遍歷

如上所述，非遞歸先序遍歷方式較為簡單。其主要思想是：

1. 將二叉樹的根節(jié)點壓入棧中。
2. 獲取棧頂元素P并打印其值，做出棧操作。
3. 若p的右節(jié)點存在，將其壓入棧中。
4. 如p的左節(jié)點存在，將其壓入棧中。
5. 如果棧不為空的話，重復2-4操作。

這種方法說的直白一點就是先讀取棧頂節(jié)點，然后在將該節(jié)點的子節(jié)點按照先右后左的方式入棧。這樣就保證了在每次循環(huán)過程中都能先訪問根節(jié)點，再以先序的方式遍歷左子樹和右子樹。

void PreTraverseNoRecursion(BiTree T)
{    //BiTree  與TreeNode* 是相同類型stack<TreeNode*> temp_stack;TreeNode* temp_node;temp_stack.push(T);do {temp_node = temp_stack.top();cout << temp_node->data << " ";temp_stack.pop();if (temp_node->Rchild)temp_stack.push(temp_node->Rchild);if (temp_node->Lchild)temp_stack.push(temp_node->Lchild);} while (!temp_stack.empty());}

2.非遞歸中序遍歷

非遞歸的中序遍歷要比先序遍歷難一些，主要是不容易思考全面。
非遞歸中序遍歷的主要思想是：

1. 定義一個結點指針p，使其指向根節(jié)點。
2. 若p不為空或棧不為空，將根節(jié)點和二叉樹最左邊的各個節(jié)點逐個壓入棧中。中序遍歷必須先訪問左子樹，因此要把根節(jié)點和二叉樹最左邊的各個節(jié)點逐個壓入棧中。這個過程能夠保證棧頂?shù)墓?jié)點是整個二叉樹最左邊最底層的節(jié)點，該節(jié)點不存在左子樹。
3. 訪問棧頂節(jié)點q并出棧。
4. 令p等于q的右節(jié)點。節(jié)點q不存在左子樹，但不一定不存在右子樹。若其存在右子樹，令p等于q的右節(jié)點，相當于讓p作為一顆新二叉樹的根節(jié)點，重復2-3操作。若q沒有右子樹，p將訪問棧中新的頂節(jié)點。
5. 重復2-4操作。

void MidTraverseNoRecursion(BiTree T)
{stack<TreeNode*> temp_stack;TreeNode* temp_node = T;while (temp_node || !temp_stack.empty()){while (temp_node){temp_stack.push(temp_node);temp_node = temp_node->Lchild;}temp_node = temp_stack.top();cout << temp_node->data << " ";temp_stack.pop();temp_node = temp_node->Rchild;}
}

3.非遞歸后序遍歷

非遞歸后序遍歷是三種非遞歸遍歷算法中最難的一種，而它難就難在需要另外一個指針來記錄上一次訪問的節(jié)點。
其主要思想是：

1. 定義兩個節(jié)點指針cur_node 和last_node，并使他們指向根節(jié)點。
2. 將根節(jié)點壓入棧中。
3. 若棧不為空，則令cur_node指向棧頂節(jié)點。
4. 若 （cur_node指向節(jié)點沒有子節(jié)點） 或 （cur_node指向節(jié)點的右節(jié)點為空 且last_node指向的節(jié)點為當前節(jié)點的左節(jié)點） 或 （last_node指向的節(jié)點為當前節(jié)點的右節(jié)點），則訪問該節(jié)點并出棧。否則將該節(jié)點的子節(jié)點按照先右后左的方式入棧。
5. 重復3-4操作。

該方法不易想到，但是想到后理解起來也很容易。其實它要做的就是先將節(jié)點從根節(jié)點開始按照先右后左的順序存入棧中，直到找到最左邊最底層的葉節(jié)點L。找到該葉節(jié)點后對其進行訪問，然后令last_node指向它，用已標記，并進行出棧操作，表示完成該節(jié)點的訪問。若L的父節(jié)點存在右節(jié)點（即L存在兄弟節(jié)點），則此時棧頂元素應該是這個L的兄弟節(jié)點（稱其為b）。若b無子節(jié)點，則對其訪問，并用last_node進行標記，然后出棧。否則將其子節(jié)點入棧。如果完成了對L 的訪問，且b不存在，則訪問其父節(jié)點，然后出棧。該過程由cur_node ->Rchild == NULL && last_node == cur_node ->Lchild 條件控制。如果完成了對L 和b的訪問,則訪問其父節(jié)點，然后出棧。該過程由last_node == cur_node ->Rchild條件控制。

理解清楚之后也不是很難。

void PostTTraverseNoRecursion(BiTree T)
{stack<TreeNode*> temp_stack;TreeNode* cur_node = T;TreeNode* last_node = T;temp_stack.push(T);while (!temp_stack.empty()){cur_node = temp_stack.top();if ((cur_node ->Lchild == NULL && cur_node ->Rchild == NULL) || (cur_node ->Rchild == NULL && last_node == cur_node ->Lchild) || (last_node == cur_node ->Rchild)){cout << cur_node ->data << " ";last_node = cur_node ;temp_stack.pop();}else{if (cur_node ->Rchild)temp_stack.push(cur_node ->Rchild);if (temp_node->Lchild)temp_stack.push(cur_node ->Lchild);}}
}

若有人看到本篇博客，那我就送他一句話：世界上就怕認真二字，格物致知方能有所收獲。

總結

以上是生活随笔為你收集整理的刷题：二叉树的非递归遍历方式的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。