非递归实现二叉树主要利用queue和stack的特点，对于层次遍历二叉树主要运用queue队头出，队尾插入，先进先出的特点，先将根插入队尾，然后输出队头的元素，同时将队头的左子树和右子树元素插入队尾，依次输出输出队头的元素，同时将队头的左子树和右子树元素插入队尾，直到队列为空。
创新互联是一家专注于网站设计制作、
成都网站建设与策划设计,城固网站建设哪家好?
创新互联做网站,专注于网站建设十年,网设计领域的专业建站公司;建站业务涵盖:城固等地区。城固做网站价格咨询:18980820575
void levelorder()
{
queue *>s;
if (_root == NULL)
return;
s.push(_root);
while (!s.empty())
{
BinaryTreeNode *front=s.front();
cout << front->_data << " ";
if (front->_left)
s.push(front->_left);
if (front->_right)
s.push(front->_right);
s.pop();
}
}
非递归实现二叉树前序遍历主要运用stack的先进后出的特点，先把根压入栈里，同时先把左子树的左子树元素以此压入栈底，最后左子树的最后一个元素压入栈底之后，再将栈底元素弹出栈，再判断栈底最后一个元素的右子树，利用以上的方法。代码如下：
void prevorder()
{
stack *>s;
if (_root == NULL)
return;
s.push(_root);
while (!s.empty())
{
BinaryTreeNode *cur = s.top();
cout << cur->_data << " ";
s.pop();
if (cur->_right)
s.push(cur->_right);
if (cur->_left)
s.push(cur->_left);
}
}
非递归实现二叉树中序遍历主要运用stack的先进后出的特点，先把根压入栈里，同时先把左子树的左子树元素以此压入栈底，最后左子树的最后一个元素压入栈底之后，判断栈底最后一个元素的右子树，利用以上的方法。代码如下：
void inorder()
{
stack *>s;
if (_root == NULL)
return;
BinaryTreeNode *cur = _root;
while (cur||!s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cout << s.top()->_data << " ";
cur = s.top()->_right;
s.pop();
}
}
非递归实现二叉树后序遍历主要运用stack的先进后出的特点，在利用前序和后序的共同特点
void postorder()
{
stack *>s;
if (_root == NULL)
return;
BinaryTreeNode *cur = _root;
BinaryTreeNode *prev = NULL;
s.push(cur);
while (cur || !s.empty())
{
while (cur->_left&&cur->_left!=prev)
{
s.push(cur->_left);
cur = cur->_left;
}
if (s.top()->_right&&s.top()->_right != prev)
{
cur = s.top()->_right;
s.push(cur);
}
else
{
cout << s.top()->_data << " ";
prev = s.top();
s.pop();
cur = s.top();
cur->_left =NULL;
}
}
}
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
网站栏目：非递归实现遍历二叉树-创新互联
网页地址：
http://cdkjz.cn/article/jgspg.html
