重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
本篇内容主要讲解“Java实现二叉树的遍历方法是什么”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Java实现二叉树的遍历方法是什么”吧!
十载的商河网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都营销网站建设的优势是能够根据用户设备显示端的尺寸不同,自动调整商河建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联从事“商河网站设计”,“商河网站推广”以来,每个客户项目都认真落实执行。
遍历或称周游,traversal。系统地访问数据结构中的节点,每个节点都正好被访问到一次。
三种深度优先遍历的递归定义:
前序法(tLR次序,preorder traversal):访问根结点,按前序遍历左子树;按前序遍历右子树。
中序法(LtR次序,inorder traversal):按中序遍历左子树;访问根结点;按中序遍历右子树。
后序法(LRt次序,postorder traversal):按后序遍历左子树;按后序遍历右子树;访问根结点。
public static ListpreOrderTraverseByRecursion(BinaryTreeNode root, List list) { if (root != null) { list.add(root.getKey());//前序法访问节点 preOrderTraverseByRecursion(root.getLeft(), list); //list.add(root.getKey());//中序法访问节点 preOrderTraverseByRecursion(root.getRight(), list); //list.add(root.getKey());//后序法访问节点 } return list; }
递归算法非常简洁,推荐使用,当前的编译系统优化效率很不错了。特殊情况用栈模拟递归,深度优先遍历的回溯特点和栈的工作原理一致,有些应用环境资源限制不适合递归。
实现
/** * 先序遍历(非递归) * 通过栈来避免递归(有节点入栈) * * @param root */ public static ListpreOrderTraverseByNonRecursion(BinaryTreeNode root) { List list = new ArrayList<>();// 用于存放遍历后的结果 Stack stack = new Stack();// 用于存放右子树节点 BinaryTreeNode p = root; //左子树和右子树都未遍历时,遍历 while (p != null || stack.size() > 0) { if (p != null) { //左子树不为空时,遍历左子树 list.add(p.getKey());//当前节点输出 stack.push(p.getRight());//右子树入栈,待左子树遍历完后遍历右子树 p = p.getLeft();//遍历左子树 } else { //左子树遍历完后,遍历右子树 p = stack.pop(); } } return list; }
实现
/** * 中序遍历(非递归) * * @param root */ public static ListinOrderTraverseByNonRecursion(BinaryTreeNode root) { List list = new ArrayList<>(); Stack stack = new Stack<>(); BinaryTreeNode current = root; //遍历节点的左子树并将根结点入栈,直到左子树为null时,然后出栈获取节点并遍历该节点的右子树的左子树直到为null while(current != null || !stack.empty()){ if(current != null){ stack.push(current); current = current.getLeft(); }else{ BinaryTreeNode top = stack.pop(); list.add(top.getKey()); current = top.getRight(); } } return list; }
实现
/** * 后续遍历(非递归) * * @param root */ public static ListpostOrderTraverseByNonRecursion(BinaryTreeNode root) { Stack stack = new Stack<>(); List list = new ArrayList<>(); stack.push(root); BinaryTreeNode current; while (stack.isEmpty() == false) { current = stack.pop(); if (current != null) { list.add(current.getKey()); stack.push(current.getLeft()); stack.push(current.getRight()); } } Collections.reverse(list); return list; }
从二叉树的第0层(根结点)开始,自上而下,追层遍历;在同一层中,按照从左到右的顺序对节点逐一访问。 特点是先遍历先访问,符合队列的特征,通过队列来实现。 实现如下:
/** * 层序遍历(宽度优先遍历) * 特点是先进先出,符合队列的特性 * * @param root * @return */ public static ListlayerOrderTraverse(BinaryTreeNode root) { List list = new ArrayList<>(); LinkedList queue = new LinkedList<>(); BinaryTreeNode current; queue.offer(root); while (!queue.isEmpty()){ current = queue.poll(); list.add(current.getKey()); if(current.getLeft() != null){ queue.addLast(current.getLeft()); } if(current.getRight() != null){ queue.addLast(current.getRight()); } } return list; }
先来个结论及说明:
仅一个先(中、后)序序列不能构造唯一一颗二叉树(原因:无法确定左右子树或根结点)
仅先(后)序序列和中序序列可以构造唯一一颗二叉树(原因:先序序列和后序序列无法构造唯一一颗二叉树)
用扩充先(后)序序列可以构造唯一一颗二叉树
用扩充中序序列不能构造唯一一颗二叉树
实现:
/** * 根据先序序列和中序序列构造二叉树(递归实现) ** 先序序列第一个元素是树的根结点,从中序序列中找出与根结点所在位置k: * 1.确定根结点的左子树和右子树的中序序列:该位置之前的元素就是根结点左子树的中序序列,该位置之后的元素就是根结点的右子树的中序序列 * 2.确定根结点的左子树和右子树的先序序列:先序序列第一个元素往后k元素就是根结点左子树的先序序列,k+1位置之后就是根结点右子树的先序序列 *
*
* perOrder[i]~perOrder[j] 是子树的先序序列 * inOrder[s]~inOrder[t] 是子树的中序序列 * * @param perOrder * @param inOrder * @param i * @param j * @param s * @param t * @return */ public static BinaryTreeNode buildTreeByPerOrderAndInOrder(Integer[] perOrder, Integer[] inOrder, int i, int j, int s, int t) { if (i > j) { return null; } BinaryTreeNode root = new BinaryTreeNode(perOrder[i]); int k; k = s; while (k <= t && inOrder[k] != perOrder[i]) { k++; } if (k > t) { return null; } root.setLeft(buildTreeByPerOrderAndInOrder(perOrder, inOrder, i + 1, j + k - s, s, k - 1)); root.setRight(buildTreeByPerOrderAndInOrder(perOrder, inOrder, i + k - s + 1, j, k + 1, t)); return root; }
一个节点的左子树和右子树存在三种组合方式,左子树为null,右子树为null,左右子树都不为null。 运用递归思想时,按这三种情况分析左右子树的后序序列和中序序列。实现如下:
/** * 根据后序序列和中序序列构造二叉树(递归实现) * * postOrder[i]~postOrder[j]是子树的后序序列 * inOrder[s]~inOrder[t]是子树的中序序列 * * @param postOrder * @param inOrder * @param i * @param j * @param s * @param t * @return */ public static BinaryTreeNode buildTreeByPostOrderAndInOrder(Integer[] postOrder, Integer[] inOrder, int i, int j, int s, int t) { if (i > j) { return null; } BinaryTreeNode root = new BinaryTreeNode(postOrder[j]); int k; k = s; while (k <= t && inOrder[k] != postOrder[j]) { k++; } if (k > t) { return null; } //左子树个数 int countLeft = k - s; //右子树个数 int countRight = t - k; if (countLeft == 0) { //左子树为null root.setRight(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - countRight, j - 1, t - countRight + 1, t)); } else if (countRight == 0) { //右子树为null root.setLeft(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - countLeft, j - 1, t - countLeft, t - countRight - 1)); } else { //左、右子树不为null root.setLeft(buildTreeByPostOrderAndInOrder(postOrder, inOrder, i, i + countLeft - 1, s, s + countLeft - 1)); root.setRight(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - 1 - countRight + 1, j - 1, t - countRight + 1, t)); } return root; }
到此,相信大家对“Java实现二叉树的遍历方法是什么”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!