【概念解释】

树：本身是一种递归的数据结构。树由根节点，以及它的子节点，以及子节点的子节点组成的一种数据结构。没有子节点的子节点被称为叶子节点。
【说明】：
【节点】对于节点的名称：“节点”|“结点”
【节点的度】一个根节点有几个子节点
【树·概念解释】.jpg
如：EFCG都是叶子节点，A的度为3，B的度为2，D的度为1
【节点的关系】子节点是父节点的孩子节点，父节点是孩子节点的双亲节点。如图中A是B的双亲节点，BCD是A的孩子节点。
【兄弟节点】有相同父节点的节点为兄弟节点，如图中的BCD
【节点的层次】A在第一层，BCD在第二层，EFG在第三层
【树的深度】是最大层次，即为3

【二叉树】最多有两个分叉的树，即树的度数为2度的树

分类和比较

【满二叉树】：所有叶子节点都在同一层，所有的分支节点（非叶子节点）都有左右子树
【斜树】：所有的子节点都向一个方向倾斜，只分叉出左子树或右子树。
【完全二叉树】：对于高度/深度为 h 的二叉树而言，h-1层都是满的，h层节点都在左侧连续排列，空位都在右侧，就是完全二叉树
【注意】：斜树其实就是链表结构。二叉树如果只分出一个叉来就是链表，如果分出两个叉来就是二叉树，如果分出多个叉来就是一棵树。满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。
满二叉树 每一层的节点个数 2^(n-1)，n代表层数；
满二叉树 如果一个满二叉树的深度为h，那么该二叉树的节点总数为 2^n -1 个
【二叉树·满二叉树】.jpg
【完全二叉树】
【二叉树·完全二叉树】.jpg
将完全二叉树的节点进行编号，对于编号为k的节点：
它的父节点就是k/2；
如果有孩子节点，它的左节点为 2k，右节点为 2k +1；
【注意】
满二叉树的节点要么没孩子，要么一定是两个。
完全二叉树从根往下数，除了最下层外都是全满（都有两个子节点），而最下层所有叶节点都向左边靠拢填满，构造一棵完全二叉树就是从上到下，从左到右放置节点。
【二叉树·满二叉树&完全二叉树】.png

构造出一棵完全二叉树

【代码实现】

public class CreateTree {
                              //  0    1    2    3    4
                              //     2k+1  2k+2
    private static int[] array = {1,   2,  3,    4,   5};
    private static List<TreeNode> nodeList = new LinkedList<>();
    private static TreeNode createTree() {
        //构造节点
        for (int i = 0; i < array.length; i++) {
            TreeNode node = new TreeNode(array[i]);
            nodeList.add(node);
        }
        //构造节点之间的关系
        for (int i = 0; i < nodeList.size()/2; i++) {
            TreeNode node = nodeList.get(i);
            node.left = nodeList.get(i * 2 + 1);
             //最后一个父节点可能没有右孩子，需要额外判断
            if (i*2 +2 < nodeList.size()){
                node.right = nodeList.get(i * 2 + 2);
            }
        }
        return nodeList.get(0);
    }
}

【相关算法】

一、求取二叉树的深度：

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
【代码实现】

public class Depth {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);
        TreeNode leftNode = new TreeNode(9);
        TreeNode rightNode = new TreeNode(20);
        TreeNode subLeftNode = new TreeNode(15);
        TreeNode subRightNode = new TreeNode(7);
        rightNode.left = subLeftNode;
        rightNode.right = subRightNode;
        treeNode.left = leftNode;
        treeNode.right = rightNode;
        System.out.println(maxDepth(treeNode));
    }
             /*   3
                 / \
                9  20
                  /  \
                 15   7  */
    public static int maxDepth(TreeNode treeNode){
        if (treeNode == null){return 0;}
        int leftDepth = maxDepth(treeNode.left);
        int rightDepth = maxDepth(treeNode.right);
        return Math.max(leftDepth,rightDepth) + 1;
    }
}

二、相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
【二叉树·相同的树·图1】.jpg
输入：p = [1,2,3], q = [1,2,3]
输出：true
【二叉树·相同的树·图二】.jpg
输入：p = [1,2], q = [1,null,2]
输出：false
【二叉树·相同的树·图三】.jpg
输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/same-tree
【思路分析】
1）两棵树，如果有左右子树，那么树A的左子树 == 树B的左子树，同时树A的右子树 ==树B的右子树
2）如果两棵树都为空，那也是相同的。
3）如果一棵为空，另一棵不为空，是不同的。
4）如果结构相同，数值不相同，也是不同的。
【代码实现】

public class SameTree {

    public boolean isSameTree(TreeNode p,TreeNode q){

        if (null == p && null == q){
            return true;
        }
        if (null == p || null == q){
            return false;
        }
        if (p.val != q.val){
            return false;
        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

三、二叉树的遍历

3.1 递归遍历

遍历：对树种的每个节点都访问一次，且只访问一次。
深度优先遍历 DFS = Deep First Search
广度优先遍历 BFS = Breath First Search
先序遍历（前序遍历）：根节点 -> 左子树 -> 右子树 A -> B -> C 12457836
中须遍历：左子树 -> 根节点 -> 右子树 B -> A -> C 42758136
后序遍历：左子树 -> 右子树 -> 根节点 B -> C -> A 47852631

完全二叉树的遍历：

先序遍历：124895367
中序遍历：849251637
后序遍历：894526731
广序遍历：123456789

public static void main(String[] args) {
        TreeNode treeNode = CreateTree.create();
        System.out.println(treeNode);
        preOrder(treeNode);
        System.out.println();
        System.out.println("-------------");
        inOrder(treeNode);
        System.out.println();
        System.out.println("-------------");
        postOrder(treeNode);
    }
    //先序  中序 和 后序的遍历

    /**
     * 先序遍历 124895367
     * @param treeNode
     */
    public static void preOrder(TreeNode treeNode){

        if (treeNode == null) return;
        System.out.print(treeNode.val + " ");
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }

    /**
     * 中序遍历 849251637
     * @param treeNode
     */
    public static void inOrder(TreeNode treeNode){
        if ( null == treeNode) return;
        inOrder(treeNode.left);
        System.out.print(treeNode.val + " ");
        inOrder(treeNode.right);
    }
     /**
      * 后续遍历 894526731
      * @param treeNode 头节点
      */
    public static void postOrder(TreeNode treeNode){
        if (null == treeNode) return;
        postOrder(treeNode.left);
        postOrder(treeNode.right);
        System.out.print(treeNode.val + " ");
    }

     //广度优先遍历 123456789
     //通过队列实现 从根节点开始存储到队列中
     // 对队列元素的处理是 将队头节点的孩子存入队列中，取出队头节点
     // 直到队列为空 所有节点处理完成 同时节点的顺序是按照层级的

    public static void bfs(TreeNode node){
        if (node == null) return;
        LinkedList<TreeNode> queues = new LinkedList<>();
        queues.offer(node);

        while (queues.size() > 0){
            //取出队列首部元素
            TreeNode treeNode = queues.poll();
            System.out.print(treeNode.val);
            //如果
            if (treeNode.left != null){
                queues.offer(treeNode.left);
            }
            if (treeNode.right != null){
                queues.offer(treeNode.right);
            }
        }
    }

3.2 非递归遍历：迭代遍历

递归 —— 有去有回

先解决子问题再基于子问题解决当前问题解决当前问题
可以理解为是解决有依赖关系的多个问题
fib(3) A -> fib(2) B -> fib(1) C
调用关系：
开始处理A；
因为A依赖B，开始处理B；
因为B依赖C，开始处理C；
C处理完成 -> B处理完成 -> A处理完成

先进后出的处理关系 — 栈
实际上在Java内部，递归就是通过栈的方式进行遍历的

先递归整棵树的遍历根节点的遍历 - 左子树的遍历 - 右子树的遍历

3.2.1 先序遍历

先序遍历：124895367

【代码实现】

先序遍历入栈时打印


  /**
   * 使用栈 + 迭代的方式打印  先序遍历
   * @param node
   */
  public static void preOrderByLoop(TreeNode node){
      Stack<TreeNode> stack = new Stack<>();
      //使用指针，记录遍历到哪个节点
      TreeNode pointerNode = node;

      while (pointerNode != null || !stack.isEmpty()){
          //入栈，把当前能读到的所有左孩子 存入栈中
          while(pointerNode != null){
              System.out.print(pointerNode.val + " ");
              stack.push(pointerNode);
              pointerNode = pointerNode.left;
          }
          //出栈 弹出栈顶元素 并找到其右孩子
          /**
           * 1 2 4 8
           * 1 2 4
           * 1 2 9
           * 1 5
           * 3 6
           * 7
           * 打印出来 124895367
           */
          if (!stack.isEmpty()){
              pointerNode = stack.pop();
              pointerNode = pointerNode.right;
          }
      }
  }

3.2.2 中序遍历

中序遍历出栈时打印


  /**
   * 使用栈 + 迭代的方式打印  中序遍历
   * @param node
   */
  public static void inOrderByLoop(TreeNode node){
      Stack<TreeNode> stack = new Stack<>();
      //使用指针，记录遍历到哪个节点
      TreeNode pointerNode = node;

      while (pointerNode != null || !stack.isEmpty()){
          //入栈，把当前能读到的所有左孩子 存入栈中
          while(pointerNode != null){
           //   System.out.print(pointerNode.val + " ");
              stack.push(pointerNode);
              pointerNode = pointerNode.left;
          }
          //出栈 弹出栈顶元素 并找到其右孩子
          /**
           * 打印出来 
           */
          if (!stack.isEmpty()){
              pointerNode = stack.pop();
              System.out.print(pointerNode.val + " ");
              pointerNode = pointerNode.right;
          }
      }
  }

3.2.3 右序遍历

右序遍历时，根节点不从栈中弹出，要在右子树遍历后再弹出；
如何判断右子树被遍历完成？
通过记录上一次遍历的节点
如果上一次遍历的节点是当前节点的右子树，代表此根节点可以被遍历出来

入栈顺序 1 2 4 8 9 5 3 6 7
出栈顺序 8 9 4 5 2 6 7 3 1

节点的出栈逻辑有两种情况
1）当前节点是叶子节点
2）上一次出栈的节点是当前节点的右子树

数据结构与算法

二叉树结构及相关算法