前言:
现在姐妹们对“java树前序遍历 中序遍历 后序遍历”可能比较注重,大家都需要分析一些“java树前序遍历 中序遍历 后序遍历”的相关知识。那么小编也在网摘上汇集了一些对于“java树前序遍历 中序遍历 后序遍历””的相关文章,希望兄弟们能喜欢,朋友们一起来了解一下吧!对于二叉树,它的特点就是任何一个节点,左节点小于父节点、右节点大于父节点遍历二叉树有多种方式,如中序遍历、层序遍历、后序遍历,中序遍历的思路就是左-->父--->右的顺序,下面给出递归和非递归的两种方法,递归很好理解,非递归就是一直找到最左节点,然后回溯节点,如果存在右节点,则重复上述过程
如将下面的二叉树使用中序遍历输出有序数组
代码如下
import java.util.ArrayList;import java.util.List;import java.util.Stack;/** * 中序遍历的非递归和递归的实现 * * @author ssj * */public class MiddleList { public static void main(String[] args) { // 创建一颗二叉树 Node root = new Node("10"); Node n6 = new Node("6"); Node n14 = new Node("14"); n6.setParent(root); n14.setParent(root); root.setLeft(n6); root.setRight(n14); Node n4 = new Node("4"); Node n8 = new Node("8"); n6.setLeft(n4); n6.setRight(n8); Node n12 = new Node("12"); Node n16 = new Node("16"); n14.setLeft(n12); n14.setRight(n16); System.out.println("---------递归遍历结果--------------------"); List list = new ArrayList(); middleListDG(root, list); System.out.println(list); System.out.println("---------非递归遍历结果--------------------"); List list2 = middleList(root); System.out.println(list2); } /** * 递归中序遍历 * * @param root * @return */ public static void middleListDG(Node root, List list) { if (root == null) { return; } middleListDG(root.left, list); list.add(root.name); middleListDG(root.right, list); } /** * 非递归中序遍历 * @param root * @return */ public static List middleList(Node root) { Stack<Node> sk = new Stack<Node>(); List list = new ArrayList(); Node n = root; while (n != null) { // 一直找到最左边的节点 while (n != null) { sk.push(n); n = n.left; } // 输出最左边的节点 while (!sk.empty()) { Node n2 = sk.pop(); list.add(n2.getName()); // 如果该节点存在右节点,先输出所有的右节点,即重复以上过程 if (n2.right != null) { n = n2.right; break; } } } return list; }}/** * 树节点 * @author ssj * */class Node { public String name; public Node left; public Node right; public Node parent = null; public String getName() { return name; } public void setName(String name) { this.name = name; } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } public Node(String name) { super(); this.name = name; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; }}
输出结果
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #java树前序遍历 中序遍历 后序遍历 #java遍历二叉树代码 #java二叉树层次遍历输出每一层元素 #java二叉树的先序中序后序遍历非递归算法 #递归算法实现二叉树的遍历