java 二叉树的创建 遍历

本来说复习一下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 左右都有

 

 遍历

　　先序遍历：根左右

　　中序遍历：左根右

　　后序遍历：左右根

　　

　　有一个很简单的记忆方法，先中后代表根的位置，左右相对位置永远不变

　　在程序里采用递归的方式进行实现

 1 package tree;
 2 
 3 import java.util.linkedlist;
 4 import java.util.list;
 5 
 6 public class tree {
 7     
 8     private static class node{
 9         node left;
10         node right;
11         int val;
12         
13         node(int data){
14             left = null;
15             right = null;
16             val = data;
17         }
18     }
19     
20     //生成一颗二叉树
21     public static list<node> creattree(int[] array){
22         
23         list<node> nodelist = new linkedlist<>();
24         //每个位置转换成节点
25         for(int i = 0; i<array.length; i++){
26             nodelist.add(new node(array[i]));
27         }
28         //按照关系建立二叉树
29         for(int i=0; i<array.length/2-1; i++){
30             //左孩子
31             nodelist.get(i).left = nodelist.get(i*2+1);
32             //右孩子
33             nodelist.get(i).right = nodelist.get(i*2+2);
34         }
35         //最后一个节点特殊处理
36         int index = array.length / 2 - 1;
37         //左孩子
38         nodelist.get(index).left = nodelist.get(index*2+1);
39         //如果长度是奇数，那就有右孩子
40         if(array.length%2 == 1){
41             nodelist.get(index).right = nodelist.get(index*2+2);
42         }
43         
44         return nodelist;
45     }
46     
47     //先序遍历（根、左、右）
48     public static void preordertraverse(node node){
49         if(node == null) return;
50         //根
51         system.out.print(node.val + " ");
52         //左
53         preordertraverse(node.left);
54         //右
55         preordertraverse(node.right);
56     }
57     
58     //中序遍历
59     public static void inordertraverse(node node){
60         if(node == null) return;
61         //左
62         inordertraverse(node.left);
63         //根
64         system.out.print(node.val + " ");
65         //右
66         inordertraverse(node.right);
67     }
68     
69     //后序遍历
70     public static void postordertraverse(node node){
71         if(node == null) return;
72         //左
73         postordertraverse(node.left);
74         //右
75         postordertraverse(node.right);
76         //根
77         system.out.print(node.val + " ");
78     }
79     
80     
81     public static void main(string[] args) {
82         int[] array = { 1, 2, 3, 4, 5, 6, 7, 8 };
83         //获取根节点
84         node root = tree.creattree(array).get(0);
85         
86         system.out.println("先序遍历：");  
87         preordertraverse(root);  
88         system.out.println();
89         
90         system.out.println("中序遍历：");  
91         inordertraverse(root);  
92         system.out.println(); 
93         
94         system.out.println("后序遍历：");  
95         postordertraverse(root);  
96         system.out.println(); 
97     }
98     
99 }

运行结果：