数据结构--树和树的表示

发表于 2022-03-06 更新于 2024-01-02 分类于知识类阅读次数：本文字数： 1.8k 阅读时长 ≈ 2 分钟

本文写于 2020 年 3 月 23 日，2022 年 3 月 6 日重新整理

写在前面

客观世界中许多事物存在层次关系，如人类的族谱，社会组织的结构等。这些分层次的结构在管理方面具有一定的效率优势，树就是类似的一种具有层次结构关系的数据结构。

二分查找

二分查找 binarySearch 作为一种时间复杂度为的优秀查找算法，其在数据管理的查询方面具有重要地位。二分查找接受被查找元素所属的序列 list （有序的，假设为升序）和被查找元素的值 target 两个参数，它的基本流程如下：

定义两个变量 left 和 right 指向序列的左端和右端，变量 mid 指向两端的中间位置，查找将在这两端之间进行。
初始化 left = 1 ， right = list.length ， mid = (left + right) / 2 。
比较 mid 处的元素与待查找元素 target 之间的关系：
1. 若 list[mid] = target ，说明在 mid 处找到了元素 target ，返回 mid 。
2. 若 list[mid] < target ，说明 target 在 mid 的右侧，这时应把 left 右移为 mid + 1 ，然后更新 mid 为 (left + right) / 2 ，重复过程 3。
3. 若 list[mid] > target ，说明 target 在 mid 的左侧，这时应把 right 左移到 mid - 1 ，然后更新 mid 为 (left + right) / 2 ，重复过程 3。
最后若始终未从过程3.1跳出，则会导致左右交叉即 left > right ，此时说明元素未查找到，应退出程序。

算法C语言代码（伪）如下：

int binarySearch(ElementType *list, int listLength, ElementType target)
{
    int left = 0;
    int right = listLength - 1;
    int mid = 0;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (list[mid] == target)
            return mid;
        else if (list[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1; //means not frond!
}