Java中如何实现二叉树的递归与非递归四种遍历方法？

本文共计2014个文字，预计阅读时间需要9分钟。

二叉树的遍历可以分为前序、中序、后序和层次遍历。前序遍历是指先访问根节点，然后遍历左子树，最后遍历右子树；中序遍历是指先遍历左子树，访问根节点，最后遍历右子树；后序遍历是指先遍历左子树，然后遍历右子树，最后访问根节点；层次遍历是指从上到下，从左到右依次访问每一层的节点。

二叉树的遍历可以分为前序、中序、后序、层次遍历。

前中后是指何时访问中间节点，即前序遍历，遍历节点的顺序为：中—>左—>右；

中序遍历，遍历节点的顺序为：左—>中—>右；

后序遍历，遍历节点的顺序为：左—>右—>中。

前序遍历

递归实现

public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" "); preorder_Traversal(root.left); preorder_Traversal(root.right); }

非递归过程如下：

1.每遍历一个节点的时候，先节点入栈，然后寻找当前节点的左子节点。