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