二叉树--天然的查找语义（1）基础篇

1.树结构可以高效的进行查找和搜索。（系统文件，就是一个树形结构。根据文件夹去查找特定文件，时间复杂度实际上就是文件数的深度logN）

生活中的树形结构：图书馆系统、大企业的管理层

将数据使用树形结构来存储后，再次进行检索或查找，效率比线性结构高的多。

2.常用树结构：

BST二分搜索树--二叉树的元素查找

平衡二叉搜索树-- AVL（严格平衡），红黑树（非严格平衡）

看到logN联想到树结构

3.树：子树不能相交。

除了根节点，每个节点有且仅有一个父节点

一颗N个节点的树有N-1条边

节点的度：该节点含有的子树的个数就称为结点的度

树的度：树中最大的节点的度数

叶子结点（终端节点）：度为0的结点

树的层次：从根开始计算

二叉树：每个节点最多只有两颗子树，二叉树中结点的度不超过2，两棵子树有左右之分。

满二叉树：所有的非叶子结点的度都是2。 

对于一颗二叉树，高度为k,则该二叉树最多有2的k次方-1个结点（最多的情况就是满二叉树）。

层次为k，第k层最多有2的k-1次方个结点。

边长 = 结点的个数n-1

设度为0的结点个数是n0，度为1的结点个数为n1,度为2的结点个数为n2，

则n0 = n2 +1

n0 + n1+ n2 = n

---

完全二叉树：满二叉树缺了右下角

完全二叉树的结点编号和满二叉树一一对应。每一层结点都尽量达到最大值，若某一层结点没有达到最大值，该层的结点都考左排列。

完全二叉树中，不存在只有右子树没有左子树的结点（结点要靠左排列）。

二叉树的存储方式：

和链表一样，顺序存储和链式存储（引用）

顺序存储，将二叉树采用数组方式存储（只能存储完全二叉树）

普通二叉树采用引用方式存储。

二叉树的遍历：前序、中序、后序、层次

在写三种遍历方式时，借助栈这个结构，保证做到不重不漏。

//先序遍历:根左右
    //传入一颗二叉树的根节点。就可以按照先序遍历的方式来输出节点值
    public static void preOrder(TreeNode root){
        //边界条件
        if(root == null){
            return ;
        }
        System.out.println(root.val + " ");
        //按照先序遍历的方式递归访问左子树
        preOrder(root.left);
        //按照先序遍历的方式来访问右树
        preOrder(root.right);
    }

  //中序遍历：左中右
    //传入一颗二叉树的根节点，就能按照中序遍历的方式来输出结果集
    public static void inOrder(TreeNode root){
        if(root == null){
            return ;
        }
        inOrder(root.left);
        System.out.println(root.val + " ");
        inOrder(root.right);
    }

层序遍历属于非递归的迭代法，以下是代码实现：

public class Num102_LevleOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        //借助队列来实现遍历过程
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //不为空时继续遍历
            //使用一个temp数组来保存当前层数的元素
            List<Integer> curList = new ArrayList<>();
            //取出当前层的所有元素添加进curList中
            int size = queue.size();
            for (int i = 0; i <size; i++) {
                TreeNode cur = queue.poll();
                curList.add(cur.val);
                if(cur.left!= null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            //当前层元素被遍历完了
            ret.add(curList);
        }
        return ret;
    }
}