本文参考了其他文章,并非原创,文末有原文链接
首先一点:桟和递归本质是一样的,这也是为什么非递归实现需要借助桟(借助桟的先进后出属性)
1. 节点数据结构
//Binary Tree Node typedef struct node { int data; struct node* lchild; //左孩子 struct node* rchild; //右孩子 }BTNode;
前序、中序、后序遍历的非递归实现中,前序和中序最简单,后序遍历实现起来有点难度。
2. 前序遍历
- 核心:由于遍历右节点需要借助根节点,所以我们在遍历根节点的同时需要将根节点存储在stack中
void PreOrderWithoutRecursion1(BTNode* root) { if (root == NULL) return; BTNode* p = root; stack<BTNode*> s; while (!s.empty() || p) { //边遍历边打印,并存入栈中,以后需要借助这些根节点进入右子树 while (p) { cout << setw(4) << p->data; s.push(p); p = p->lchild; } //当p为空时,说明根和左子树都遍历完了,该进入右子树了 if (!s.empty()) { p = s.pop(); p = p->rchild; } } cout << endl; }
3. 中序遍历
- 核心:由于遍历右节点需要借助根节点,所以我们在遍历根节点的同时需要将根节点存储在stack中
//中序遍历 void InOrderWithoutRecursion1(BTNode* root) { //空树,直接返回 if (root == NULL) return; //树非空 BTNode* p = root; //桟用于存储所有根节点 stack<BTNode*> s; while (!s.empty() || p) { //一直遍历到左子树最下边,边遍历边保存根节点到栈中 while (p) { s.push(p); p = p->lchild; } //当p为空时,说明已经到达左子树最下边,这时需要出栈了 if (!s.empty()) { p = s.pop(); cout << setw(4) << p->data; //进入右子树,开始新的一轮左子树遍历(这是递归的自我实现) p = p->rchild; } } }
4. 后序遍历
- 核心:后序遍历和前序,中序遍历有点不同,在对根节点(每个树的相对根节点)进行访问前,需要先判断是不是已经访问过右孩子节点了
//后序遍历 void PostOrderWithoutRecursion(BTNode* root) { if (root == NULL) return; stack<BTNode*> s; //pCur:当前访问节点,pLastVisit:上次访问节点 BTNode* pCur, *pLastVisit; //pCur = root; pCur = root; pLastVisit = NULL; //先把pCur移动到左子树最下边 while (pCur) { s.push(pCur); pCur = pCur->lchild; } while (!s.empty()) { //开始从桟中取出存储的根节点 pCur = s.pop(); //一个根节点被访问的前提是:无右子树或右子树已被访问过 if (pCur->rchild == NULL || pCur->rchild == pLastVisit) { cout << setw(4) << pCur->data; //修改最近被访问的节点 pLastVisit = pCur; } //不满足上面的条件,说明当前根节点有右孩子节点,且其右孩子节点还未被访问,必须先访问右孩子节点 else { //根节点再次入栈 s.push(pCur); //进入右子树 pCur = pCur->rchild; //进入有子树后,需要将右子树的所有根节点也存放到桟中 while (pCur) { s.push(pCur); pCur = pCur->lchild; } } } cout << endl; }
原文链接:https://blog.csdn.net/zhangxiangDavaid/article/details/37115355#commentBox