本来说复习一下BFS和DFS，辗转就来到了二叉树...本文包括二叉树的创建和遍历
概念
数据：1 2 3 4 5 6 7生成一颗二叉树
上面的数是数据，不是位置，要区别一下数据和位置
红色的代表位置，黑色的代表数据，数据是通过数组给的
看红色的标记，每一个父节点的左儿子是 当前值*2+1 右儿子是 当前值*2+2，我们是从0开始编号的，如果是-1开始编号，则为x*2 、x*2+1
有了上面这个公式就会变得很简单，既然要生成一颗数，那么每个节点是必不可少的，就要定义一个节点类，里面包含当前值，左右儿子，左右儿子一个个往下指，就形成了 一棵树
在生成二叉树的时候，考虑到最后一个节点，上图数组的长度是8，此时没有右节点，如果为9，就有右节点
得到结果：length%2 == 0 只有左节点 length%2 == 1 左右都有
遍历
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
有一个很简单的记忆方法，先中后代表根的位置，左右相对位置永远不变
在程序里采用递归的方式进行实现
package tree; import java.util.LinkedList;
import java.util.List; public class Tree { private static class Node{
Node left;
Node right;
int val; Node(int data){
left = null;
right = null;
val = data;
}
} //生成一颗二叉树
public static List<Node> CreatTree(int[] array){ List<Node> nodelist = new LinkedList<>();
//每个位置转换成节点
for(int i = 0; i<array.length; i++){
nodelist.add(new Node(array[i]));
}
//按照关系建立二叉树
for(int i=0; i<array.length/2-1; i++){
//左孩子
nodelist.get(i).left = nodelist.get(i*2+1);
//右孩子
nodelist.get(i).right = nodelist.get(i*2+2);
}
//最后一个节点特殊处理
int index = array.length / 2 - 1;
//左孩子
nodelist.get(index).left = nodelist.get(index*2+1);
//如果长度是奇数，那就有右孩子
if(array.length%2 == 1){
nodelist.get(index).right = nodelist.get(index*2+2);
} return nodelist;
} //先序遍历（根、左、右）
public static void preOrderTraverse(Node node){
if(node == null) return;
//根
System.out.print(node.val + " ");
//左
preOrderTraverse(node.left);
//右
preOrderTraverse(node.right);
} //中序遍历
public static void inOrderTraverse(Node node){
if(node == null) return;
//左
inOrderTraverse(node.left);
//根
System.out.print(node.val + " ");
//右
inOrderTraverse(node.right);
} //后序遍历
public static void postOrderTraverse(Node node){
if(node == null) return;
//左
postOrderTraverse(node.left);
//右
postOrderTraverse(node.right);
//根
System.out.print(node.val + " ");
} public static void main(String[] args) {
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8 };
//获取根节点
Node root = Tree.CreatTree(array).get(0); System.out.println("先序遍历：");
preOrderTraverse(root);
System.out.println(); System.out.println("中序遍历：");
inOrderTraverse(root);
System.out.println(); System.out.println("后序遍历：");
postOrderTraverse(root);
System.out.println();
} }
运行结果：