在这里我将写出两种二叉树便利的方法 第一种，是基于两个队列q1,q2，将当前节点放在q1,子节点放在q2，然后将q1出队列。然后再将q2的复制到q1。再继续执行。这样，每次只有q1在出队列输出，每次输出的都是按照书序的
第二种 基于一个数组。有两个指针，一个指向头部head，一个指向尾部的end。让head指针往结尾跑，而end指针始终指向数组的末尾。如果有了新的子节点，就往数组中增加。所以，始终，这两个指针都是运动的。
import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;/** * Created by yangrui on 2017/2/7. */public class TreeNode { PRivate int value; public int getValue() { return value; } /** * 左子树 */ private TreeNode tl; /** * 右子树 */ private TreeNode tr; public TreeNode(int value) { this.value = value; } public TreeNode() { } public static void main(String[] args) { TreeNode root = new TreeNode(1); TreeNode node2 = new TreeNode(2); TreeNode node3 = new TreeNode(3); TreeNode node4 = new TreeNode(4); TreeNode node5 = new TreeNode(5); TreeNode node6 = new TreeNode(6); TreeNode node7 = new TreeNode(7); TreeNode node8 = new TreeNode(8); root.tl = node2; root.tr = node3; node2.tl = node4; node2.tr = node5; node3.tr = node6; node5.tl = node7; node5.tr = node8; root.traversal2(root); } public void traversal2(TreeNode node) { Queue<TreeNode> q1 = new LinkedList<>(); Queue<TreeNode> q2 = new LinkedList<>(); q1.add(node); while (!q1.isEmpty()) { while (!q1.isEmpty()) { TreeNode temp = q1.poll(); System.out.println(temp.getValue()); if (temp.tl!=null){ q2.add(temp.tl); } if (temp.tr!=null){ q2.add(temp.tr); } } Queue<TreeNode> temp = new LinkedList<>(); temp=q1; q1=q2; q2=temp; } } public void traversal(TreeNode node) { if (node==null){ return; } int head=0; int end = 0; List<TreeNode> list =new ArrayList<>(); list.add(node); System.out.println(node.getValue()); while (head<list.size()){ end=list.size(); while (head<end){ if (list.get(head).tl!=null){ list.add(list.get(head).tl); } if (list.get(head).tr!=null){ list.add(list.get(head).tr); } head++; } } }}新闻热点
疑难解答
