经典算法之非递归算法实现二叉树前、中、后序遍历

本文主要是介绍经典算法之非递归算法实现二叉树前、中、后序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考：https://blog.csdn.net/wardseptember/article/details/78883843

 

#include <iostream>
#include <vector>
using namespace std;typedef struct BTNode {char val;struct BTNode *left, *right;BTNode(char x) :val(x), left(nullptr), right(nullptr) {}
}BTNode, *BTree;//创建一棵二叉树
BTree createTree() {BTree pA = new BTNode('A');BTree pB = new BTNode('B');BTree pC = new BTNode('C');BTree pD = new BTNode('D');BTree pE = new BTNode('E');BTree pF = new BTNode('F');BTree pG = new BTNode('G');BTree pH = new BTNode('H');BTree pI = new BTNode('I');pA->left = pC;pA->right = pB;pC->left = pD;pC->right = pE;pB->right = pF;pD->left = pG;pE->right = pH;pF->left = pI;return pA;
}//非递归算法实现二叉树前序遍历
void preOrderNonRecursion(BTree pT) {if (pT != nullptr) {vector<BTNode *> pvec;pvec.push_back(pT);BTNode *p;while (!pvec.empty()) {//这里打印根节点，也可以指向其他操作p = pvec.back();cout << p->val;pvec.pop_back();//注意遍历顺序是：根 左 右；所以入栈顺序是：右子树 左子树if (p->right != nullptr) {pvec.push_back(p->right);}if (p->left != nullptr) {pvec.push_back(p->left);}}}
}//非递归算法实现二叉树中序遍历
void inOrderNonRecursion(BTree pT) {if (pT != nullptr) {vector<BTNode *> pvec;BTNode *q = pT;while (!pvec.empty() || q != nullptr) {while (q != nullptr) {pvec.push_back(q);q = q->left;}if (!pvec.empty()) {q = pvec.back();pvec.pop_back();//此处打印节点，也可以执行其他操作cout << q->val;q = q->right;}}}
}//用两个栈实现非递归二叉树后序遍历
//这里实现的原理是利用先序遍历原理：根  左  右
//先实现遍历：根  右  左；然后逆序就变成：左  右  根
void postOrderNonRecursion(BTree pT) {if (pT != nullptr) {vector<BTNode *> vec1;vector<BTNode *> vec2;BTNode *p;vec1.push_back(pT);while (!vec1.empty()) {//遍历根节点，存入vec2p = vec1.back();vec2.push_back(p);vec1.pop_back();//注意遍历顺序是：根 右 左；所以入栈顺序是：左子树 右子树if (p->left != nullptr) {vec1.push_back(p->left);}if (p->right != nullptr) {vec1.push_back(p->right);}}//上面的遍历顺序是：根 右 左，逆序就是：左 右 根while (!vec2.empty()) {p = vec2.back();cout << p->val;vec2.pop_back();}}
}int main() {BTree pTree = createTree();cout << "非递归算法实现二叉树前序遍历：";preOrderNonRecursion(pTree);cout << endl;cout << "非递归算法实现二叉树中序遍历：";inOrderNonRecursion(pTree);cout << endl;cout << "非递归算法实现二叉树后序遍历：";postOrderNonRecursion(pTree);cout << endl;return 0;
}

output：

非递归算法实现二叉树前序遍历：ACDGEHBFI
非递归算法实现二叉树中序遍历：GDCEHABIF
非递归算法实现二叉树后序遍历：GDHECIFBA
请按任意键继续. . .

 

 

 

这篇关于经典算法之非递归算法实现二叉树前、中、后序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---