非递归实现遍历二叉树

非递归实现二叉树主要利用queue和stack的特点，对于层次遍历二叉树主要运用queue队头出，队尾插入，先进先出的特点，先将根插入队尾，然后输出队头的元素，同时将队头的左子树和右子树元素插入队尾，依次输出输出队头的元素，同时将队头的左子树和右子树元素插入队尾，直到队列为空。

目前创新互联已为上千的企业提供了网站建设、域名、网站空间、成都网站托管、企业网站设计、东莞网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

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;

}

}

}