终于抽出空了，又是一年一度的中秋节。💖明月伴你我，祝大家事事皆圆满。💖

那么今天为大家带来一篇JAVA数据结构的树，树在JAVA中的存在极其重要，也是面试中的高频点。一些树的基本名词，以及更为基础的理论，可在这一篇博客中查看数据结构及其拓展篇（二）。那么今天我给大家带来的是：

🌳二叉树🌳

🌲二叉查找树🌲

🌴红黑树🌴

二叉树

一、首先我们得知道什么是二叉树：

①即每个节点至多有两颗树，即每个节点的度不大于二

②二叉树的子树有左右之分，其顺序是不能颠倒的

二叉树作为一种重要的树形结构类型，在我们的实际应用中是有着极其重要的地位和广泛的意义的。总结一下，一颗二叉树的节点是一个有限的集合，且这颗二叉树要么为空，要么就是由一个度不大于二的根节点和两颗左子树和右子树且顺序不能颠倒的二叉树组成的。

二叉树的类型有很多种，那么作为基础的树，我们必须了解满二叉树和完全二叉树，如图。

满二叉树 ：如上图的完全二叉树，它的深度为 3，所以它的节点总数为 (2^k) -1 =7个节点。换言之，如果一棵树的深度为n,节点总数为(2^k) -1，那么它就是一棵满二叉树。

完全二叉树 ：如上图的完全二叉树，当且仅当其与深度为3，节点数为7的二叉树的节点一一对应时，我们称之为完全二叉树。完全二叉树是一种效率很高的数据结构，且满二叉树又是一种特别的完全二叉树。

趁热打铁，我们来说说二叉树的遍历运算是怎样的一种规则呢？如图。

由如上的遍历结果，我们来一一解析：

（根-左-右）前序：①既然叫根左右，那我们就从根开始，得到A。②然后是左，得到结果A B。同样根据根左右来计算。得到的结果就是A B D H E I。③然后是右。最终得到的结果是：A B D H E I C F G。

（左-根-右）中序：①同理，左根右先从左开始。得到二叉树的左子树的左，H D B。②再从左子树开始，得到二叉树的左子树的右，结果为 H D B I E。③然后是左根右的根，得到结果： H D B I E A。④最后是左根右的右。得到最终结果为：H D B I E A F C G。

（左-右-根）后序：①左右根，第一步取得左。结果为：H D。②第二步取得右，结果为 H D I E。③第三步取得根，结果为 H D I E B。④至此左子树取完了，接下来是右子树，结果为 H D I E B F G C。⑤左右子树都取完了，最后是根，结果为： H D I E B F G C A。

如上，是不是二叉树的遍历就一目了然了。如果有不懂的，欢迎大家的留言。

看完了二叉树的遍历，我们再来说说二叉树的存储结构，二叉树一般来说有两种存储结构：

一种是顺序存储，即用一组连续的存储单元从上至下，从左至右，存储完全二叉树上的节点元素。
一种是链式存储。二叉链表由数据域和左、右指针域构成，在含有n个结点的二叉链表中有n+1个空链域。三叉链表由数据域和左、右指针域及指向其双向亲（即父节点和子节点）的指针域。

那么在JAVA中我们如何手动去创建一个简单的树呢？如下图这棵树：

接下来我们来写代码实现这颗树：

一、首先创建实体集

/** * @author GanTieXia * @date 2021/9/21 19:04 */
public class TreeNode {
    // 数据
    int data;

    // 左字节点
    TreeNode leftChild;

    // 右子节点
    TreeNode rightChild;

    public TreeNode(int data) {
        this.data = data;
    }

    public TreeNode() {}
}

二、写实现方法

import java.util.ArrayList;
import java.util.List;

/** * @author GanTieXia * @date 2021/9/21 19:07 */
public class CreateTree {

    // 创建二叉树
    public static TreeNode creatTree(int[] value){
        // 新建以及集合方便做数据处理
        List<TreeNode> list = new ArrayList<>();

        for(int i=0;i < value.length;i++){
            TreeNode node = new TreeNode(value[i]);
            list.add(node);
        }

        // 新建一个对象
        TreeNode root;
        // 为了保证不报错下标越界异常,取i<list.size()/2的值运算
        for(int i=0;i < list.size()/2;i++){
            root = list.get(i);
            TreeNode left = list.get(i*2+1);
            root.leftChild = left;

            if(i*2+2 < list.size()){
                TreeNode right = list.get(i*2+2);
                root.rightChild = right;
            }
        }
        return list.get(0);
    }

    // 前序(根-左-右)遍历的方法
    public void preOrder(TreeNode root){
        if(root != null){
            System.out.println(root.data);
            preOrder(root.leftChild);
            preOrder(root.rightChild);
        }
    }

    public static void main(String[] args) {
        // 创建传入数组
        int[] value = new int[]{1,2,3,4,5};
        // 创建此类对象
        CreateTree createTree = new CreateTree();
        // 调用创建方法
        TreeNode root = createTree.creatTree(value);
        // 调用遍历输出方法
        createTree.preOrder(root);
    }
}

右键运行代码，我们擦好看一下输出：

如上，与图片中树的前序遍历结果相同，这就实现了二叉树的创建。

不知不觉已经晚上20：47了，明天还是工作日，计划中的二叉查找树和红黑树就下次再带给大家吧。