二叉树中序遍历是如何实现?示例

XIAO 2020-05-30 17:33:27 java常见问答 4416

当我们需要实现二叉查找树和二叉堆的时候,自然而然我们想到使用二叉树去实现遍历,那么你是否清楚如何实现二叉树中序的遍历呢?有兴趣的小伙伴可以跟小编一起来看看哦。

二叉树的中序遍历,通常用递归是遍历很容易实现的,但如果用迭代算法就有一定的难度了;

二叉树的中序遍历,其顺序就是——左子树,根节点,右子树,对于遍历来说,我们先从根结点开始,访问到根结点时,这个时候是不需要将根结点入列表的,可以先将它入栈,之后就好根据其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常见问答信息的话,记得关注本站消息。

推荐阅读:

二叉树节点数该怎么计算?有几种算法?

二叉树的度是什么意思?二叉树是什么?

二叉树遍历例题及答案详解,java入门教程