非遞迴遍歷二叉樹(打賭你肯定能理解)
摘要：
好久沒寫, 忙於實習以及晚上刷刷題, 這次來寫一下平時很多人都很畏懼的二叉樹非遞迴遍歷,說實話,我自己也挺怕遞迴轉成非遞迴的,因為有些轉起來比較簡單,有些轉起來就很困難了,這次我們來試試二叉樹的非遞迴遍歷,難度倒是不算大.
前序遍歷的非遞迴寫法
...
好久沒寫, 忙於實習以及晚上刷刷題, 這次來寫一下平時很多人都很畏懼的二叉樹非遞迴遍歷,說實話,我自己也挺怕遞迴轉成非遞迴的,因為有些轉起來比較簡單,有些轉起來就很困難了,這次我們來試試二叉樹的非遞迴遍歷,難度倒是不算大.
-
前序遍歷的非遞迴寫法
前序遍歷的非遞迴寫法要簡單不少,我們來簡單捋一下思路,我們需要先遍歷根節點,再遍歷左子樹的節點,再遍歷右子樹的節點,完成遍歷.另外,一般來說,由遞迴轉化為非遞迴,我們都需要用到棧,這裡也不例外.下面直接上程式碼,原理都在程式碼裡面進行解釋.
void preOrder(TreeNode* root)
{
if(root == nullptr)
{
return;
}
stack<int> s;
auto p = root;
while(!s.empty() || p)
{
//直接訪問樹的最左節點,因為是先序遍歷所以每次訪問先列印節點的值
while(p)
{
s.push(p);
cout<<p.val<<endl;
p = p->left;
}
if(!s.empty())
{
auto node = s.top();
s.pop();
p = node->right;
}
}
}
-
中序遍歷的非遞迴寫法
在三種非遍歷演算法中,中序遍歷應該是最簡單的了.實現程式碼q其實比較好玩的是和前序遍歷基本一樣(笑),只是改了一下輸出的位置.
void inOrder(TreeNode* root)
{
if(root == nullptr)
{
return;
}
stack<TreeNode*> s;
auto p = root;
while(!s.empty() || p)
{
//到達樹的最左節點,由於是中序遍歷,所以先不列印節點的值
while(p)
{
s.push(p);
p = p->left;
}
if(!s.empty())
{
auto node = s.top();
s.pop();
cout<<node.val<<endl;
p = node->right;
}
}
}
-
後序遍歷的非遞迴寫法
這個應該是三種非遞迴的寫法中最難的了,因為我們需要判斷當我們從子樹返回的時候判斷是從左子樹返回還是從右子樹返回的,所以我們需要一個prev指標來儲存我們上一次訪問的指標,其餘的部分其實和之前也沒有差很多.
void postOrder(TreeNode* root)
{
if(root == nullptr)
{
return;
}
stack<TreeNode*> s;
auto p = node;
TreeNode* prev = nullptr;
while(!s.empty() || p)
{
while(p)
{
s.push(p);
p = p->left;
}
if(!s.empty())
{
auto node = s.top();
s.pop();
if(!node->right || node->right == prev)
{
cout<<node->val;
prev = node;
}
else
{
s.push(node);
p = node->right;
}
}
}
}
總結: 其實上面的程式碼風格十分統一,我個人覺得理解起來還是很簡單的,主要核心還是理解遍歷的順序問題,我們每次都先訪問到樹的最左邊,然後不斷的壓棧,思路其實並不難理解.