【数据结构】树的简单分析总结（附js实现）

作者: 前端西瓜哥 | 来源:发表于2019-05-31 15:27 被阅读0次

本文会针对树这种数据结构，进行相关内容的阐述。其实本文应该算是一篇读书笔记。

文章首发于我的个人博客网站：https://blog.fstars.wang/posts/alg-tree-analy-in-js/

内容总览

树
二叉树
二叉查找树
堆和堆的一些操作
堆排序
堆的应用

另外，我先在这里给出 js 实现的源码地址：

树

这里简单说下树是什么。

树是一种非线性的数据结构。树中的元素称为“节点”。每个节点有有限个子节点或没有子节点，且树中不能有环路。

树

两个相连的节点的关系称为 “父子关系”。

一些术语（摘自维基百科）：

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
深度：对于任意节点n，n的深度为从根到n的唯一路径长，根的深度为0；
高度：对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；

二叉树

树有很多种类，比如二叉树、三叉树、四叉树等。但最常用的树就是二叉树。

二叉树是每个节点最多只有两个分支的树结构，这两个分支的节点被称为 左子节点 和 右子节点。

满二叉树，指的是除了叶子节点，每个节点都有两个子节点的二叉树。

完全二叉树：除了最后一层，其他层的节点个数都要最大，且最后一层的节点都靠左排列的二叉树。

满二叉树

可能有人觉得完全二叉树看起来好像没什么用，怎么还靠左边的，靠中间不行吗？其实靠左是因为二叉树的其中一种数据存储方式是用数组存储，使用完全二叉树就不会浪费数组的空间（不会出现一些数组元素不存储的情况）

二叉树的存储

1. 链式存储法

链式存储法，是通过指针的方式来记录父子关系的一种方法。它有点类似链表，每个节点除了保存自身的数据外，还会有left 和 right 两个指针，指向另外两个节点。

const node = {
    data: 1,         // 节点保存的数据
    left: node2,    // 左子节点指向 node2 节点
    right: null     // null 表示没有右子节点
}

2. 顺序存储法

用数组存储。为了代码可读性更好，我们一般会选择浪费数组下标为 0 的存储位置，即根节点在下标为 1 的位置。这时父节点和左右节点的下标关系如下：

left = 2 * i;
right = 2 * i + 1;
i = left / 2;   
i = right / 2;  // 这里是向下取整

这里的 i 为父节点下标，left 和 right 为两个子节点下标。

这里有个要注意的地方：这里的父节点的下标值是子节点除以 2 并取整。（有些编程语言的整数相除，会自动将得到的结果去掉小数部分，而一些编程语言，比如 Javascript，是会得到小数的，需要手动向下取整。）

如果你就是不想浪费数组的第一个元素的存储位置，誓要将根节点保存在数组的第一个位置。那此时父节点和子节点的下标关系为：

left = 2 * i + 1;
right = 2 * i + 2;
i = (left - 1) / 2;
i = (right - 1) / 2;

如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。

二叉树的遍历

这个是很常见的面试题呢。

1. 前序遍历

根左右。 这里的“前”描述的是根节点，即根节点最先输出（打印），然后输出左子树，最后输出右子树。

代码中的树是用 链式存储法 存储的。代码实现用到了递归。

// 前序遍历（根左右）
preOrder() {
    let order = '';
    r(this.root);

    order = order.slice(0, order.length - 1); // 这里只是去掉最后的一个逗号。
    return order;

    // 递归函数
    function r(node) {
        if (!node) return;
        order += `${node.val},`;
        r(node.left);
        r(node.right);
    }
},

2. 中序遍历

左根右。 “中序”的这个“中”也是指的根节点的输出位置是中间。中序遍历先输出左子树，再输出根节点，最后输出右子树。

// 中序遍历
inOrder() {
    let order = '';
    r(this.root);

    order = order.slice(0, order.length - 1);
    return order;

    // 递归函数
    function r(node) {
        if (!node) return;
        r(node.left);
        order += `${node.val},`;
        r(node.right);
    }
},

3. 后续遍历

左右根。 先打印左子树，然后打印根节点，最后打印右子树。

postOrder() {
    let order = '';
    r(this.root);

    order = order.slice(0, order.length - 1);
    return order;

    // 递归函数
    function r(node) {
        if (!node) return;
        r(node.left);
        r(node.right);
        order += `${node.val},`;
    }
},

4. 层次遍历

层次遍历，就是每层的节点从左往右遍历，直到遍历完所有节点。如果是顺序存储法存储的，数组从前往后遍历即可。如果是链式存储法存储树，实现就会复杂一些，要用到一个队列

levelOrder() {
    if (this.root == null) return '';
    let a = [],
        left, right;
    a.push(this.root);

    // 节点入队，指针指向头部元素，如果它有left/right，入队。
    // 指针后移，继续同样步骤。。。直至指针跑到队列尾部后面去。。。
    for(let i = 0; i < a.length; i++) {     // 需要注意的是，数组 a 的长度是动态变化的（不停变长）
        left = a[i].left;
        if (left) a.push(left);

        right = a[i].right;
        if (right) a.push(right);
    }
    return a.map(item => item.val).join(',');
}

二叉查找树

二叉查找树，也叫做二叉搜索树。此外它也被称为 二叉排序树，因为中序遍历就可以得到有序的数据序列（非常高效，时间复杂度是 O(n)）。

二叉查找树的作用是快速查找。除了快速查找，它也支持快速插入、删除数据。

那么什么样的二叉树才是二叉查找树呢？二叉查找树是任意一个节点的左子树的节点都小于该节点，任意一个节点的的右子树的节点都大于该节点的二叉树。

根据定义，二叉查找树是 不允许有两个数据相同的节点的。

二叉查找树的查找操作

先和根节点的值比较，如果相等，就找到了；如果要查找的值比根节点小，就在左子树中递归查找；如果比根节点大，就在右子树中递归查找。

find(val) {
    // 假设二叉树没有重复数据
    let p = this.root;
    while(p != null) {
        if (val == p.val) return p;
        else if (val < p.val) p = p.left;
        else p = p.right;
    }
    return null; // 没找到
},

二叉查找树的插入操作

类似查找操作。从根节点开始，比较要插入的数据和节点的大小关系。如果要插入的数据比当前节点的数据大，且右子树为空，就作为该节点的右子节点；如果右子树不为空，就继续递归右子树。同理，比当前节点数据小，就看该节点的左子树，若为空，插入到左子节点位置；若不为空，就递归左子树。

// 插入节点
insert(val) {
    if (this.root == null) {
        this.root = node;
        return true;
    }

    let node = new Node(val);
    let p = this.root;

    while (p != null) {
        if (val < p.val) {
            if (p.left == null) {
                p.left = node;
                return this.inOrder(); 
                // 返回个中序遍历的结果，检查插入是否正确。（你可以改为 true，表示插入成功）
            }
            p = p.left;
        }
        else if (val > p.val) {
            // preP = p;
            if (p.right == null) {
                p.right = node;
                return this.inOrder();
            }
            p = p.right;
        }

        if (val == p.val) {
            console.warn('二叉树中含相同值的数据，无法插入')
            return false;
        }
    }
},

二叉查找树的删除操作

这个就很复杂，要分三种情况：

要删除的节点没有子节点：直接更新父节点指向其的指针为 null
要删除的节点只有一个子节点：父节点中指向要删除的节点的指针，更新为要删除节点的那个子节点。
要删除的节点有两个子节点：找到右子树中的最小节点（一般是叶子节点），替换到要删除的节点上。（当然你也可以选择找左子树的最大节点）

// 删除
remove(val) {
    // 假设二叉树没有重复数据
    let p = this.root;
    let parent, dir;   // 暂不考虑只有根节点一个的情况。
    while(p != null) {
        
        if (val == p.val) {
            // 要删除的节点没有子节点
            if (p.left == null && p.right == null) {
                parent[dir] = null;
                return true;
            } 
            // 要删除的节点只有一个子节点
            else if (p.left == null && p.right != null) {
                parent[dir] = p.right
                console.log('只有右节点');
                return true;
            } else if (p.right == null && p.left != null) {
                parent[dir] = p.left;
                console.log('只有左节点');
                return true;
            } 
            
            // 要删除的节点有两个子节点
            // 可以将右子树的最小结点替换到被删除的节点位置，并删除这个最小节点
            // 当然你也可以在左子树中找最大节点。
            else if (p.left != null && p.right != null) {
                // 因为要记录最小节点的父节点，所以不能用 this.findMin()
                // 第一步：找出最小节点 minP
                let minParent,
                    minP = p;
                while (minP) {
                    if (minP.left == null) {
                        // 找到。
                        break;
                        // return minP;
                    }
                    minParent = minP;
                    minP = minP.left;
                }

                // 第二步：替换（把数据转移过去即可）
                p.val = minP.val;

                // 第三步：删除最小节点
                if (minP.right == null) {
                    minParent.left = null;
                    console.log('最小节点没有子节点');
                    return true;
                } else if (minP.right != null) {
                    minParent.left = minP.right;
                    console.log('最小节点只有右节点');
                    return true;
                } 

            }
            return p;
        } 

        // 继续找要删除的节点。
        else {
            parent = p;
            if (val < p.val) {
                p = p.left;
                dir = 'left';
            } else {
                p = p.right;
                dir = 'right';
            }
        }
    }
    return null;   // 没找到

    // 要保存父节点，且要记录当前节点是父节点的 left 还是 right。
},

还有另一种简单的删除操作，就是标记一个节点为“已删除”，虽然操作变得简单了，但“已删除”的数据仍然在内存中，会浪费内存空间。

支持重复数据的二叉查找树

一般来说，根据定义，二叉查找树是不允许有重复数据的。但实际开发中，数据一般不可能不重复。所以我们看看怎么使二叉查找树支持重复数据存储：

节点改为可以存储多个数据，而不是只有一个数据。可以考虑链表和动态扩容数组。
插入过程中，如果发现已经有重复的数据了，就放到这个节点的右子树的最左节点的位置（当然你也可以考虑放到左子树的最右边节点位置）。如果是这样的实现的话，查找操作和删除操作就要跟着做一些小修改。

平衡二叉树

维基百科的定义：平衡二叉搜索树（英语：Balanced Binary Tree）是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。它能在O(logn)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。

平衡二叉树的发明，是为了解决二叉树在不断插入、删除等动态操作后，导致时间复杂度退化的问题。它会让二叉树尽量地保持平衡，即保持 矮矮胖胖* 的样子。

平衡二叉树中，最为有名的就是 红黑树 了。是不是经常有群友开玩笑说他们招人，要求当场手写红黑树呢。红黑树的性能很好，广泛用于实际开发中，其他的平衡二叉树则很少出现在人们的视野之中。

平衡二叉树的实现很复杂，就暂时不详细分析了。

堆

堆是一个 每个节点的数据都大于等于（或小于等于）它的子节点的完全二叉树。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作 大顶堆。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作 小顶堆。

因为堆是完全二叉树，所以我们用数组存储。

1. 插入一个元素

插入元素到堆，具体做法是插入到数组的末尾，然后通过堆化操作，对树进行调整，重新变成堆。

堆化（heapify），是指一个节点，不停地向上或向下进行交换，直到找到合适的位置，使当前的二叉树变成堆。

插入时进行的堆化是 从下往上堆化。新插入的元素位于末尾，需要不停地和父元素进行比较和进行交换，直到找到合适的位置结束，此时树就会又变成堆。

// 入堆，从下往上堆化。
insert(val) {
    // count 指的是当前数组存储数据的大小，n 为 数组的容量
    //（当然js的数组是动态数组。这里的 n 是我手动加的限制）
    if (this.count >= this.n) {   
        console.log('堆满了，别加了！！')
        return;
    }
    this.count++;

    let a = this.a;  // a 是存储数据的数组
    a[this.count] = val;

    let i = this.count,
        j = Math.floor(i/2);   // 临时存储 i/2

    while (i > 1 && a[i] > a[j]) {
        [a[i], a[j]] = [a[j], a[i]];
        i = j;
        j = Math.floor(i/2);
    }
    return true;
}

2. 删除堆顶元素

删除了堆顶元素后，我们需要把最后一个元素移动到堆顶元素位置，然后进行 从上往下的堆化。

从上往下堆化具体的实现是：最后一个元素替换掉堆顶元素后，就比较堆顶元素和它的两个子节点，看看谁最大，如果不是堆顶元素最大，堆顶元素就和值最大的子节点交换。重复上面的步骤，直到当前节点最大或者当前节点成为叶子节点（到底了）。

// 删除堆顶元素
removeMax() {
    if (this.count == 0) return false;  // 堆为空

    this.a[1] = this.a[this.count];
    this.a[this.count] = undefined;
    this.count--;

    // 从上往下 堆化
    let i = 1,
        maxPos = i;

    while (true) {
        if (i * 2 <= this.count && this.a[i*2] > this.a[maxPos]) maxPos = i * 2;
        if (i * 2 + 1 <= this.count && this.a[i*2 + 1] > this.a[maxPos]) maxPos = i * 2 + 1;
        if (maxPos == i) {
            break;
        }
        [this.a[i], this.a[maxPos]] = [this.a[maxPos], this.a[i]];
        i = maxPos;
    }
    return true;
}

堆排序

堆排序算法分两个步骤：先建堆，然后进行排序。

1. 建堆

对数组进行原地建堆。原地是指在原数组上进行操作，不需要另开一个堆。

建堆的方式有两种：

借助前面提到的插入操作的方式。

这里就是往 “堆区域” 末尾插入元素，然后从下往上堆化。类似插入排序，我们将数组分为 “堆区域” 和 “未处理区域”，不停地将“未处理区域”里的元素插入到“堆区域” 中，直到遍历完整个数组。

从最后一个非叶子节点开始往前，进行 从上往下的堆化。

叶子节点因为没有子节点，所以不需要进行堆化。另外，对于完全二叉树来说，最后一个非叶子节点的下标为 i / 2（i 从1开始，你可以自己画个完全二叉树验证一下）。

建堆的复杂度是 O(n)。

2. 排序

将堆顶节点和最后一个节点进行交换，然后对剩余的 n -1 个元素进行从上往下堆化。然后我们再交换堆顶节点和第 n - 1 个元素，然后对剩余的 n - 2 个元素进行从上往下堆化，就这样不停地交换和堆化，直到堆中只有一个元素。

性能分析

1. 堆排序的时间复杂度是 O(nlogn)。

建堆的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以堆排序的时间复杂度是 O(nlogn)。

2. 堆排序是不稳定的排序

因为排序过程中，堆顶元素会和堆的最后一个元素进行交换，导致排序不稳定。

3. 堆排序是原地排序

堆排序和快速排序的比较

快速排序比堆排序好。理由如下：

堆排序访问数据方式不好，是跳着访问数组元素的，不利于 CPU缓存。
堆排序的交换操作更多。堆排序的建堆完成后，会降低数据的有序堆，这样会使得交换操作变多。

代码实现是在原数组上进行数据交换的。

堆的应用

1. 优先级队列

优先级可以用于解决 合并有序小文件、高性能定时器 等问题。

2. 求 TopK 数据

这个就是维护一个大小为 k 的小顶堆。将未入堆的元素和堆顶元素比较，如果比堆顶元素大，就入堆，直到所有元素都入堆后，这个堆就是 TopK 元素了。

时间复杂度是 O(nlogK)。最坏情况下，一次堆化需要 O(logK)，要进行 n 次堆化操作。

3. 求中位数

如果是静态数据，先排序，然后求中位数即可，这样边际成本低。

如果是动态数据，那就需要维护一个大顶堆和一个小顶堆。要求大顶堆的数量等于小顶堆的数量或小顶堆的数量+1，且大顶堆的元素都小于小顶堆的元素。中位数即大顶堆的堆顶元素。

大顶堆和小顶堆

初始化的时候，可以用类似 topK 算法，弄一个数量为 k 为 n/2 的小顶堆放数组右边，然后将剩余的元素转换为大顶堆。

然后每次添加数据的时候，都会分别比较大顶堆的堆顶元素和小顶堆的堆顶元素，决定插入到哪边。插入后，还要进行一些堆的插入和删除操作，以维持这两个堆数量要差不多相同（左右元素数量相同或者左边堆比右边多一个）。

除了可以利用堆求中位数，我们还可以利用堆计算 “99% 响应时间” 的问题。即维护数量为 99/n 的大顶堆和数量为 1/n 的小顶堆。