当我们需要实现二叉查找树和二叉堆的时候，自然而然我们想到使用二叉树去实现遍历，那么你是否清楚如何实现二叉树中序的遍历呢?有兴趣的小伙伴可以跟小编一起来看看哦。
二叉树的中序遍历，通常用递归是遍历很容易实现的，但如果用迭代算法就有一定的难度了;
二叉树的中序遍历，其顺序就是——左子树，根节点，右子树，对于遍历来说，我们先从根结点开始，访问到根结点时，这个时候是不需要将根结点入列表的，可以先将它入栈，之后就好根据其peek()函数去访问到根结点的右子树了;接下来我们就希望一直访问到的是左子树，并将左孩子入列表，右子树是最后访问到的。
代码实现如下所示：
非递归的方式：
public static class TreeNode
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int val)
{
data = val;
}
}
/**
*非递归
*/
public List<Integer> inorderTraversal(TreeNode root)
{
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty())
{
while (root != null)
{
stack.push(root);
root = root.left;
}
if (!stack.isEmpty())
{
list.add(stack.peek().data);
root = stack.peek().right;
stack.pop();
}
}
return list;
}递归方式：
/**
* 递归
*/
public List<Integer> inorderTraversal(TreeNode root)
{
List<Integer> list = new ArrayList<>();
if (root == null)
return list;
inorder(root,list);
return list;
}
public static void inorder(TreeNode root, List list)
{
if (root != null)
{
inorder(root.left,list);
list.add(root.data);
inorder(root.right,list);
}
}主函数：
public static void main(String[] args)
{
TreeNode p = new TreeNode(1);
p.left = new TreeNode(2);
p.right = new TreeNode(3);
p.left.left = new TreeNode(4);
p.left.right = new TreeNode(5);
p.right.right = new TreeNode(6);
Tree13 t = new Tree13();
List<Integer> list = t.inorderTraversal(p);
for (int i = 0; i < list.size(); i++)
{
System.out.print(list.get(i) + " ");
}
}运行结果：
4 2 5 1 3 6
好了，以上就是本篇文章的所有内容了，还想了解更多java常见问答信息的话，记得关注本站消息。
推荐阅读：