C++ 非遞歸實現二叉樹的前中後序遍歷

二叉樹的前序遍歷

在不使用遞歸的方式遍歷二叉樹時,我們可以使用一個棧模擬遞歸的機制。二叉樹的前序遍歷順序是:根 → 左子樹 → 右子樹,我們可以先將二叉樹的左路結點入棧,在入棧的同時便對其進行訪問,此時就相當於完成瞭根和左子樹的訪問,當左路結點入棧完畢後再從棧頂依次取出結點,並用同樣的方式訪問其右子樹即可。

具體步驟如下:

  1. 將左路結點入棧,入棧的同時訪問左路結點。
  2. 取出棧頂結點top。
  3. 準備訪問top結點的右子樹。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
	//前序遍歷
	vector<int> preorderTraversal(TreeNode* root) {
		stack<TreeNode*> st; //輔助棧
		vector<int> ret; //用於存放前序遍歷的結果
		TreeNode* cur = root;
		while (cur || !st.empty())
		{
			//1、將左路結點入棧,入棧的同時訪問左路結點
			while (cur)
			{
				st.push(cur);
				ret.push_back(cur->val);
				cur = cur->left;
			}
			//2、取出棧頂結點
			TreeNode* top = st.top();
			st.pop();
			//3、準備訪問其右子樹
			cur = top->right;
		}
		return ret; //返回前序遍歷結果
	}
};

二叉樹的中序遍歷

二叉樹的中序遍歷順序是:左子樹 → 根 → 右子樹,我們可以先將二叉樹的左路結點入棧,當左路結點入棧完畢後,再從棧頂依次取出結點,在取出結點的同時便對其進行訪問,此時就相當於先訪問瞭左子樹再訪問瞭根,之後再用同樣的方式訪問取出結點的右子樹即可。

具體步驟如下:

  1. 將左路結點入棧。
  2. 取出棧頂結點top並訪問。
  3. 準備訪問top結點的右子樹。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
	//中序遍歷
	vector<int> inorderTraversal(TreeNode* root) {
		stack<TreeNode*> st; //輔助棧
		vector<int> ret; //用於存放中序遍歷的結果
		TreeNode* cur = root;
		while (cur || !st.empty())
		{
			//1、將左路結點入棧
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}
			//2、取出棧頂結點並訪問
			TreeNode* top = st.top();
			st.pop();
			ret.push_back(top->val);
			//3、準備訪問其右子樹
			cur = top->right;
		}
		return ret; //返回中序遍歷結果
	}
};

二叉樹的後序遍歷

二叉樹的後序遍歷順序是:左子樹 → 右子樹 → 根,我們可以先將二叉樹的左路結點入棧,當左路結點入棧完畢後,再觀察棧頂結點,若棧頂結點的右子樹為空,或棧頂結點的右子樹已經被訪問過瞭,則棧頂結點可以出棧並訪問,若棧頂結點的右子樹還未被訪問,則用同樣的方式訪問棧頂結點的右子樹,直到其右子樹被訪問後再訪問該結點,這時的訪問順序遵循瞭二叉樹的後序遍歷所要求的順序。

具體步驟如下:

  1. 將左路結點入棧。
  2. 觀察棧頂結點top。
  3. 若top結點的右子樹為空,或top結點的右子樹已經訪問過瞭,則訪問top結點。訪問top結點後將其從棧中彈出,並更新上一次訪問的結點為top。
  4. 若top結點的右子樹還未被訪問,則準備訪問其右子樹。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
	//後序遍歷
	vector<int> postorderTraversal(TreeNode* root) {
		stack<TreeNode*> st; //輔助棧
		vector<int> ret; //用於存放後序遍歷的結果
		TreeNode* cur = root;
		TreeNode* prev = nullptr; //記錄上一次訪問的結點
		while (cur || !st.empty())
		{
			//1、將左路結點入棧
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}
			//2、取出棧頂結點
			TreeNode* top = st.top();
			//3、若取出結點的右子樹為空,或右子樹已經訪問過瞭,則訪問該結點
			if (top->right == nullptr || top->right == prev)
			{
				//訪問top結點後將其從棧中彈出
				st.pop();
				ret.push_back(top->val);
				//更新上一次訪問的結點為top
				prev = top;
			}
			else //4、若取出結點的右子樹還未被訪問,則準備訪問其右子樹
			{
				cur = top->right;
			}
		}
		return ret; //返回後序遍歷結果
	}
};

註意: 看動圖演示時請結合所給代碼,動圖是嚴格按照代碼的邏輯制作的。

到此這篇關於C++ 非遞歸實現二叉樹的前中後序遍歷的文章就介紹到這瞭,更多相關二叉樹前中後序遍歷內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: