前序遍历的非递归实现
以如下二叉树为例,分析:
根据先序遍历的顺序,先访问根结点,再访问左子树,最后访问右子树,而对于每个子树来说,又按照同样的访问顺序进行遍历。上图的先序遍历顺序为:ABDECF思路分析
非递归的实现思路如下:
对于任意节点P,
- 输出结点P,然后将其入栈,再看P的左孩子是否为空;
- 若P的左孩子不为空,则置P的左孩子为当前节点,重复上一步的过程;
- 若P的左孩子为空,则将栈顶节点出栈,但不输出,并将出栈结点的右孩子置为当前节点,看其是否为空;
- 若不为空,则循环第1步的操作;
- 如果为空,则继续出栈,但不输出,同时将出栈节点的右孩子置为当前节点,看其是否为空,重复第4步和第5步的操作;
- 直到当前节点P为NULL并且栈空,便利结束。
实例分析
下面以上图为例详细分析其先序遍历的非递归实现过程:
首先,从根节点A开始,根据操作1),输出A,并将其入栈,由于A的左孩子不为空,根据操作2),将B置为当前节点,再根据操作1),将B输出,并将其入栈,由于B的左孩子也不为空,根据操作2),将D置为当前节点,再根据操作1),输出D,并将其入栈,此时输出序列为ABD;
由于D的左孩子为空,根据操作3),将栈顶节点D出栈,但不输出,并将其右孩子置为当前节点;
由于D的右孩子为空,根据操作5),继续将栈顶节点B出栈,但不输出,并将其右孩子置为当前节点;
由于B的右孩子E不为空,根据操作1),输出E,并将其入栈,此时输出序列为:ABDE;
由于E的左孩子为空,根据操作3),将栈顶节点E出栈,但不输出,并将其右孩子置为当前节点;
由于E的右孩子为空,根据操作5),继续将栈顶节点A出栈,但不输出,并将其右孩子置为当前节点;
由于A的右孩子C不为空,根据操作1),输出C,并将其入栈,此时输出序列为:ABDEC;
由于A的左孩子F不为空,根据操作2),则将F置为当前节点,再根据操作1),输出F,并将其入栈,此时输出序列为:ABDECF;
由于F的左孩子为空,根据操作3),将栈顶节点F出栈,但不输出,并将其右孩子置为当前节点;
由于F的右孩子为空,根据操作5),继续将栈顶元素C出栈,但不输出,并将其右孩子置为当前节点;
此时栈空,且C的右孩子为NULL,因此遍历结束。
代码实现
根据以上思路,前序遍历的非递归实现代码如下:1 | void pre_traverse(BTree pTree) |