第四期:数据结构(下)——再来实现一下二叉搜索树、二叉堆和图

780 阅读6分钟

js篇没有结束喔,只不过先复习一下数据结构吧

前两天看到一个大佬发的关于数据结构的博客,满满的字一个代码没有,众人都说太干了。然后小白就写一个只实现的吧

注意这里是下篇

希望你有一些数据结构的基础,了解他们的基本结构。这里主要是实现!!!

图中的图片,一部分是自己画的,一部分是百度图片找的。原来在某c开头的博客上记录笔记故有了上面的水印。

函数式编程的下篇毁于掘金更新那段时间了,很痛心,希望后面忍着泪补上 希望与大家共同进步,代码过多难免有疏漏,且图的部分因为有很多大佬写过了故我这里主要写的是其核心思想(像判空这类的细节没有处理)。如有误,望指教,感恩

代码过多不能排版,只能处理处理头部这样过过日子

上篇链接

此系列博客文章进度

✅js篇

🔲html、css篇

🔲DOM、BOM篇

🔲轮子篇

🔲打包工具篇

✅数据结构篇

🔲前端必刷小算法篇

🔲HTTP篇

🔲性能优化篇

🔲常见设计模式篇

一、 二叉搜索树

树的实现与其相关操作其实都很简单,它的核心就是依靠递归嘛

至于我们为啥上来就直接实现二叉搜索树,而不是别的什么树呢?

首先这树这种数据结构中,其二叉树是最为重要的(也即度小于等于2)。

但是呢?在二叉树中,二叉搜索树又是极为重要且经典的数据结构

why?

那什么是二叉搜索树呢?

即它在二叉树的基础上又做了一个规定, 即只允许你在左侧节点存(比父节点)小的值,在右侧节点存储(比父节点)大的值。 左小右大嘛方便后面的搜索

在下面我们将实现以下方法

  • add(key)向树中添加节点
  • 遍历(中序先序后序只是输出key的位置不同而已,以中序为例)
  • min()取最小值
  • max()取最大值
  • search(key)判数组是否存在某值
  • remove(key)删除树中某节点

实现

1. 添加节点

add(key) {
            const node = new TNode(key)

            // 下面两种情况,树为空或不空
            if (this.root === null) {
                this.root = node
            }
            // 不为空得找地方,另写一个方法
            else {
                this._addNode(this.root, node)
            }
        }
        _addNode(node, newNode) {
            // 首先跟根节点比较大小以判断一会往左方还是往右方
            // 放右边去吧
            if (newNode.key > node.key) {
                if (node.right === null) {
                    node.right = newNode
                } else {
                    this._addNode(node.right, newNode)
                }
            }
            // 放左边去吧
            else {
                if (node.left === null) {
                    node.left = newNode
                } else {
                    this._addNode(node.left, newNode)
                }
            }
        }

2. 遍历(前中后序遍历只在于打印语句代码的先后顺序)

// 中序遍历
        //如果你对递归理解的不是很好,小白这里简单解释一下
        // 首先这句this._middleTraversal(node.left),即进入函数看有无左孩子,有接着往左边跑,什么时候到打印语句呢?肯定此时已经到了最左边,开始之心函数下面的语句,打印就不用说了,打印完了再看它有无右孩子
        // 接着这个递归栈开始弹栈,到上一个左孩子的父节点,然后打印看有无右孩子
        //就这样随着弹栈,随着打印,随着判断有孩子,有有孩子就进去处理
        //右的方式同理
        _middleTraversal(node) {
                if (node != null) {
                    // 去找左边
                    this._middleTraversal(node.left)

                    // 左到头了,开始打印
                    console.log(node.key)

                    this._middleTraversal(node.right)

                }
            }
            // 对外暴露这个中序遍历的方法,以为上面的还有传入根节点
        middleTraversal() {
            this._middleTraversal(this.root)
        }

3. 取最大、取最小值

// 我们都清楚一般使用递归的也可使用循环进行改造
        // 递归简单好理解,但是性能差
        // 循环不好理解,但是性能好(这里的都比较简单)
        // 下面,我min用循环,max用递归
        min() {
            return this._minNode(this.root).key
        }

        //根据二叉搜索树的特性,最小值就是最左边的呗
        _minNode(node) {
            while (node != null && node.left != null) {
                node = node.left
            }
            return node
        }

        max() {
            return this._maxNode(this.root).key
        }

        // 在最右边呗
        _maxNode(node) {
            if (node.right === null) {
                return node
            } else {
                return this._maxNode(node.right)
            }

        }

4. 搜索指定节点

       isKey(key) {
            return this._isKey(this.root, key)
        }
        _isKey(node, key) {
            if (node === null) {
                return false
            }
            // 左边
            if (node.key > key) {
                return this._isKey(node.left)
            }
            // 右边
            else if (node.key < key) {
                return this._isKey(node.right)
            }
            // 相等
            else if (node.key === key) {
                return true
            } else {
                return false
            }
        }

5. 移出节点(本章难点)

这段代码的难点是在于返回值有一个易错点

错误示例

容易认为像这样

// 情况二 if (node.left != null && node.right === null) { node = node.left return true }

直接node=node.left,就认为它们之间的指针关系连接好了,但其实并没有。其父节点仍然是指向的原来的子节点,即这棵树你根本没有做任何改变

为啥呢?因为你这样写是拿不到它的父节点的,它父节点指向的还是原来的它子节点那块地址

你可能又会说我不是改变node的值了么?

首先node只是个变量,它原先指的是一个对象的,你现在又让它指向一个新的对象

可是其父节点中指针域可不是指的你node啊,它指的你node指向的那块地址。此时你node又指向了新的地址,其父节点可不会跟着变化啊(小白还是纯小白时犯下的错误,公开处刑?害,谁让那时自己基础差啊,改了得有2-3天)

 remove(key) {
            return this._remove(this.root, key)
        }

        // 这里有三种情况
        // 1. 叶子节点,直接干掉即可
        // 2. 有一个孩子,那么将它的孩子作为继承人就行了
        // 3. 两孩子就比较难受了,得找一个和它比较像的吧。有两个,它左子树的右叶子和它右子树的左叶子。这里我们将它的继承者定为它右子树的左叶子。
        _remove(node, key) {
            if (node.key > key) {
                return this._remove(node.left, key)

            } else if (node.key < key) {
                return this._remove(node.right, key)

            }
            // 找到了开始删除
            else if (node.key === key) {
                // 情况一
                if (node.left === null && node.right == null) {
                    node = null
                    return true
                }
                // 情况二
                if (node.left != null && node.right === null) {
                    node = node.left
                    return true
                }
                if (node.left === null && node.right != null) {

                    node = node.right
                    return true
                }

                // 情况三
                const rightTree = node.right
                const currentKey = this._minNode(rightTree).key
                node.key = currentKey

                this._remove(node.right, currentKey)
                return true

            } else {
                return false
            }
        }
    }

正确代码

        remove(key) {
            return this.root = this._remove(this.root, key)
        }

        // 这里有三种情况
        // 1. 叶子节点,直接干掉即可
        // 2. 有一个孩子,那么将它的孩子作为继承人就行了
        // 3. 两孩子就比较难受了,得找一个和它比较像的吧。有两个,它左子树的右叶子和它右子树的左叶子。这里我们将它的继承者定为它右子树的左叶子。
        _remove(node, key) {
            if (node.key > key) {
                node.left = this._remove(node.left, key)
                return node
            } else if (node.key < key) {
                node.right = this._remove(node.right, key)
                return node
            }
            // 找到了开始删除
            else if (node.key === key) {
                // 情况一
                if (node.left === null && node.right == null) {
                    node = null
                    return node
                }
                // 情况二
                if (node.left != null && node.right === null) {
                    node = node.left
                    return node
                }
                if (node.left === null && node.right != null) {

                    node = node.right
                    return node
                }

                // 情况三
                const rightTree = node.right
                const currentKey = this._minNode(rightTree).key
                node.key = currentKey

                node.right = this._remove(node.right, currentKey)
                return node

            } else {
                return false
            }
        }
    }

部分测试代码

  tree.add(6)
    tree.add(7)
    tree.add(4)
    tree.add(2)
    tree.add(10)
    tree.middleTraversal()
    console.log(tree.min())
    console.log(tree.max())
    console.log(tree.remove(6))

    console.log(tree)
    console.log(tree.isKey(11))

二、 二叉堆

终于到了一个比较来说实现不是那么常规的数据结构的实现了

首先来了解一下什么是二叉堆?

二叉堆的本质是一个完全二叉树,且其又有最大堆最小堆之分

最小堆:任何一个父节点的值都要小于它左右孩子的值

最大堆与最小堆相反

来看二叉堆的实现吧(原理一下,这里我们以最小堆为例)

我们接下来我实现以下功能:

  • insert(val)像堆中插入新数据
  • extract()剔除最小值(最小堆),最大堆就剔除最大值
  • findMin() 返回最小者,最大堆中就findMax返回最大值呗

前提: 我们要知道储存一棵二叉树一般有两种方式,一个是“指针”的形式即保存数据之间的联系。 第二种形式即使用数组,我们可以事先给树编写序号,利用数组的索引位置一一对应。如下图

这时我们就得需要知道一些东西

在数组中给我们一个数据的位置,我们如何拿到它的父、子节点? 通过一些规律观察我们可以有以下结论。 数组中如果给定一已存储了节点元素个位置index,那么

  • 它的左子节点位置是 2 * index + 1;
  • 它的右子节点位置是 2 * index + 2;
  • 它的父节点位置是(index -1)/ 2(向下取整,根节点除外)。

工具函数

 class MinHeap {
        constructor() {
            this.data = []
        }

        //先写三个工具函数

        // 拿左孩子
        _getLeftIndex(index) {
            return 2 * index + 1
        }

        // 拿右孩子
        _getRightIndex(index) {
            return 2 * index + 2
        }

        //拿父节点
        _getParentIndex(index) {
            if (index === 0) {
                return undefined
            } else {
                return Math.floor((index - 1) / 2)
            }
        }
 }

insert:插入数据

实现insert方法的核心就是它里面的上移操作。 什么上移及怎么上移呢? 看图 (图片是以前画的,其水印是我原来在某c开头博客做笔记时上传的,下面是我又截下来的)

新来一个节点2,要加入堆中,开始加入堆底。即放到节点3的右孩子位置上

这是因为二叉堆的特性,最小堆父节点数据是要小于它每个子节点的。现在不符合这一特性了,即节点2要进行上移。怎么上移呢,它先和自己的父节点进行数据的比较。若比其父节点数值小。则进行位置交换

交换完成

实现

        insert(value) {

            this.data.push(value) //此时相当于新来的在树的最后了
            this._upHead(this.data.length - 1) //进行上移

        }
        // 上移
        _upHead(index) {
            // 拿其父节点
            let parent = this._getParentIndex(index)

            while (index > 0 && (this.data[index] < this.data[parent])) {
                // 交换
                this._swap(this.data, parent, index)
                index = parent
                parent = this._getParentIndex(index)
            }
        }
        // 交换
        _swap(arr, a, b) {
            [arr[b], arr[a]] = [arr[a], arr[b]]
        }

extract:剔除堆顶

extract方法的作用是剔除堆顶。 extract方法的核心是堆化,先来看看堆化的思路吧。

如下图我们要剔除堆顶,不能直接剔除就完事了吧。。。我们还要保持它的堆结构呢,怎么保持呢?

首先让这个堆顶节点1与它的子节点比较,小于它的子节点(废话嘛)。交换两者位置

交换完成之后,再与它的子节点比较。这时就出现了一点问题。如果是和节点7交换,那么我们直接pop掉即可,和6交换我们要怎么办呢?去data里面去找到吗?这显然不是我们不需要的。

来再换一种方法吧

首先我们就先把堆顶和堆底节点互换,然后把换完的新堆底扔出去

这时新堆顶是7,它要下移。则有子节点比较。交换位置

接着比较,交换位置

再换,大功告成

       extract() {
            //空堆
            if (this.data.length === 0) {
                return false
            }
            if (this.data.length === 1) {
                return this.data.pop()
            }
            // 堆中有多值
            let current = this.data[0] //要删除的

            // 交换
            this._swap(this.data, 0, this.data.length - 1)
                //移出
            this.data.pop()

            // 下移
            this._sinkDown(0)
            return current

        }

        // 堆化(下移)
        _sinkDown(index) {
            let current = index
            let left = this._getLeftIndex(index)
            let right = this._getRightIndex(index)
            let size = this.data.length

            //与左孩子比较
            if (this.data[current] > this.data[left] && left < size) {

                current = left
            }
            if (this.data[current] > this.data[right] && left < size) {

                current = right
            }

            //current发生了变动,开始进行交换及其递归处理,没有发生变动则说明此时已经是堆化的结构了
            if (index != current) {
                this._swap(this.data, index, current);
                this._sinkDown(current)
            }

        }

findMin :返最小值(即堆顶)

        findMin() {
            return this.data.length === 0 ? undefined : this.data[0]
        }

部分测试代码

 heap.insert(4)
    heap.insert(5)
    heap.insert(1)
    heap.insert(2)
    heap.insert(3)

    console.log(heap)

    heap.insert(4)
    heap.insert(5)
    heap.insert(1)
    heap.insert(2)
    heap.insert(3)

    heap.extract()
    console.log(heap)

三、图(以最简单的无向无权图为例)

这可能是你见过最简单的图的实现方法

3.1 图的表示

来简单复习一下吧

邻接矩阵

采用一个二维矩阵

如图:(额找的这个图不太好,咋都有三个边啊)

顶点的存储方式好说,数组就可以。便就用这么一个矩阵,ab之间右边则记为1

再来简单说一下它的缺点:对于一个边极少(矩阵为稀疏矩阵)浪费空间

邻接表

邻接表可借助如图一个链表的方式存储每个顶点的边

也来简单说一下它的缺点:对于有向图的入边表示不了

3.2 图的实现

我们这里不使用链表表示边的情况了,为了简单。我们就使用一个对象

如顶点A相邻的顶点有B,C,D

我们就这样表示{"A":["B","C","D"]}

图的表示采有邻接表

 class Graph {
        constructor() {
            this.vertexes = []//顶点
            this.edges = {}//记录边
            this.statu = {}//顶点状态
        }
 }

加入顶点

  addVertexe(v) {
            this.vertexes.push(v)
            this.edges[v] = []
        }

加入边

   addEdges(v1, v2) {
            this.edges[v1].push(v2)
            this.edges[v2].push(v1)
        }

3.3 图的遍历

记录状态

 _initStatu() {
            this.vertexes.forEach(item => {
                this.statu[item] = 1
            })
        }

bfs需要借助队列,把上次写好的队列拿过来

 class Queue {
        constructor() {
            this._data = {}
            this._count = 0
            this._first = 0 //队头指针
        }
        isEmpty() {
            return this._count === this._first
        }
        enqueue(value) {
            this._data[this._count++] = value
        }
        dequeue() {
            if (this.isEmpty()) {
                return undefined
            }
            let res = this._data[this._first]
            delete this._data[this._first]
            this._first++;
            return res

        }
        peek() {
            if (this.isEmpty()) {
                return undefined
            }
            return this._data[this._first]
        }
        size() {
            return this._count - this._first
        }
        clean() {
            this._data = {}
            this._count = 0
            this._first = 0
        }
    }

广度优先搜索

哈哈,我又搞了个图。来举个栗子吧

bfs,人如其名,以广度为先

比如上图我们从a开始,与a相连的为g,e,b。依次访问到之后回到g处,与g相连的有f(重复的a我们不在要一遍了);在到e处,与e相连的暂时没有了(ab重复);再到b处,与b相连的有c...就这样一直搞下去直到把所有的顶点访问一遍(如果写过二叉树的层次遍历你会感觉他们非常相像,借用队列呗)

怎么记录一顶点访问过没有呢

这就用到顶点状态了。

如开始顶点的状态为1,访问过它之后就把它的状态设置为2,有时候我们还会传进去一个函数用于处理这个顶点,那么处理过的就设置为3

实现(注意下面的测试栗子不是上图中的啊,原来练习写的测试栗子,这个测试的栗子代码有点长和恶心就没有改动)

 bfs(v, fn) {
            // 初始化状态
            this._initStatu()
            const q = new Queue()
            q.enqueue(v)

            while (!q.isEmpty()) {
                let current = q.dequeue()

                // 将当前顶点状态设为2
                this.statu[current] = 2

                // 取与当前顶点相连的入队
                this.edges[current].forEach(item => {
                    if (this.statu[item] == 1) {
                        this.statu[item] = 2
                        q.enqueue(item)
                    }
                })

                // 访问出队的顶点(即操作它)
                fn(current)
                this.statu[current] = 3
            }
        }

测试代码

 const g = new Graph();
    ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(item => g.addVertexe(item))

    g.addEdges('A', 'B')
    g.addEdges('A', 'C')
    g.addEdges('A', 'D')
    g.addEdges('C', 'D')
    g.addEdges('C', 'G')
    g.addEdges('D', 'G')
    g.addEdges('D', 'H')
    g.addEdges('B', 'E')
    g.addEdges('B', 'F')
    g.addEdges('E', 'I')
    console.log(g)
    g.bfs('A', function(v) {
            console.log(v)
        })

深度优先搜索

dfs同样人如其名,还是用上面这个图举个栗子,还是从a开始

a找到了g,从g找到了f,从f(先选一条路)找到了h,从h找到了i到头了回去

回到f,进去另一条路,找到了e,找到了b,找到了c找到了d,又到头回去。这回中间没有可走的岔路了,故直接到了起始a,通过a又找到了e

完了,最简单的思路就是递归了

实现

  dfs(v, fn) {
            // 初始化状态
            this._initStatu()
            this._dfsVisit(v, fn)

        }
        _dfsVisit(v, fn) {
            this.statu[v] = 2
            fn(v)

            // 拿与其相邻的顶点
            this.edges[v].forEach(item => {
                if (this.statu[item] === 1) {
                    this._dfsVisit(item, fn)
                }
            })
            this.statu[v] = 3
        }
    }

测试代码

 const g = new Graph();
    ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(item => g.addVertexe(item))

    g.addEdges('A', 'B')
    g.addEdges('A', 'C')
    g.addEdges('A', 'D')
    g.addEdges('C', 'D')
    g.addEdges('C', 'G')
    g.addEdges('D', 'G')
    g.addEdges('D', 'H')
    g.addEdges('B', 'E')
    g.addEdges('B', 'F')
    g.addEdges('E', 'I')
    console.log(g)
    g.dfs('A', function(v) {
            console.log(v)
        })

参考书籍

王道考研数据结构

严奶奶的那本(数据结构(C语言版) 第2版 (严蔚敏等))

学习js数据结构与算法

写到最后

小白原来的笔记链接(有一些错误没有进行更改)

AVL以及红黑树就留到以后有时间写吧

星光不问赶路人,时光不负有心人 期待着我们的下一次邂逅