以下是我要解析的一个二叉树的模型形状
接下来废话不多直接上代码
一种是用递归的方法，另一种是用堆栈的方法：
首先创建一棵树：
节点对象：
1 public class Node { 2 //节点数值 3 private int data; 4 //左子节点 5 private Node leftNode; 6 //右子节点 7 private Node rightNode; 8 9 public Node(int data, Node leftNode, Node rightNode) {10 this.data = data;11 this.leftNode = leftNode;12 this.rightNode = rightNode;13 }14 15 public int getData() {16 return data;17 }18 19 public void setData(int data) {20 this.data = data;21 }22 23 public Node getLeftNode() {24 return leftNode;25 }26 27 public void setLeftNode(Node leftNode) {28 this.leftNode = leftNode;29 }30 31 public Node getRightNode() {32 return rightNode;33 }34 35 public void setRightNode(Node rightNode) {36 this.rightNode = rightNode;37 }38 }
递归方式，实现树的遍历：
1 public class BinaryTreeWithNode1 { 2 3 /** 4 * 二叉树的先序中序后序排序 5 */ 6 public Node init() { //注意必须逆序建立，先建立子节点，再逆序往上建立，因为非叶子结点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错 7 Node J = new Node(8, null, null); 8 Node H = new Node(4, null, null); 9 Node G = new Node(2, null, null);10 Node F = new Node(7, null, J);11 Node E = new Node(5, H, null);12 Node D = new Node(1, null, G);13 Node C = new Node(9, F, null);14 Node B = new Node(3, D, E);15 Node A = new Node(6, B, C);16 return A; //返回根节点17 }18 19 public void printNode(Node node) {20 System.out.print(node.getData());21 }22 23 public void theFirstTraversal(Node root) { //先序遍历24 printNode(root);25 if (root.getLeftNode() != null) { //使用递归进行遍历左孩子26 theFirstTraversal(root.getLeftNode());27 }28 if (root.getRightNode() != null) { //递归遍历右孩子29 theFirstTraversal(root.getRightNode());30 }31 }32 33 public void theInOrderTraversal(Node root) { //中序遍历34 if (root.getLeftNode() != null) {35 theInOrderTraversal(root.getLeftNode());36 }37 printNode(root);38 if (root.getRightNode() != null) {39 theInOrderTraversal(root.getRightNode());40 }41 }42 43 44 public void thePostOrderTraversal(Node root) { //后序遍历45 if (root.getLeftNode() != null) {46 thePostOrderTraversal(root.getLeftNode());47 }48 if (root.getRightNode() != null) {49 thePostOrderTraversal(root.getRightNode());50 }51 printNode(root);52 }53 54 public static void main(String[] args) {55 BinaryTreeWithNode1 tree = new BinaryTreeWithNode1();56 Node root = tree.init();57 System.out.println("先序遍历");58 tree.theFirstTraversal(root);59 System.out.println("");60 System.out.println("中序遍历");61 tree.theInOrderTraversal(root);62 System.out.println("");63 System.out.println("后序遍历");64 tree.thePostOrderTraversal(root);65 System.out.println("");66 }67 68 }
堆栈方式，实现树的遍历：
1 import java.util.Stack; 2 3 4 public class BinaryTreeWithNode2 { 5 6 7 public Node init() { //注意必须逆序建立，先建立子节点，再逆序往上建立，因为非叶子结点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错 8 Node J = new Node(8, null, null); 9 Node H = new Node(4, null, null);10 Node G = new Node(2, null, null);11 Node F = new Node(7, null, J);12 Node E = new Node(5, H, null);13 Node D = new Node(1, null, G);14 Node C = new Node(9, F, null);15 Node B = new Node(3, D, E);16 Node A = new Node(6, B, C);17 return A; //返回根节点18 }19 20 public void printNode(Node node) {21 System.out.print(node.getData());22 }23 24 25 public void theFirstTraversal_Stack(Node root) { //先序遍历26 Stack stack = new Stack ();27 Node node = root;28 while (node != null || stack.size() > 0) { //将所有左孩子压栈29 if (node != null) { //压栈之前先访问30 printNode(node);31 stack.push(node);32 node = node.getLeftNode();33 } else {34 node = stack.pop();35 node = node.getRightNode();36 }37 }38 }39 40 public void theInOrderTraversal_Stack(Node root) { //中序遍历41 Stack stack = new Stack ();42 Node node = root;43 while (node != null || stack.size() > 0) {44 if (node != null) {45 stack.push(node); //直接压栈46 node = node.getLeftNode();47 } else {48 node = stack.pop(); //出栈并访问49 printNode(node);50 node = node.getRightNode();51 }52 }53 }54 55 public void thePostOrderTraversal_Stack(Node root) { //后序遍历56 Stack stack = new Stack ();57 Stack output = new Stack ();//构造一个中间栈来存储逆后序遍历的结果58 Node node = root;59 while (node != null || stack.size() > 0) {60 if (node != null) {61 output.push(node);62 stack.push(node);63 node = node.getRightNode();64 } else {65 node = stack.pop();66 node = node.getLeftNode();67 }68 }69 System.out.println(output.size());70 while (output.size() > 0) {71 72 printNode(output.pop());73 }74 }75 76 public static void main(String[] args) {77 BinaryTreeWithNode2 tree = new BinaryTreeWithNode2();78 Node root = tree.init();79 System.out.println("先序遍历");80 tree.theFirstTraversal_Stack(root);81 System.out.println("");82 System.out.println("中序遍历");83 tree.theInOrderTraversal_Stack(root);84 System.out.println("");85 System.out.println("后序遍历");86 tree.thePostOrderTraversal_Stack(root);87 System.out.println("");88 }89 90 91 }
原文出处：