算法与数据结构

树

特点：

• 每个节点有一个或者多个子节点
• 没有父节点的节点称为根节点
• 每一个非根节点只有一个父节点
• 每一个节点及其后代节点整体上可以看成一棵树，称为当前节点的父节点的一个子树

相关术语

• 节点的度：一个节点含有子树的个数
• 叶节点：度为0的节点称为叶节点
• 分支节点：度不为0的节点
• 节点的层次：从根节点开始，根节点的层次为1，根的直接后继层次为2，以此类推
• 树的度：树中所有节点的度的最大值（一个节点含有子树的个数）
• 树的高度：书中节点的最大层次
• 孩子节点：一个节点的直接后继节点称为该节点的孩子节点
• 父节点：一个节点的直接前驱称为该节点的父节点
• 兄弟节点：同一父节点的孩子节点成为兄弟节点

二叉树相关概念

• 概念：度不超过2的树
• 真二叉树：所有节点的度要么为0，要么为2
• 满二叉树：所有节点的度要么为0，要么为2，并且所有的叶子节点都在最后一层
• 完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树，这种树可以理解为是从左往右放置节点
  • 度为1的节点只有左子树
  • 度为1的节点要么是1个，要么是0个
  • 同样节点数量的二叉树，完全二叉树的高度最小

二叉查找树

插入的思想：

• 如果当前树中没有任何一个节点，则直接把新节点当做根节点

• 如果当前树不为空，则从根节点开始：

  • 如果新节点的key小于当前节点的key，则继续找当前节点的左子节点
  • 如果新节点的key大于当前节点的key，则继续找当前节点的右子节点
  • 如果新节点的key等于当前节点的key，则树中已经存在这样的节点，直接替换value值

查找思想：

从根节点开始：

• 如果要查询的key小于当前节点的key，则继续找当前节点的左子节点
• 如果要查询的key大于当前节点的key，则继续找当前节点的右子节点
• 如果要查询的key等于当前节点的key，则树中返回当前节点的value

二叉树遍历

• 前序遍历：根节点，前序遍历左子树，前序遍历右子树

二叉树前序遍历.png

• 中序遍历：中序遍历左子树，根节点，中序遍历右子树，遍历的结果是升序或者降序的

二叉树中序遍历.png

• 后序遍历：后序遍历左子树，中序遍历右子树，根节点

二叉树后序遍历.png

• 层序遍历：从上到下，从左到右依次访问每个节点
  • 将根节点入队列
  • 循环执行以下操作，直到队列为空
    • 将队头节点A出队，进行访问
    • 将A的左子节点入队，将A的有子节点入队

二叉树层序遍历.png

二叉树高度

• 递归的方式

二叉树高度.png

• 循环遍历的方式

public static int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int preCount = 1;
    int pCount = 0;

    int level = 0;

    while (!q.isEmpty()) {
        TreeNode temp = q.poll();
        preCount--;

        if (temp.left != null) {
            q.offer(temp.left);
            pCount++;
        }
        if (temp.right != null) {
            q.offer(temp.right);
            pCount++;
        }

        if (preCount == 0) {
            preCount = pCount;
            pCount = 0;
            // System.out.println();
            level++;
        }
    }
    return level;
}

完全二叉树判断

完全二叉树判断.png

翻转二叉树

翻转二叉树1.png 翻转二叉树2.png

前驱节点

获取方式：

前驱节点.png

代码实现逻辑

前驱节点代码实现.png

后继节点

后继节点.png

代码实现

后继节点代码实现.png

平衡树

红黑树

B 树

堆

特性：

• 是一个完全二叉树

• 他通常用数组来实现，具体做法：将二叉树的节点按照层级顺序放入数组中，根节点在位置1，其他节点在位置2和3，而子节点的子节点则分别在4,5,6,7，这样，一个节点的位置为k，则它的父节点的位置为k/2，则它的两个子节点的位置为2k和2k+1

• 每个节点都大于等于它的两个子节点，这两个子节点的顺序是不固定的

新增元素

• 先往数组的最后一个元素赋值
• 通过上浮操作，对堆重新排序
• 上浮操作：如果往堆中新插入元素，我们只需要不断的比较新节点的a[k]和它的父节点a[k/2]的大小，然后根据结果完成数据元素的交换

删除最大元素：

• 交换索引1处的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根节点
• 将最打索引处的元素删除
• 通过下沉调整对，让堆重新有序
• 下沉操作：通过循环，不断的对比当前节点k和其 左子节点2k和右子节点2k+1处中的较大值 的元素大小，如果当前节点比刚刚比对出来的那个节点 小，则需要交换位置

堆排序

• 堆的创建：

  • 给定一个数组，然后哦转换为堆
  • 重新创建一个数组，然后从左往右遍历原数组，每得到一个元素后，添加到新数组中，并通过上浮，对堆进行调整，最后的新数组就是一个堆
  • 创建一个新数组，把原数组0-length-1拷贝到新数组的 1-length处，在从新数组的一半（根据堆的特性，从数组的一半处开始，往后都是子节点）开始往1索引处扫描（从右往左），然后对扫描后的元素最下层调整

• 堆按照从小到大排序

  1. 构造堆
  2. 得到堆顶元素，这个值就是最大值
  3. 交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适位置
  4. 对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶（下沉操作）
  5. 重复 2- 4 步骤，直到堆中剩一个元素为止

优先队列

• 最大优先队列：和堆的算法基本一致，包括插入和删除最大值的操作，堆的数据结构导致，最大值就处于最顶端
• 最小优先队列
  • 最小元素放到数组的索引1处
  • 每个节点的数据总是小于等于它的两个子节点的数据

图

• 定义：有一组顶点和一组能够将两个顶点相连的边组成

• 自环：即一条连接一个顶点和其自身的边

• 平行边：连接同一对顶点的两条边

• 分类：

  • 无向图：边仅仅连接两个顶点，并没有其他含义
  • 有向图：边不仅连接两个顶点，并且具有方向

• 相邻顶点：两个顶点通过一条边相连时，我们称这两个顶点是相邻的。并且称这条边依附于这两个顶点

• 度：依附于该顶点的边的个数

• 子图：是一幅图的所有边的子集组成的图

• 路径：由边的顺序连接的一系列的顶点组成

• 环：是一条至少含有一条边且终点和起点相同的路径

• 连通图：如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就成为连通图

• 连通子图：一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图

存储结构

• 邻接矩阵

  • 使用一个V*V的二维数组int [V] [V] adj,把索引的值看做是顶点
  • 如果顶点v和顶点w相连，我们只需要将 adj [v] [w] 和 adj [w] [v] 的值都设置为1，否则设置为 0
  • 邻接矩阵这种存储方式的空间复杂度是v^2，如果处理的问题规模比较大的话，内存空间极有可能不够用

• 邻接表

  • 使用一个大小为V的数组Queue[V] adj，把索引看做是顶点
  • 每个索引处adj[v]存储了一个队列，该队列中存储的是所有与该点相邻的其他顶点