二叉树（二）：三种遍历的非递归实现

本文要点：

二叉树三种遍历方式（前序、中序、后序）的非递归实现

ps：递归方法实现：递归法实现二叉树的创建与遍历

非递归的实现需要借助栈！！

前序：

首先需要判断是否是空树，是空返回；否则从根部一直向树的左子树方遍历，遍历一个访问一个，并且将其压入栈。当树不为空，并且栈不为空时，说明栈里仍有元素可访问。

void _PrevOrder_NonR(Node* root) //非递归--前序 { if(root == NULL) return ; Node* cur = root; stack<Node*> s; while (cur || !s.empty()) //cur != NULL说明仍然有子树可以被遍历 //!s.empty() 说明栈不为空时可以有数据被访问 { while (cur) { cout<<cur->_data<<" "; s.push(cur); cur = cur->_left; } Node* top = s.top(); s.pop(); cur = top->_right; //访问当前根节点的右子树 } cout<<endl; } 中序：

中序的过程与前序相似，只是访问数据的时间不同。中序是先入栈再访问，即当左子树入栈以后才访问

void _InOrder_N0nR(Node* root) //非递归--中序 { if(root == NULL) return ; Node* cur = root; stack<Node*> s; while(cur || !s.empty()) { while(cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); //此时栈顶存的是当前子树的根节点 cout<<top->_data<<" "; s.pop(); cur = top->_right; //将右子树作为左子树的子树来遍历 } cout<<endl; } 后序：

三种非递归遍历中，后序遍历是比较难理解的。后序遍历必须保证左子树和右子树都访问完以后才能访问根节点，而能访问根节点的可能是有两种：右子树已经被访问或者当前根节点的右子树为NULL。因此，就需要一个标记位pos，当当前根节点右子树和pos相等时，说明已经可以访问该根节点了。

void _PostOrder_NonR(Node* root) //非递归--后序 { Node* cur = root; Node* pos = root; stack<Node*> s; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); if (top->_right == NULL || top->_right == pos) //top存的是当前的根节点，当top的右子树为空或者top的右子树为pos，说明右子树已经遍历过， //这时就可以访问当前的根节点了 { cout<<top->_data<<" "; pos = top; s.pop(); } else { cur = top->_right; } } cout<<endl; }