根据数组创建二叉树，并对二叉树进行先序、中序和后序遍历。
代码实现：
import java.util.LinkedList; import java.util.List; public class BinaryTree { private static List<Node> nodeList=null; /** * <p>MethodName:main </p> * <p>Description: 二叉树的构建及遍历：先序、中序和后序</p> * <p>@param args</p> * <p>Return:void </p> * @author Sunny * @date 2016-9-27下午7:50:53 */ public static void main(String[] args) { int[] arr={7,6,4,9,0,5,2,8,3,1}; createBinaryTree(arr); Node root=nodeList.get(0); System.out.println("前序遍历："); preOrder(root); System.out.println(); System.out.println("中序遍历："); inOrder(root); System.out.println(); System.out.println("后序遍历："); postOrder(root); System.out.println(); } //根据数组构造二叉树 public static void createBinaryTree(int[] arr){ nodeList=new LinkedList<Node>(); for(int nodeIndex=0;nodeIndex<arr.length;nodeIndex++){ nodeList.add(new Node(arr[nodeIndex])); } for(int parentIndex=0;parentIndex<arr.length/2-1;parentIndex++){ Node parent=nodeList.get(parentIndex); //左孩子 Node left=nodeList.get(parentIndex*2+1); parent.setLeftChild(left); //右孩子 Node right=nodeList.get(parentIndex*2+2); parent.setRightChild(right); } //该父节点可能没有右孩子，故单独处理 int index=arr.length/2-1; nodeList.get(index).setLeftChild(nodeList.get(index*2+1)); if(arr.length%2==1){ nodeList.get(index).setRightChild(nodeList.get(index*2+2)); } } //前序遍历 public static void preOrder(Node node){ if(node==null){ return; } System.out.print(node.getData()+" "); preOrder(node.getLeftChild()); preOrder(node.getRightChild()); } //中序遍历 public static void inOrder(Node node){ if(node==null){ return; } inOrder(node.getLeftChild()); System.out.print(node.getData()+" "); inOrder(node.getRightChild()); } //后序遍历 public static void postOrder(Node node){ if(node==null){ return; } postOrder(node.getLeftChild()); postOrder(node.getRightChild()); System.out.print(node.getData()+" "); } } /** * * <p>Title:Node </p> * <p>Description:构造节点类 </p> * <p>Company: </p> * @author Sunny * @date 2016-9-27下午8:33:17 */ class Node{ private int data; private Node leftChild; private Node rightChild; public Node(int data){ this.data=data; leftChild=null; rightChild=null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } }
结果：
前序遍历： 7 6 9 8 3 0 1 4 5 2 中序遍历： 8 9 3 6 1 0 7 5 4 2 后序遍历： 8 3 9 1 0 6 5 2 4 7
