前序遍历的非递归实现
以如下二叉树为例,分析:
根据先序遍历的顺序,先访问根结点,再访问左子树,最后访问右子树,而对于每个子树来说,又按照同样的访问顺序进行遍历。上图的先序遍历顺序为:ABDECF思路分析
非递归的实现思路如下:
对于任意节点P,
- 输出结点P,然后将其入栈,再看P的左孩子是否为空;
- 若P的左孩子不为空,则置P的左孩子为当前节点,重复上一步的过程;
- 若P的左孩子为空,则将栈顶节点出栈,但不输出,并将出栈结点的右孩子置为当前节点,看其是否为空;
- 若不为空,则循环第1步的操作;
- 如果为空,则继续出栈,但不输出,同时将出栈节点的右孩子置为当前节点,看其是否为空,重复第4步和第5步的操作;
- 直到当前节点P为NULL并且栈空,便利结束。