查找与排序

查找

查找的基本概念和顺序查找

• 查找定义：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
• 关键字：数据元素中某个可以以唯一标识该元素的数据项。
• 平均查找长度（ASL：Average Search Length）：在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。
• 顺序查找（线性查找）：主要用于在线性表中进行查找。从查找表的一端开始，顺序扫描查找表，依次将扫描到的关键字和待查找的值key进行比较。如果相等，则查找成功。如果扫描结束仍然没有发现相等的数据元素，则查找失败。
  • 时间复杂度为O(n)。

折半查找

• 算法思路：
  • 首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中。然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止，或者确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
• 折半查找分析：
  • 折半查找判定树。
  • 对于折半查找，查找的比较次数就是从根结点到该结点经历的结点数。
  • 时间复杂度为O(logn)。
  • 概要：具有N个（N>0）结点的完全二叉树的高度为 log₂(N+1) +1。

分块查找

• 分块查找又称为索引顺序查找。
• 分块查找极速赛车开奖直播历史记录：
  • ① 确定待查找值在哪个块（折半查找）。
  • ② 在确定的块中查找待查找值（顺序查找）。
• 分块查找分析：
  • 由于分块查找实际是进行两次查找，所以整个算法的平均查找长度是两次查找的平均查找长度之和。即ASL分块 = ASL折半 + ASL顺序。

二叉排序树

• 二叉排序树（Binary Search Tree，也叫二叉搜索树）或者是一棵空极速赛车开奖直播历史记录树，或者是具有以下性质的二叉树：
  • ① 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
  • ② 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
  • ③ 它的左右子树也是一棵二叉排序树。
• 算法思想：
  • 由于二叉排序树的特点（左子树<根结点<右子树），所以每次查找一个关键字，需要先和根结点进行比较：
    • 如果这个关键字小于根结点的值，则再到这个根结点的左子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。
    • 如果这个关键字大于根结点的值，则再到这个根结点的右子树进行同样的比较操作一直进行下去直到找到极速赛车开奖直播历史记录该关键字，表示查找成功，或者是空指针，表示查找失败。
  • 插入关键字代码：
    • 1. 空树：直接插入新结点返回成功。
    • 2. 树不空：检查是否存在关键字重复的结点：
      • ① 存在：返回插入失败。
      • ② 不存在：检查根结点的值和待插入关键字值的大小关系递归插入左右子树。
  • 删除结点：
    • 极速赛车开奖直播历史记录① 删除的是叶子结点：直接删去该结点即可。
    • ② 删除的是仅有左子树或者右子树的结点：“子承父业”。
    • ③ 删除的是左右子树都有的结点：找到待删除结点的直接前驱或者直接后继结点，用该结点来替换待删除结点，再删除该结点。
• 二叉排序树分析：
  • 查找时间复杂度是O(n)。
• 概要：“左小右大”。

平衡二叉树（AVL树）

• 平衡二叉树（AVL树）是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树。
• 平衡因子：定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是−1、0或1。
• 平衡调整：
  • 平衡二叉树的建立过程和二叉排序树的建立过程是相似的，都是从一棵空树开始陆续插入结点。不同的地方在于对于平衡二叉树的建立过程中，由于插入结点可能会破坏结点的平衡性，所以需要进行平衡调整。
• LL调整（左孩子的左子树上插入结点导致）：
  • 最小不平衡子树根结点的平衡因子为2>0，它的左孩子结点平衡因子为1>极速赛车开奖直播历史记录0，两个都大于极速赛车开奖直播历史记录0，所以直接右旋就可以调整。
  • 概要：“正则右旋”。
• RR调整（右孩子的右子树上插入结点导致）：
  • 最小不平衡子树根结点的平衡因子为-2<0，它的右孩子结点平衡因子为-1<0，两个都小于0，所以直接左旋就可以调整。
  • 概要：“负则左旋”。
• LR调整（左孩子的右子树上插入结点导致）。
• RL调整（右孩子的左子树上插入结点导致）。
• 概要：先局部转换为LL或RR，最后进行调整。
• 分析：
  • 含有n个结点平衡二叉树的最大深度为O(log₂n)，因此，平衡二叉树的平均查找长度为O(log₂n)。

B树和B+树

• 2-3树：
  • 2-3树是一种多路查找树：2和3的意思就是2-3树包含两种结点：
    • 1. 2结点包含一个元素和两个孩子（或者没有孩子）。
      • ① 左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值。
      • ② 2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子。
    • 2. 3结点包含一大一小两个元素和三个孩子（或者没有孩子）。（两个元素按大小顺序排列好）
      • ① 左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。
      • ② 3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子。
    • 3. 2-3树所有叶子结点都在同一层次。
• 2-3-4树：
  • 2-3-4树也是一种多路查找树：2和3和4的意思就是2-3-4树包含三种结点：
    • 1. 2结点包含一个元素和两个孩子（或者没有孩子）。
      • ① 左子树包含的元素小于该结点的元素极速赛车开奖直播历史记录值，右子树包含的元素大于该结点的元素值。
      • ② 2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子。
    • 2. 3结点包含一大一小两个元素和三个孩子（或者没有孩子）。
      • ① 左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。
      • ② 3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子。
        极速赛车开奖直播历史记录 * 3) 4结点包含小中大三个元素和四个孩子（或者没有孩子）。
      • ① 左子树包含的元素小于该结点最小的元素值，第二个子树包含大于最小的元素值小于中间元素值的元素，第三个子树包含大于中间元素值小于最大元素值的元素，右子树包含的元素大于该结点最大的元素值。
      • ② 4结点要不有四个孩子，要不就没有孩子，不允许有一个或两个或三个孩子。
    • 4. 2-3-4树所有叶子结点都在同一层次。
• B树：
  • B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。一棵m阶B树或为空树，或为满足如下特性的m叉树：
    • 1）树中每个结点至多有m棵子树。（即至多含有m-1个关键字) ("两棵子树指针夹着一个关键字")
    • 2）若根结点不是终端结点，则至少有两棵子树。(至少一个关键字)
    • 3）除根结点外的所有非叶结点至少有 ⌈m/2⌉棵子树。（即至少含有⌈m/2⌉-1个关键字）
    • 4）所有非叶结点的结构如下：
    • 5）所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)
  • B树的查找操作：
    • 查找过程：
      • ① 先让待查找关键字key和结点的中的关键字比较，如果等于其中某个关键字，则查找成功。
      • ② 如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。
      • Eg: 如果Key比第一个关键字K1还小，则去P0指针所指向的子树中查找，如果比最后一个关键字Kn还大，则去Pn指针所指向的子树中查找。
  • B树的插入操作：
    • 分裂的方法：取这个关键字数组中的中间关键字(⌈n/2⌉)作为新的结点，然后其他关键字形成两个结点作为新结点的左右孩子。
  • B树的删除操作：
    • B树中的删除操作与插入操作类似，但要稍微复杂些，要使得删除后的结点中的关键字个数≥⌈极速赛车开奖直播历史记录m/2⌉-1 ，因此将涉及结点的“合并”问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点上两种情况。
      • 1）如果删除的关键字在终端结点上（最底层非叶子结点）：
        • ① 结点内关键字数量大于⌈m/2⌉-1 ，这时删除这个关键字不会破坏B树的定义要求。所以直接删除。
        • ② 结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中存在关键字数量大于⌈m/2⌉-1 的结点，则去兄弟阶段中借关键字。
        • ③ 结点极速赛车开奖直播历史记录内关键字数量等于⌈m/2�极速赛车开奖直播历史记录�-1 ，并且其左右兄弟结点中不存在关键字数量大于⌈m/2⌉-1 的结点，则需要进行结点合并。
      • 2）如果删除的关键字不在终端结点上（最底层非叶子结点）：需要先转换成在终端结点上，再按照在终端结点上的情况来分别考虑对应的方法。
        • 相邻关键字：对于不在终端结点上的关键字,它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。
        • 第一种情况：存在关键字数量大于⌈m/2⌉-1 的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换待删除的关键字。
        • 第二种情况：左右子树的关键字数量均等于⌈m/2⌉-1 ，则将这两个左右子树结点合并，然后删除待删除关键字。
• B+树：
  • B+树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构。
  • m阶的B+树与m阶的B树的主要差异在于：
    • 1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有(n+1)棵子树。
    • 2）在B+树中，每个结点（非根内部结点）关键字个数n的范围是 ⌈m/2⌉≤n≤m（根结点1≤n≤m），在B树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉ -1≤极速赛车开奖直播历史记录n≤m-1（根结点：1≤n≤m-1）。
    • 3）在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，极速赛车开奖直播历史记录不含有该关键字对应记录的存储地址。
    • 4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

散列表

• 散列表：根据给定的关键字来计算出关键字在表中的地址的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。
• 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。
• 散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为“冲突”，这些发生碰撞的不同关键字称为同义词。
• 构造散列函数的tips：
  • 1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
  • 2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生。
  • 3）散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。
• 常用Hash函数的构造方法：
  • 1. 开放定址法：直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=a×key+b。式中，a和b是常数。这种方法计算最简单，并且不会产生冲突。
  • 2. 除留余数法：假定散列表表长为m，取一个不大于m但最接近或等于m的质极速赛车开奖直播历史记录数p，利用以下公式把关键字转换成散列地址。散列函数为H(key)=key % p。除留余数法的关键是选好p，使得每一个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。
  • 3. 数字分析法：设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有极速赛车开奖直播历史记录某几种数码经常出现，则应选取数码分布较为均匀的若干极速赛车开奖直播历史记录位作为散列地址。这种方法适合于已知的关键字集合。
  • 4. 平方取中法：顾名思义，取关键字的平方值的中间几位作为散列地址。具体取多少位要看实际情况而定。这种方法得到的散列地址与关键字的每一位都有关系，使得散列地址分布比较均匀。
  • 5. 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到散列地址。
• 常用Hash函数的冲突处理办法：
  • 1. 开放定址法极速赛车开奖直播历史记录：将产生冲突的Hash地址作为自变量，通过某种冲突解决函数得到一个新的空闲的Hash地址。
    • 1）线性探测法：冲突发生时，顺序查看表中下一个单元（当探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
    • 2）平方探测法：设发生冲突的地址为d,平方探测法得到的新的地址序列为d+1²，d-1²，d+2²，d-2²......平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
    • 3）再散列法：又称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(Key)得到的地址发生冲突时，则利用第二个散列函数Hash2(Key)计算该关键字的地址增量。
    • 4）伪随机序列法：当发生地址冲突时，地址增量为伪随机极速赛车开奖直播历史记录数序列，称为伪随机序列法。
  • 2. 拉链法：对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。拉链极速赛车开奖直播历史记录法适用于经常进行插入和删除的情况。
  • 3. 散列表的查找过程：类似于构造散列表，给定一个关键字Key。
    • 先根据散列函数计算出其散列地址。然后检查散列地址位置有没有关键字。
      • 1. 如果没有，表明该关键字不存在，返回查找失败。
      • 2. 如果有，则检查该记录是否等于关键字。
        • ① 如果等于关键字，返回查找成功。
        • ② 如果不等于，则按照给定的冲突处理办法来计算下一个散列地址，再用该地址去执行上述过程。
  • 4. 散列表的查找性能：和装填因子有关。
    • α越大，表示装填的记录越“满”，发生冲突的可能性就越大，反之发生冲突的可能性越小。

排序

排序的基本知识

• 定义：排序就是将原本无序的序列重新排列成有序的序列。
• 排序的稳定性：
  • 如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

插入类排序

• 直接插入排序：
  • 直接插入排序：首先以一个元素为有序的序列，然后将后面的元素依次插入到有序的序列中合适的位置直到所有元素都插入有序序列。
  • 时间复杂度为O(n²)。
  • 直接插入排序是稳定性是稳定的。
• 折半插入排序：
  • 折半插入排序将比较和移动这两个操作分离出来，也就是先利用折半查找找到插入的位置，然后一次性移动元素，再插入该元素。
  • 折半插入排序的时间复杂度为O(n²)。
  • 稳定性：和直接插入排序稳定性相同，是稳定的。
• 希尔排序：
  • 希尔排序的基本思想：希尔排序本质上还是插入排序，只不过是把待排序序列分成几个子序列，再分别对这几个子序列进行直接插入排序。
    • ①先以增量5来分割序列，也就是下标为0,5,10,15...的关键字分成一组，下标为1,6,11,16..分成一组,然后对这些组分别进行直接插入排序，这就完成了一轮希尔排序。
    • ②缩小增量(d1=n/2，di+1= di/2= [5/2]=2,并且最后一个增量等于1),所以第二轮以增量为2进行类似的排序过程。
    • ③接下来的第三轮，第四轮...都是类似的过程，直到最后一轮以增量为1。此时就是前面所说的直接插入排序。
  • 概要:
  • 时间复杂度：... 希尔排序的时间复杂度约为O(n^1.3) 在最坏情况下希尔排序的时间复杂度为O(n^2)
  • 空间复杂度：希尔排序的空间复杂度为O(1)
  • 稳定性：不稳定，由于不同的增量可能就会把相等的关键字划分到两个直接插入排序中进行排序， 可能就会造成相对顺序变化。

交换类排序

• 冒泡排序：
  • 假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即Ai-1），则交换它们，直到序列比较完。我们称它为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，……，这样最多做n-1趟冒泡就能把所有元素排好序。
  • 空间复杂度：交换时开辟了存储空间来存储中间变量，所以空间复杂度为O(1)
  • 时间复杂度
  • 稳定性：当两个关键字相等，if判断条件不成立，所以不会发生数据移动。所以是稳定的。
• 快速排序：
  • 快速排序是一种基于分治法的排序方法。每一趟快排选择序列中任一个元素作为枢轴(pivot)(通常选第一个元素)，将序列中比枢轴小的元素都移到枢轴前边，比枢轴大的元素都移到枢轴后边。
  • 时间复杂度：最好情况下时间复杂度为O(nlogn) ,待排序序列越无序，算法效率越高。 最坏情况下时间复杂度为O(n^2)，待排序序列越有序，算法效率越低。
  • 空间复杂度：由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为 ⌈log2(n+1)⌉(每次partition都很均匀)递归树的深度O(logn)最坏情况下，因为要进行n-1次递归调用，所以栈的深度为极速赛车开奖直播历史记录O(n)；
  • 稳定性：快速排序是不稳定的，是因为存在交换关键字。

选择类排序

• 简单选择排序：
  • 空间复杂度：需要额外的存储空间仅为交换元素时借助的中间变量，所以空间复杂度是O(1)
  • 时间复杂度：关键操作在于交换元素操作，整个算法由双重循环组成，外层循环从0到n-2一共n-2+1=n-1次，对于第i层外层循环，内层循环执行n-1-(i+1)+1=n-i-1次。 当i=0,内层循环执行n-1次，当极速赛车开奖直播历史记录i=n-2,内层循环执行1次，所以是一个等差数列求和,一共为(1+n-1)(n-1)/2=n(n-1)/2 ,所以时间复杂度为O(n^2)
  • 稳定性：不稳定 原因就在于交换部分会打破相对顺序
• 堆排序：
  • 什么是堆？
    • 堆是一棵完全二叉树，而且满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。
      • 如果是每个结点的值都不小于它的左右孩子结点的值，则称为大顶堆。
      • 如果是每个结点的值都不大于它的左右孩子结点的值，则称为小顶堆。
  • 什么是堆排序？
    • 我们知道对于一个堆来说，它的根结点是整个堆中所有结点的值的最大值(大顶堆)或者最小值(小顶堆)。所以堆排序的思想就是每次将无序序列调节成一个堆，然后从堆中选择堆顶元素的值，这个值加入有序序列，无序序列减少一个，再反复调节无序序列，直到所有关键字都加入到有序序列。
    • 时间复杂度： 堆排序的总时间可以分为①建堆部分+②n-1次向下调整堆
      堆排序的时间复杂度为O(n)+O(nlog2n)=O(nlog2n)
  • 堆排序不稳定

归并排序

• 假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并，得到 ⌈n/2⌉个长度为2或1的有序表；再两两归并，……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。
• 例如：49 38 65 97 76 13 27
  • ①首先将整个序列的每个关键字看成一个单独的有序的子序列
  • ②两两归并，49和38归并成38 49，65和97归并成65 97，76和13归并成13 76，27没有归并对象
  • ③两两归并，38 49和65 97归并成38 49 65 97，13,76和27归极速赛车开奖直播历史记录并成13 27 76
  • ④两两归并，38 49 65 97和13 27 76归并成13 27 38 49 65 76 97
• 时间复杂度：O(nlog2n)
• 空间复杂度:因为需要将这个待排序序列转存到一个数组，所以需要额外开辟大小为n的存储空间，即空间复杂度为O(n)
• 稳定性：稳定

基数排序

• 基数排序(也叫桶排序)是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。
• 例子：53, 3, 542, 748, 14, 214, 154, 63, 616
  • 补充位数：053, 003, 542, 748, 014, 214, 154, 063, 616
  • 桶实际是一个队列，先进先出(从桶的上面进，下面出)
  • 关键字数量为n,关键字的位数为d,比如748 d=3，r为关键字的基的个数，就是组成关键字的数据的种类，比如十进制数字一共有0至9一共10个数字，即r=10
• 空间复杂度：需要开辟关键字基的个数个队列，所以空间复杂度为O(r)
• 时间复杂度：需要进行关键字位数d次"分配"和"收集"，一次"分配"需要将n个关键字放进各个队列中，一次"收集"需要将r个桶都收集一遍。所以一次"分配"和一次"收集"时间复杂度为O(n+r)。d次就需要O(d(n+r))的时间复杂度。
• 稳定性：由于是队列，先进先出的性质，所以在分配的时候是按照先后顺序分配，也就是稳定的，所以收集的时候也是保持稳定的。即基数排序是稳定的排序算法。

外部排序

• 需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序的方法就叫做外部排序。
• 如何得到初始的归并段
  • 置换选择排序：解决排序段放入内存的问题
• 如何减少多个归并段的归并次数
  • 最佳归并树：最少的归并次数（I/O次数）
• 如何每次m路归并快速得到最小的关键字
  • 败者树：减少比较次数
• 概要: 内存容量无法容纳大量数据

二叉树与树与森林

树与二叉树

• 如何将一棵树转化成二叉树？
  • 树的孩子兄弟表示法与二叉树的二叉链表表示法都是用到两个指针
    • 将孩子兄弟表示法理解成二叉链表
  • 树转换成二叉树的手动模拟方法：
    • ①将同一结点的各个孩子用线串连起来
    • ②将每个结点的子树分支，从左往右，除了第一个以外全部删除
    • 概要: 例子
• 如何将一棵二叉树转化成树？
  • 二叉树转换成树的手动模拟方法：
    • ①将二叉树从上到下分层，并调节成水平方向。(分层方法：每遇到左孩子则为一层)
    • ②找到每一层的双亲结点，方法为它的上一层相连的那个结点就是双亲结点。例如bcd这一层，与它相连的上一层结点即为a,所以bcd这三个结点的双亲结点都是a.
    • ③将每一层结点和其双亲结点相连，同时删除该双亲结点各个孩子结点之间的联系。
    • 概要: 例子

森林与二叉树

• 森林：森林是m（m≥0）棵互不相交的树的集合
• 如何将森林转换成二叉树？
  • 森林转换成树的手动模拟方法：
    • ①将森林中每棵树都转换成二叉树
    • ②将第二棵树作为第一棵树的根结点的右子树，将第三棵树作为第二棵树的根结点的右子树..依次类推
    • 概要: 例子
• 如何将二叉树转换成森林？
  • 二叉树转换成森林的手动模拟方法：
    • 反复断开二叉树根结点的右孩子的右子树指针，直到不存在根结点有极速赛车开奖直播历史记录右孩子的二叉树为止。
    • 概要: 例子

树与森林的遍历

• 先序：先访问根结点，再访问根结点的每棵子树。 访问子树也是按照先序的要求
• 后序：先访问根结点的每棵子树，再访问根结点。 访问子树也是按照先序的要求
• 树的先序遍历等于它对应二叉树的先序遍历，后序遍历等于它对应的二叉树的中序遍历
• 概要: 例子