采用递归方式实现
节点类
public class Node { private int value; //父节点 private Node fNode; //左节点 private Node left; //右节点 private Node right; //是否已经打印过 private boolean sign = false; public Node() { } public boolean isSign() { return sign; } public void setSign(boolean sign) { this.sign = sign; } public Node getfNode() { return fNode; } public void setfNode(Node fNode) { this.fNode = fNode; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; //设置左节点的父类 left.setfNode(this); } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; //设置右节点的父类 right.setfNode(this); } public int getValue() { return value; } public Node setValue(int value) { this.value = value; return this; } }
递归方法
//后序遍历二叉树 public static void reducer(Node node) { if (node == null) return; //判断当前节点是否已经打印,如果没有就进去判断它的左右节点 if (!node.isSign()) { /* if:如果左节点不为空并且没有被打印,那么就说明该节点未被调用过,进行递归操作 else if: 判断完左节点就判断右节点,这是后续遍历的操作顺序 else : 如果左节点和右节点都打印了,那么就打印当前节点的值,并且回退到上一个节点(父节点) */ if (node.getLeft() != null && !node.getLeft().isSign()) { reducer(node.getLeft()); } else if (node.getRight() != null && !node.getRight().isSign()) { reducer(node.getRight()); } else { System.out.print(node.getValue()); node.setSign(true); //如果父节点为空说明已经遍历完了 if (node.getfNode() != null) { reducer(node.getfNode()); } else { return; } } } }
测试
public class BinaryIterator { public static void main(String[] args) { //构建顶级节点的左节点 Node l = new Node().setValue(2); l.setLeft(new Node().setValue(3)); l.setRight(new Node().setValue(4)); //构建顶级节点的右节点 Node r = new Node().setValue(5); r.setLeft(new Node().setValue(6)); r.setRight(new Node().setValue(7)); //顶节点(起始节点) Node node = new Node(); node.setLeft(l); node.setRight(r); node.setValue(1); //测试 reducer(node);//rest:3426751 } }
草图(想要透彻理解,必须要慢慢根据图进行推演)