树的定义本是递归定义,所以采用递归的方法实现遍历算法,更加让人理解,且代码简单方便。若采用非递归的方法实现,须得利用栈模拟实现。


栈的特点(后进先出)


非递归实现二叉树的前序遍历:

原理如图所示:


参考代码如下:

void _PrevOrder(Node* root)//非递归实现前序遍历

{

stack<Node*> s;

if(root == NULL)

return;

s.push(root);

while (!s.empty())

{

root = s.top();

cout<<root->_data<<" ";

s.pop();

if (root->_right)

{

s.push(root->_right);

}

if(root->_left)

{

s.push(root->_left);

}

}

}


非递归实现二叉树的中序遍历


原理:

先从二叉树的最左边进行遍历(1、2、3),且一边遍历,一边入栈,当当到达结点3时,因为3的左右子树都为空,此时需弹出结点3,栈顶元素变为2,再遍历2的右子树的左结点,因为4的左右子树都为空,此时需弹出2,压人4,左子树已遍历结束,弹出4,再弹出1,依照遍历左子树,遍历右子树。

参考代码如下:

void _InOrder(Node* root)//非递归实现中序遍历

{

stack<Node*> s;

Node* cur = root;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

Node* top = s.top();

cout<<top->_data<<" ";

s.pop();

cur = top->_right;

}

}


非递归实现二叉树的后序遍历

步骤:

1、借助栈实现后序遍历,先找到最左边且为最下边的结点3(一边找,一边入栈)

2、若3没有右子树,则弹出3且打印结点3,还需要引入一个指向当前弹出结点的指针prev

3、若3有右子树,则需要遍历右子树,遍历结束才可以打印并弹出结点3,重复此三步骤可完成后序遍历。

参考代码如下:

void _PosOrder(Node* root)//非递归实现后序遍历

{

Node* cur = root;

Node* prev = NULL;

stack<Node*> s;

if(root == NULL)

return;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cur = s.top();

if(cur->_right == NULL || cur->_right == prev)

{

cout<<cur->_data<<" ";

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;

}

}

}