二叉树简介(Binary Tree)

二叉树种类：满二叉树、完全二叉树

1、满二叉树

一棵二叉树只有0/2的节点，并且0的节点在同一层，被称为满二叉树。深度为k，有2^k-1个节点的二叉树。

2、完全二叉树

完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

是完全二叉树

是完全二叉树

不是完全二叉树

3、二叉搜索树

二叉搜索树是一个有数值的有序树，有以下特征：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 左右子树也分为为二叉排序

4、平衡二叉搜索树

平衡二叉搜索树，由称为AVL树，具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

是平衡二叉搜索树

不是平衡二叉搜索树

5、二叉树的存储方式

可以链式存储(链表)，也可以顺序存储(数组)，一般用链式存储比较多
TreeNode结构如下

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.vale = val;
        this.left = null;
        this.right = null;
    }
}

6、二叉树的遍历方式

深度优先搜索、广度优先搜索

深度优先搜索(递归法、迭代法)

• 前序(Pre-order)： 中/左/右
• 中序(In-order)： 左/中/右
• 后序(Post-order)： 左/右/中

广度优先搜索：

• 层序遍历(迭代法)