一、树的概念

有很多数据的逻辑关系并不是线性关系，在实际场景中，常常存在着一对多，甚至是多对多的情况，它是由n(n≥0)个有限节点组成一个具有层次关系的集合

树的分类如下:

二、二叉树

二叉树(binary tree)是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节 点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。

二叉树节点的两个孩子节点，一个被称为左孩子(left child)，一个被称为右孩子(right child)。这 两个孩子节点的顺序是固定的，左孩子小于右孩子。

满二叉树

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就
是满二叉树

完全二叉树

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树

满二叉树要求所有分支都是满的;而完全二叉树只需保证最后一个节点之前的节点都齐全即可

二叉树的存储

二叉树属于逻辑结构，可以使用链表和数组进行存储。

链式存储

• 二叉树的每一个节点包含3部分
  • 存储数据的data变量
  • 指向左孩子的left指针
  • 指向右孩子的right指针

数组存储

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来

寻址方式:

一个父节点的下标是n，那么它的左孩子节点下标就是2×n+1、右孩子节点下标就是2*(n+1) 对于一个稀疏的二叉树(孩子不满)来说，用数组表示法是非常浪费空间的 所以二叉树一般用链表存储实现。(二叉堆除外)

二叉查找树

二叉查找树(binary search tree)，二叉查找树在二叉树的基础上增加了以下几个条件

如果左子树不为空，则左子树上所有节点的值均小于根节点的值

如果右子树不为空，则右子树上所有节点的值均大于根节点的值

左、右子树也都是二叉查找树

二叉查找树要》 求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性。因此二叉查找树还有另一个名字——二叉排序树(binary sort tree)

三、二叉树的遍历

二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的
方式来遍历，遍历出的序列顺序也不同

3.1 深度优先遍历

所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式

前序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树

中序遍历

二叉树的中序遍历，输出顺序是左子树、根节点、右子树

后序遍历

二叉树的后序遍历，输出顺序是左子树、右子树、根节点

四、代码实现

public class TreeNode {

    public int data; // 数据节点

    public TreeNode leftChild; // 左孩子
    public TreeNode rightChild; // 右孩子


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



/**
 * 二叉查找树
 */
public class BinarySearchTreeNode {


    private TreeNode root; // 根节点

    public void insertNode(int data) {
        root = insertNode(root, data);
    }


    /**
     *
     * @param node 当前数的根节点
     * @param data
     */
    public TreeNode insertNode(TreeNode node, int data) {
        if (null == node) {
            return new TreeNode(data);
        }


        if (data < node.data) {
            node.leftChild = insertNode(node.leftChild, data);
        } else if (data > node.data) {
            node.rightChild = insertNode(node.rightChild, data);
        } else{
            node.data = data;
        }
        return node;
    }


    /**
     * 前序遍历 根 左 右
     * @param node
     */
    public static void preorderTraversal(TreeNode node) {
        // 终止条件
        if (null == node) {
            return;
        }
        System.out.println(node.data);
        preorderTraversal(node.leftChild);
        preorderTraversal(node.rightChild);
    }


    /**
     * 中序遍历 左 根 右
     * @param node
     */
    public static void inorderTraversal(TreeNode node) {
        // 终止条件
        if (null == node) {
            return;
        }

        inorderTraversal(node.leftChild);
        System.out.println(node.data);
        inorderTraversal(node.rightChild);
    }

    /**
     * 前序遍历 左 根 右
     * @param node
     */
    public static void postorderTraversal(TreeNode node) {
        // 终止条件
        if (null == node) {
            return;
        }
        postorderTraversal(node.leftChild);
        postorderTraversal(node.rightChild);
        System.out.println(node.data);
    }

    /**
     *                 ┌───┐
     *                 │ 10│
     *           ┌─────┴───┴───┐
     *           │             │
     *         ┌─┴─┐          ┌┴───┐
     *         │  8│          │  11│
     *      ┌──┴───┴──┐       └────┴────┐
     *      │         │                 │
     *   ┌──┴┐      ┌─┴─┐             ┌─┴──┐
     *   │ 7 │      │ 9 │             │12  │
     *   └───┘      └───┘             └────┘
     * @param args
     */

    public static void main(String[] args) {
        // 构建一个二叉查找树
        BinarySearchTreeNode btt= new BinarySearchTreeNode();
        btt.insertNode(10);
        btt.insertNode(8);
        btt.insertNode(11);
        btt.insertNode(7);
        btt.insertNode(9);
        btt.insertNode(12);

        // 前序遍历
        preorderTraversal(btt.root);
        System.out.println("---------------------------");
        inorderTraversal(btt.root);
        System.out.println("---------------------------");
        postorderTraversal(btt.root);

    }



}