C++ 非遞歸實現(xiàn)二叉樹的前中后序遍歷

更新時間：2021年11月23日 15:19:40 作者：2021dragon

本文將結(jié)合動畫和代碼演示如何通過C++ 非遞歸實現(xiàn)二叉樹的前中后序的遍歷，代碼具有一定的價值，感興趣的同學(xué)可以學(xué)習(xí)一下

二叉樹的前序遍歷

在不使用遞歸的方式遍歷二叉樹時，我們可以使用一個棧模擬遞歸的機制。二叉樹的前序遍歷順序是：根 → 左子樹 → 右子樹，我們可以先將二叉樹的左路結(jié)點入棧，在入棧的同時便對其進行訪問，此時就相當(dāng)于完成了根和左子樹的訪問，當(dāng)左路結(jié)點入棧完畢后再從棧頂依次取出結(jié)點，并用同樣的方式訪問其右子樹即可。

具體步驟如下：

將左路結(jié)點入棧，入棧的同時訪問左路結(jié)點。
取出棧頂結(jié)點top。
準(zhǔn)備訪問top結(jié)點的右子樹。

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; //用于存放前序遍歷的結(jié)果
		TreeNode* cur = root;
		while (cur || !st.empty())
		{
			//1、將左路結(jié)點入棧，入棧的同時訪問左路結(jié)點
			while (cur)
			{
				st.push(cur);
				ret.push_back(cur->val);
				cur = cur->left;
			}
			//2、取出棧頂結(jié)點
			TreeNode* top = st.top();
			st.pop();
			//3、準(zhǔn)備訪問其右子樹
			cur = top->right;
		}
		return ret; //返回前序遍歷結(jié)果
	}
};

二叉樹的中序遍歷

二叉樹的中序遍歷順序是：左子樹 → 根 → 右子樹，我們可以先將二叉樹的左路結(jié)點入棧，當(dāng)左路結(jié)點入棧完畢后，再從棧頂依次取出結(jié)點，在取出結(jié)點的同時便對其進行訪問，此時就相當(dāng)于先訪問了左子樹再訪問了根，之后再用同樣的方式訪問取出結(jié)點的右子樹即可。

具體步驟如下：

將左路結(jié)點入棧。
取出棧頂結(jié)點top并訪問。
準(zhǔn)備訪問top結(jié)點的右子樹。

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; //用于存放中序遍歷的結(jié)果
		TreeNode* cur = root;
		while (cur || !st.empty())
		{
			//1、將左路結(jié)點入棧
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}
			//2、取出棧頂結(jié)點并訪問
			TreeNode* top = st.top();
			st.pop();
			ret.push_back(top->val);
			//3、準(zhǔn)備訪問其右子樹
			cur = top->right;
		}
		return ret; //返回中序遍歷結(jié)果
	}
};

二叉樹的后序遍歷

二叉樹的后序遍歷順序是：左子樹 → 右子樹 → 根，我們可以先將二叉樹的左路結(jié)點入棧，當(dāng)左路結(jié)點入棧完畢后，再觀察棧頂結(jié)點，若棧頂結(jié)點的右子樹為空，或棧頂結(jié)點的右子樹已經(jīng)被訪問過了，則棧頂結(jié)點可以出棧并訪問，若棧頂結(jié)點的右子樹還未被訪問，則用同樣的方式訪問棧頂結(jié)點的右子樹，直到其右子樹被訪問后再訪問該結(jié)點，這時的訪問順序遵循了二叉樹的后序遍歷所要求的順序。

具體步驟如下：

將左路結(jié)點入棧。
觀察棧頂結(jié)點top。
若top結(jié)點的右子樹為空，或top結(jié)點的右子樹已經(jīng)訪問過了，則訪問top結(jié)點。訪問top結(jié)點后將其從棧中彈出，并更新上一次訪問的結(jié)點為top。
若top結(jié)點的右子樹還未被訪問，則準(zhǔn)備訪問其右子樹。

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; //用于存放后序遍歷的結(jié)果
		TreeNode* cur = root;
		TreeNode* prev = nullptr; //記錄上一次訪問的結(jié)點
		while (cur || !st.empty())
		{
			//1、將左路結(jié)點入棧
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}
			//2、取出棧頂結(jié)點
			TreeNode* top = st.top();
			//3、若取出結(jié)點的右子樹為空，或右子樹已經(jīng)訪問過了，則訪問該結(jié)點
			if (top->right == nullptr || top->right == prev)
			{
				//訪問top結(jié)點后將其從棧中彈出
				st.pop();
				ret.push_back(top->val);
				//更新上一次訪問的結(jié)點為top
				prev = top;
			}
			else //4、若取出結(jié)點的右子樹還未被訪問，則準(zhǔn)備訪問其右子樹
			{
				cur = top->right;
			}
		}
		return ret; //返回后序遍歷結(jié)果
	}
};

注意：看動圖演示時請結(jié)合所給代碼，動圖是嚴(yán)格按照代碼的邏輯制作的。

到此這篇關(guān)于C++ 非遞歸實現(xiàn)二叉樹的前中后序遍歷的文章就介紹到這了,更多相關(guān)二叉樹前中后序遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: