数据结构

lzhgod2025-01-072025-01-08

树和二叉树、森林

树的先根遍历相当于对应的二叉树的先序遍历

树的后根遍历相当于对应的二叉树的中序遍历

low、high、mid

mid = (high - low) / 2 ，向下取整

若查找的值比mid的值大，令low=mid+1，更新mid；若比mid的值小，令high=mid-1，更新mid

左子树的所有值都小于根节点，右子树的所有值都大于根节点

在二叉搜索树的基础上满足平衡二叉树的条件，即左右子树的高度差不大于1

插入节点：插入到符合的位置，如果不平衡，往上找第一个不平衡的根节点，把这个树摘出来，进行排序，排完序再放回去

在一个数组中，找一个数为基准数，将这个数中所有比基准数大的数放在该数的右边，比基准数小的数放在该数的左边。

将一个记录插入到已排好序的序列中，从而得到一个新的有序序列

将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序

先将整个待排序的记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行一次直接插入排序

重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故称为”冒泡排序”。

插入：在堆的末尾插入元素，然后再进行排序

删除：将堆的最后一个元素覆盖要删除的元素，然后在进行排序

大顶堆：上大下小

小顶堆：上小下大

类似深度优先搜索

把图的所有边去掉，优先选最小的边，直到所有顶点连通，并且不形成环