树的概念

节点：根节点、父节点、子节点、兄弟节点

空树：一棵树可以没有任何节点
一棵树可以只有1个节点，也就是只有根节点
子树：左子树、右子树
节点的度（degree）：子树的个数
树的度：所有节点度中的最大值
叶子节点（leaf）：度为 0 的节点
非叶子节点：度不为 0 的节点
层数（level）：根节点在第1层，根节点的子节点在第2层，以此类推（有些教程也从第0层开始计算）
节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数
节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数
树的深度：所有节点深度中的最大值
树的高度：所有节点高度中的最大值
树的深度等于树的高度

有序树，无序树，森林

有序树

  • 树中任意节点的子节点之间有顺序关系

无序树

  • 树中任意节点的子节点之间没有顺序关系，也称为“自由树”

森林

  • 由m（m≥0）棵互不相交的树组成的集合**

    二叉树 - Binary Tree 是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。

    性质

  1. 非空二叉树第 i 层最多 2 个结点 （i >= 1）
  2. 深度为 k 的二叉树最多 2 - 1 个结点 （k >= 1）
  3. 在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2(有两个子节点)的结点多一个
  4. 具有n个节点的二叉树，其深度至少为log2n+1,其中，log2n表示取log2n的整数部分
  5. 对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n） 的结点
    1. 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋
    2. 若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i
    3. 若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1

      存储结构

      二叉树数据结构
      二叉树顺序存储图片
      树形结构 - 图1
      链式存储
      二叉树链式存储图片
      树形结构 - 图2

      分类

  • 满二叉树

  • 完全二叉树（堆）
    • 大顶堆：根 >= 左 && 根 >= 右
    • 小顶堆：根 <= 左 && 根 <= 右
  • 二叉查找树（二叉排序树）：左 < 根 < 右
  • 平衡二叉树 : 左子树树高 - 右子树树高 | <= 1
    • (AVL树)
    • 红黑树
    • SBT

  • 最小失衡树：平衡二叉树插入新结点导致失衡的子树：调整：

    • LL型：根的左孩子右旋
    • RR型：根的右孩子左旋
    • LR型：根的左孩子左旋，再右旋
    • RL型：右孩子的左子树，先右旋，再左旋

      真二叉树（Proper Binary Tree）

      概念：所有节点的度都要么为 0，要么为 2
      所有节点的度都要么为0，要么为2。
      树形结构 - 图3
      下图的树不是真二叉树，因为3号节点的度为1.
      树形结构 - 图4

      满二叉树（Full Binary Tree）

      所有节点的度要么为0，要么为2，且所有的叶子节点都在最后一层。
      树形结构 - 图5

  • 假设满二叉树的高度为树形结构 - 图6（树形结构 - 图7），那么

  1. 第树形结构 - 图8层的节点数量为：树形结构 - 图9
  2. 叶子节点数量为：树形结构 - 图10
  3. 总节点数量树形结构 - 图11，树形结构 - 图12，树形结构 - 图13，树形结构 - 图14的底为2.
  • 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多

  • 满二叉树一定是真二叉树，真二叉树不一定是满二叉树

    完全二叉树（Complete Binary Tree）

    概念：叶子节点只会出现最后 2 层，且最后 1 层的叶子结点都靠左对齐
    完全二叉树与满二叉树是很相似的，所以也可以这么定义，完全二叉树：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应
    树形结构 - 图15
    小结论：1、完全二叉树从根结点至倒数第2层是一棵满二叉树，2、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
    性质：

  • 度为 1 的节点只有左子树，度为1的节点要么是 1 个，要么是 0 个

  • 同样节点数量的二叉树，完全二叉树的高度最小（从上往下，从左往右满排布）
  • 假设完全二叉树的高度为h（h ≥ 1），那么有：
    • 至少有2h−12^{h−1}2h−1个节点， 202^020 + 212^121 + 222^222 + … + 2h−22^{h-2}2h−2 + 1
    • 最多有2h−12^h−12h−1个节点( 满二叉树 )， 202^020 + 212^121 + 222^222 + … + 2h−12^{h-1}2h−1
  • 假设总节点数量为 n
    • 2h−12^{h−1}2h−1 <= 2h2^h2h
    • h−1h-1h−1 <= log⁡2n\log_2nlog2n < hhh
    • hhh = foor (log⁡2n)+1(\log_2n) + 1(log2n)+1
    • floor是向下取整，另外，ceiling是向上取整
  • 树形结构 - 图16

  • 树形结构 - 图17

    平衡二叉树（AVL树）

    性质

  • | 左子树树高 - 右子树树高 | <= 1

  • 平衡二叉树必定是二叉搜索树，反之则不一定
  • 最小二叉平衡树的节点的公式：F(n)=F(n-1)+F(n-2)+1 （1 是根节点，F(n-1) 是左子树的节点数量，F(n-2) 是右子树的节点数量）

平衡二叉树图片
树形结构 - 图18

最小失衡树

平衡二叉树插入新结点导致失衡的子树
调整：

  • LL 型：根的左孩子右旋
  • RR 型：根的右孩子左旋
  • LR 型：根的左孩子左旋，再右旋
  • RL 型：右孩子的左子树，先右旋，再左旋

遍历

  • 前序遍历: 首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树
  • 中序遍历: 首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树

  • 后序遍历: 首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点

  • 深度优先搜索: 顾名思义，查找时深度优先，从根结点访问最远的结点直到找到所有节点。前序，中序和后序遍历都是深度优先遍历的特例,可以借助栈实现,也可以递归实现

  • 广度优先搜索: 广度优先遍历会先访问离根节点最近的节点，二叉树的广度优先遍历又称按层次遍历。算法借助队列实现

  • https://blog.csdn.net/Monster_ii/article/details/82115772 非递归遍历图解

    1.   public void preorder() {
    2.       if (root == null) {
    3.           return;
    4.       }
    6.       Stack<Node<E>> stack = new Stack<>();
    7.       stack.push(root);
    9.       while (!stack.isEmpty()) {
    10.           Node<E> node = stack.pop();
    11.           System.out.print(node.element + "  ");
    12.           if (node.right != null) {
    13.               stack.push(node.right);
    14.           }
    15.           if (node.left != null) {
    16.               stack.push(node.left);
    17.           }
    18.       }
    19.   }
    21.   public void inorder() {
    22.       if (root == null) {
    23.           return;
    24.       }
    25.       Stack<Node<E>> stack = new Stack<>();
    26.       Node<E> node = root;
    28.       while (node != null || !stack.isEmpty()) {
    29.           while (node != null) {
    30.               stack.push(node);
    31.               node = node.left;
    32.           }
    33.           node = stack.pop();
    34.           System.out.print(node.element + "  ");
    35.           node = node.right;
    36.       }
    37.   }
    39.   public void postorder() {
    40.       Node<E> node = this.root;
    41.       Stack<Node<E>> stack = new Stack<>();
    43.       Node<E> lastVisited = null;
    45.       while (node != null || !stack.isEmpty()) {
    46.           while (node != null) {
    47.               stack.push(node);
    48.               node = node.left;
    49.           }
    51.           node = stack.pop();
    52.           if (node.right == null || node.right == lastVisited) {
    53.               System.out.print(node.element + "  ");
    54.               lastVisited = node;
    55.               node = null;
    56.           }else {
    57.               stack.push(node);
    58.               node = node.right;
    59.           }
    61.       }        
    62.   }
    64.   //广度优先遍历
    65.    private static void bfs(BinaryTree.Node tn) {
    66.       if (tn == null) {
    67.           return;
    68.       }
    70.       Queue<BinaryTree.Node> queue = new LinkedList<>();
    71.       queue.offer(tn);
    73.       int ans = 0;
    74.       while (!queue.isEmpty()) {
    75.           BinaryTree.Node treeNode = queue.poll();
    76.           System.out.print(treeNode.data + "\t");
    78.           if (treeNode.leftNode != null) {
    79.               queue.offer(treeNode.leftNode);
    80.           }
    82.           if (treeNode.rightNode != null) {
    83.               queue.offer(treeNode.rightNode);
    84.           }
    85.       }       
    87.   }

    树的判定

    完全二叉树的判定
    实现步骤：
    树形结构 - 图19

    1. /**
    2. * 判断是否为完全二叉树 —— (层序遍历)
    3. * @return
    4. */
    5. public boolean isComplete() {
    6.   if (root == null) return false;
    7.   Queue<Node<E>> queue = new LinkedList<>();
    8.   queue.offer(root);
    9.   boolean leaf = false;
    10.   while (!queue.isEmpty()) {
    11.       Node<E> node = queue.poll();
    12.       if (leaf && !node.isLeaf()) return false;
    13.       if (node.left != null) {
    14.           queue.offer(node.left);
    15.       } else if (node.right != null) {
    16.           //相当于node.left == null && node.right != null
    17.           return false;
    18.       }
    19.       if (node.right != null) {
    20.           queue.offer(node.right);
    21.       } else {
    22.           //node.left == null && node.right == null
    23.           //node.left ！= null && node.right == null
    24.           // 后面遍历的节点都必须是叶子节点
    25.           leaf = true;
    26.       }
    27.   }
    28.   return true;
    29. }

    真二叉树的判定

    实现步骤：
    1、利用队列先进先出的特性
    2、利用真二叉树的节点，要么度为0，要么度为2的特点
    3、在层序遍历的时候，判断每层的节点数量，如果levelSize % 2 != 0，返回flase
    4、结合上面层序遍历的图解，就会发现，每一层的节点遍历完后，队列中的节点数量size等于下一层的节点数量，而第一层只有根节点 ``` /**

    • 判断是否为真二叉树 —— (层序遍历)
    • @return */ public boolean isProper (){ if (root == null) return false; // 存储着每一层的元素数量 int levelSize = 1; Queue> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) {
      1. Node<E> node = queue.poll();
      2. levelSize--;
      3. if (node.left != null) {
      4.     queue.offer(node.left);
      5. }
      6. if (node.right != null) {
      7.     queue.offer(node.right);
      8. }
      9. // 意味着即将要访问下一层
      10. if (levelSize == 0) {
      11.     //每一层访问完后，下一层的节点个数是队列的size
      12.     levelSize = queue.size();
      13.     if (levelSize % 2 != 0) return false;
      14. }
      } return true; }
  1. <a name="BMf8p"></a>
  2. ## 树的高度
  3. 树的高度实际上就是树的层数，与上面的判定真二叉树很接近，只需要在设置一个`height`，在遍历完每一层的时候，`height++`,结束遍历后，返回的就是树的高度<br />树的高度实际上所有子节点的高度中最大的一个，然后再 + 1，这样的思路，很容易以递归的方式实现，所以计算树的高度，有递归和迭代两种方法，这里贴出递归的方法，因为迭代的方法就是上面判定二叉树的方法做点小改动，就不贴出来了，需要的话，自行下载源码。

/**

  • 计算树的高度
  • @return / public int height(){ //递归法 return heightByRecursive(root); //迭代法 //return heightByIteration(); } /*
  • (递归法)获取传入节点的高度
  • @param node
  • @return */ private int heightByRecursive(Node node){ if (node == null) return 0; return 1 + Math.max(heightByRecursive(node.left),heightByRecursive(node.right)); }
  1. <a name="fRRrD"></a>
  2. ## 前驱与后继
  3. <a name="Xd4xt"></a>
  4. ### 寻找前驱节点
  5. ![](https://cdn.nlark.com/yuque/0/2021/png/2387751/1616132734621-7416f6f9-4e6a-46dc-8e04-b1cbe340362f.png#align=left&display=inline&height=547&margin=%5Bobject%20Object%5D&originHeight=547&originWidth=1158&size=0&status=done&style=none&width=1158)<br />根据上面的判定条件给出实现代码：

/**

  • 获取传入节点的前驱节点
  • @param node
  • @return */ protected Node predecessor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（left.right.right.right….） Node p = node.left; if (p != null) {
    1.  while (p.right != null) {
    2.      p = p.right;
    3.  }
    4.  return p;
    } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.left) {
    1.  node = node.parent;
    } // node.parent == null // node == node.parent.right return node.parent; }
  1. <a name="8qe70"></a>
  2. ### 寻找后继节点
  3. ![](https://cdn.nlark.com/yuque/0/2021/png/2387751/1616132743449-f4073878-092d-4a3a-95a8-aa540756c853.png#align=left&display=inline&height=536&margin=%5Bobject%20Object%5D&originHeight=536&originWidth=1222&size=0&status=done&style=none&width=1222)<br />根据上面的判定条件给出实现代码：
  1. /**
  2.  * 获取传入节点的后继节点
  3.  *
  4.  * @param node
  5.  * @return
  6.  */
  7. protected Node<E> successor(Node<E> node) {
  8.     if (node == null) {
  9.         return null;
  10.     }
  11.     // 后继节点在右子树当中（right.left.left.left....）
  12.     Node<E> p = node.right;
  13.     if (p != null) {
  14.         while (p.left != null) {
  15.             p = p.left;
  16.         }
  17.         return p;
  18.     }
  19.     // 从父节点、祖父节点中寻找后继节点
  20.     while (node.parent != null && node == node.parent.right) {
  21.         node = node.parent;
  22.     }
  23.     return node.parent;
  24. }

`` 找出前驱或者后继节点有什么用，不知道你有没有看到方法的访问修饰符：protected，实际上着两个方法都不是给用户调用的，正如我们的疑惑一样，用户不知道怎么用，用来干嘛，实际上这是为继承二叉树BinaryTree`类的子类所使用的，其作用是在删除度为 2 的时，将找到的前驱或者后继节点用来替代的