将一个数组变成二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作 “左子树” 和 “右子树”。 比如数组：

int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9} 变为二叉树为：

分析： 1、首先要定义每一个结点，每一个结点包括自身值，左结点和右结点，实现get、set方法。

public class Node {public int data;      //自己本身值public Node left;     //左结点public Node right;     //右结点public Node() {}public Node(int data, Node left, Node right) {this.data = data;this.left = left;this.right = right;}public int getData() {return data;}public void setData(int data) {this.data = data;}public Node getLeft() {return left;}public void setLeft(Node left) {this.left = left;}public Node getRight() {return right;}public void setRight(Node right) {this.right = right;}
}

2、创建二叉树

public class Demo2 {public static List list = new ArrayList();      //用一个集合来存放每一个Nodepublic void createTree(int[] array) {for (int i = 0; i < array.length; i++) {Node node = new Node(array[i], null, null);    //创建结点，每一个结点的左结点和右结点为nulllist.add(node); // list中存着每一个结点}// 构建二叉树if (list.size() > 0) {for (int i = 0; i < array.length / 2 - 1; i++) {       // i表示的是根节点的索引，从0开始if (list.get(2 * i + 1) != null) { // 左结点list.get(i).left = list.get(2 * i + 1);}if (list.get(2 * i + 2) != null) {// 右结点list.get(i).right = list.get(2 * i + 2);}}// 判断最后一个根结点：因为最后一个根结点可能没有右结点，所以单独拿出来处理int lastIndex = array.length / 2 - 1;// 左结点list.get(lastIndex).left = list.get(lastIndex * 2 + 1);// 右结点，如果数组的长度为奇数才有右结点if (array.length % 2 == 1) {list.get(lastIndex).right = list.get(lastIndex * 2 + 2);}}
}// 遍历，先序遍历
public static void print(Node node) {if (node != null) {System.out.print(node.data + " ");print(node.left);print(node.right);}
}public static void main(String[] args) {int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };Demo2 demo = new Demo2();demo.createTree(array);print(list.get(0));}
}

结果为： 1 2 4 8 9 5 3 6 7