class Node { private int data; private Node leftNode; private Node rightNode; public Node(int data, Node leftNode, Node rightNode){ this.data = data; this.leftNode = leftNode; this.rightNode = rightNode; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeftNode() { return leftNode; } public void setLeftNode(Node leftNode) { this.leftNode = leftNode; } public Node getRightNode() { return rightNode; } public void setRightNode(Node rightNode) { this.rightNode = rightNode; } } public Node initNode() { Node J = new Node(8, null, null); Node H = new Node(4, null, null); Node G = new Node(2, null, null); Node F = new Node(7, null, J); Node E = new Node(5, H, null); Node D = new Node(1, null, G); Node C = new Node(9, F, null); Node B = new Node(3, D, E); Node A = new Node(6, B, C); return A; } public void printNode(Node node){ System.out.print(node.getData()); } //递归先序 public void beforeLoop(Node node){ printNode(node); if (node.leftNode !=null) { beforeLoop(node.leftNode); } if (node.rightNode !=null) { beforeLoop(node.rightNode); } } //递归中序 public void middleLoop(Node node){ if (node.leftNode !=null) { middleLoop(node.leftNode); } printNode(node); if (node.rightNode !=null) { middleLoop(node.rightNode); } } //递归后序 public void afterLoop(Node node){ if (node.leftNode !=null) { afterLoop(node.leftNode); } if (node.rightNode !=null) { afterLoop(node.rightNode); } printNode(node); } //循环先序 public void before(Node root){ Stack<Node> stack = new Stack<Node>(); Node node = root; while(node !=null || stack.size() > 0){ if(node !=null){ printNode(node); stack.push(node); node=node.leftNode; }else{ node=stack.pop(); node=node.rightNode; } } } //循环中序 public void middle(Node root){ Stack<Node> stack = new Stack<Node>(); Node node = root; while(node !=null || stack.size() > 0){ if(node !=null){ stack.push(node); node=node.leftNode; }else{ node=stack.pop(); printNode(node); node=node.rightNode; } } } //循环后序 public void after(Node root){ Stack<Node> stack = new Stack<Node>(); Stack<Node> output = new Stack<Node>(); Node node = root; while(node !=null || stack.size() > 0){ if(node !=null){ stack.push(node); output.push(node); node=node.rightNode; }else{ node=stack.pop(); node=node.leftNode; } } while (output.size() > 0){ node = output.pop(); printNode(node); } }