18 张图带你彻底认识这些数据结构

曾经终败给现在 2022-04-24 05:46 255阅读 0赞

640?wx\_fmt=jpeg

作者 | 嘉明

来源 | https://github.com/reng99/blogs

数据结构是计算机存储、组织数据的方式。数据结构是指相互直接存在一种或多种特殊关系的数据元素的集合。通常情况下，精心选择数据结构可以带来更高的运行或者存储效率。作为一名程序猿，更需要了解下数据结构。

讲到数据结构，我们都会谈到线性结构和非线性结构。

1.线性结构是一个有序数据元素的集合。它应该满足下面的特征：

  • 集合中必存在唯一的一个“第一个元素”
  • 集合中必存在唯一的一个“最后的元素”
  • 除最后一元素之外，其它数据元素均有唯一的“后继”
  • 除第一个元素之外，其它数据元素均有唯一的“前驱”

按照百度百科的定义，我们知道符合条件的数据结构就有栈、队列和其它。

2.非线性结构其逻辑特征是一个节点元素可以有多个直接前驱或多个直接后继。

那么，符合条件的数据结构就有图、树和其它。

嗯～了解一下就行。我们进入正题：

数组

数组是一种线性结构，以十二生肖（鼠、牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪）排序为例：

640?wx\_fmt=png array_demo

我们来创建一个数组并打印出结果就一目了然了：

  1. let arr = ['鼠', '牛', '虎', '兔', '龙', '蛇', '马', '羊', '猴', '鸡', '狗', '猪'];
  2. arr.forEach((item, index) => {
  4.     console.log(`[ ${index} ] => ${item}`);
  5. });
  7. // [ 0 ] => 鼠
  8. // [ 1 ] => 牛
  9. // [ 2 ] => 虎
  10. // [ 3 ] => 兔
  11. // [ 4 ] => 龙
  12. // [ 5 ] => 蛇
  13. // [ 6 ] => 马
  14. // [ 7 ] => 羊
  15. // [ 8 ] => 猴
  16. // [ 9 ] => 鸡
  17. // [ 10 ] => 狗
  18. // [ 11 ] => 猪

栈

栈是一种后进先出(LIFO)线性表，是一种基于数组的数据结构。（ps：其实后面讲到的数据结构或多或少有数组的影子）

  • LIFO(Last In First Out)表示后进先出，后进来的元素第一个弹出栈空间。类似于自动餐托盘，最后放上去的托盘，往往先被拿出来使用。
  • 仅允许在表的一端进行插入和移除元素。这一端被称为栈顶，相对地，把另一端称为栈底。如下图的标识。
  • 向一个栈插入新元素称作进栈、入栈或压栈，这是将新元素放在栈顶元素上面，使之成为新的栈顶元素。
  • 从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

640?wx\_fmt=png stack_demo

我们代码写下，熟悉下栈：

  1. class Stack {
  3.     constructor(){
  5.         this.items = [];
  6.     }
  7.     // 入栈操作
  8.     push(element = ''){
  10.         if(!element) return;
  11.         this.items.push(element);
  12.         return this;
  13.     }
  14.     // 出栈操作
  15.     pop(){
  17.         this.items.pop();
  18.         return this;
  19.     }
  20.     // 对栈一瞥，理论上只能看到栈顶或者说即将处理的元素
  21.     peek(){
  23.         return this.items[this.size() - 1];
  24.     }
  25.     // 打印栈数据
  26.     print(){
  28.         return this.items.join(' ');
  29.     }
  30.     // 栈是否为空
  31.     isEmpty(){
  33.         return this.items.length == 0;
  34.     }
  35.     // 返回栈的元素个数
  36.     size(){
  38.         return this.items.length;
  39.     }
  40. }

⚠️ 注意：栈这里的push和pop方法要和数组方法的push和pop方法区分下。

队列

队列是一种先进先出（FIFO）受限的线性表。受限体现在于其允许在表的前端（front）进行删除操作，在表的末尾（rear）进行插入【优先队列这些排除在外】操作。

640?wx\_fmt=png

queue_demo

代码走一遍：

  1. class Queue {
  3.     constructor(){
  5.         this.items = [];
  6.     }
  7.     // 入队操作
  8.     enqueue(element = ''){
  10.         if(!element) return;
  11.         this.items.push(element);
  12.         return this;
  13.     }
  14.     // 出队操作
  15.     dequeue(){
  17.         this.items.shift();
  18.         return this;
  19.     }
  20.     // 查看队前元素或者说即将处理的元素
  21.     front(){
  23.         return this.items[0];
  24.     }
  25.     // 查看队列是否为空
  26.     isEmpty(){
  28.         return this.items.length == 0;
  29.     }
  30.     // 查看队列的长度
  31.     len(){
  33.         return this.items.length;
  34.     }
  35.     // 打印队列数据
  36.     print(){
  38.         return this.items.join(' ');
  39.     }
  40. }

链表

在进入正题之前，我们先来聊聊数组的优缺点。

优点：

  • 存储多个元素，比较常用
  • 访问便捷，使用下标[index]即可访问

缺点：

  • 数组的创建通常需要申请一段连续的内存空间，并且大小是固定的（大多数的编程语言数组都是固定的），所以在进行扩容的时候难以掌控。（一般情况下，申请一个更大的数组，会是之前数组的倍数，比如两倍。然后，再将原数组中的元素复制过去）
  • 插入数据越是靠前，其成本很高，因为需要进行大量元素的位移。

相对数组，链表亦可以存储多个元素，而且存储的元素在内容中不必是连续的空间；在插入和删除数据时，时间复杂度可以达到O(1)。在查找元素的时候，还是需要从头开始遍历的，比数组在知道下表的情况下要快，但是数组如果不确定下标的话，那就另说了…

我们使用十二生肖来了解下链表：

640?wx\_fmt=png linklist_demo

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。如上图。下面用代码实现下：

  1. // 链表
  2. class Node {
  4.     constructor(element){
  6.         this.element = element;
  7.         this.next = null;
  8.     }
  9. }
  11. class LinkedList {
  13.     constructor(){
  15.         this.length = 0; // 链表长度
  16.         this.head = new Node('head'); // 表头节点
  17.     }
  18.     /**
  19.      * @method find 查找元素的功能，找不到的情况下直接返回链尾节点
  20.      * @param { String } item 要查找的元素
  21.      * @return { Object } 返回查找到的节点 
  22.      */
  23.     find(item = ''){
  25.         let currNode = this.head;
  26.         while(currNode.element != item && currNode.next){
  28.             currNode = currNode.next;
  29.         }
  30.         return currNode;
  31.     }
  32.     /**
  33.     * @method findPrevious 查找链表指定元素的前一个节点
  34.     * @param { String } item 指定的元素
  35.     * @return { Object } 返回查找到的之前元素的前一个节点，找不到节点的话返回链尾节点
  36.     */
  37.     findPrevious(item){
  39.         let currNode = this.head;
  40.         while((currNode.next != null) && (currNode.next.element != item)){
  42.             currNode = currNode.next;
  43.         }
  44.         return currNode;
  45.     }
  46.     /**
  47.      * @method insert 插入功能
  48.      * @param { String } newElement 要出入的元素
  49.      * @param { String } item 想要追加在后的元素（此元素不一定存在）
  50.      */
  51.     insert(newElement = '', item){
  53.         if(!newElement) return;
  54.         let newNode = new Node(newElement),
  55.             currNode = this.find(item);
  56.         newNode.next = currNode.next;
  57.         currNode.next = newNode;
  58.         this.length++;
  59.         return this;
  60.     }
  61.     // 展示链表元素
  62.     display(){
  64.         let currNode = this.head,
  65.             arr = [];
  66.         while(currNode.next != null){
  68.             arr.push(currNode.next.element);
  69.             currNode = currNode.next;
  70.         }
  71.         return arr.join(' ');
  72.     }
  73.     // 链表的长度
  74.     size(){
  76.         return this.length;
  77.     }
  78.     // 查看链表是否为空
  79.     isEmpty(){
  81.         return this.length == 0;
  82.     }
  83.     /**
  84.      * @method indexOf 查看链表中元素的索引
  85.      * @param { String } element 要查找的元素
  86.      */
  87.     indexOf(element){
  89.         let currNode = this.head,
  90.             index = 0;
  91.         while(currNode.next != null){
  93.             index++;
  94.             if(currNode.next.element == element){
  96.                 return index;
  97.             }
  98.             currNode = currNode.next;
  99.         }
  100.         return -1;
  101.     }
  102.     /**
  103.      * @method removeEl 移除指定的元素
  104.      * @param { String } element 
  105.      */
  106.     removeEl(element){
  108.         let preNode = this.findPrevious(element);
  109.         preNode.next = preNode.next != null ? preNode.next.next : null;
  110.     }
  111. }

字典

字典的主要特点是键值一一对应的关系。可以比喻成我们现实学习中查不同语言翻译的字典。这里字典的键（key）理论上是可以使用任意的内容，但还是建议语意化一点，比如下面的十二生肖图：

640?wx\_fmt=png dictionary_demo

  1. class Dictionary {
  3.     constructor(){
  5.         this.items = {};
  6.     }
  7.     /**
  8.      * @method set 设置字典的键值对
  9.      * @param { String } key 键
  10.      * @param {*} value 值
  11.      */
  12.     set(key = '', value = ''){
  14.         this.items[key] = value;
  15.         return this;
  16.     }
  17.     /**
  18.      * @method get 获取某个值
  19.      * @param { String } key 键
  20.      */
  21.     get(key = ''){
  23.         return this.has(key) ? this.items[key] : undefined;
  24.     }
  25.     /**
  26.      * @method has 判断是否含有某个键的值
  27.      * @param { String } key 键
  28.      */
  29.     has(key = ''){
  31.         return this.items.hasOwnProperty(key);
  32.     }
  33.     /**
  34.      * @method remove 移除元素
  35.      * @param { String } key 
  36.      */
  37.     remove(key){
  39.         if(!this.has(key))  return false;
  40.         delete this.items[key];
  41.         return true;
  42.     }
  43.     // 展示字典的键
  44.     keys(){
  46.         return Object.keys(this.items).join(' ');
  47.     }
  48.     // 字典的大小
  49.     size(){
  51.         return Object.keys(this.items).length;
  52.     }
  53.     // 展示字典的值
  54.     values(){
  56.         return Object.values(this.items).join(' ');
  57.     }
  58.     // 清空字典
  59.     clear(){
  61.         this.items = {};
  62.         return this;
  63.     }
  64. }

集合

集合通常是由一组无序的，不能重复的元素构成。 一些常见的集合操作如图：

640?wx\_fmt=png set_demo
es6中已经封装好了可用的Set类。我们手动来写下相关的逻辑：

  1. // 集合
  2. class Set {
  4.     constructor(){
  6.         this.items = [];
  7.     }
  8.     /**
  9.      * @method add 添加元素
  10.      * @param { String } element 
  11.      * @return { Boolean }
  12.      */
  13.     add(element = ''){
  15.         if(this.items.indexOf(element) >= 0) return false;
  16.         this.items.push(element);
  17.         return true;
  18.     }
  19.     // 集合的大小
  20.     size(){
  22.         return this.items.length;
  23.     }
  24.     // 集合是否包含某指定元素
  25.     has(element = ''){
  27.         return this.items.indexOf(element) >= 0;
  28.     }
  29.     // 展示集合
  30.     show(){
  32.         return this.items.join(' ');
  33.     }
  34.     // 移除某个元素
  35.     remove(element){
  37.         let pos = this.items.indexOf(element);
  38.         if(pos < 0) return false;
  39.         this.items.splice(pos, 1);
  40.         return true;
  41.     }
  42.     /**
  43.      * @method union 并集
  44.      * @param { Array } set 数组集合
  45.      * @return { Object } 返回并集的对象
  46.      */
  47.     union(set = []){
  49.         let tempSet = new Set();
  50.         for(let i = 0; i < this.items.length; i++){
  52.             tempSet.add(this.items[i]);
  53.         }
  54.         for(let i = 0; i < set.items.length; i++){
  56.             if(tempSet.has(set.items[i])) continue;
  57.             tempSet.items.push(set.items[i]);
  58.         }
  59.         return tempSet;
  60.     }
  61.     /**
  62.      * @method intersect 交集
  63.      * @param { Array } set 数组集合
  64.      * @return { Object } 返回交集的对象
  65.      */
  66.     intersect(set = []){
  68.         let tempSet = new Set();
  69.         for(let i = 0; i < this.items.length; i++){
  71.             if(set.has(this.items[i])){
  73.                 tempSet.add(this.items[i]);
  74.             }
  75.         }
  76.         return tempSet;
  77.     }
  78.     /**
  79.      * @method isSubsetOf 【A】是【B】的子集❓
  80.      * @param { Array } set 数组集合
  81.      * @return { Boolean } 返回真假值
  82.      */
  83.     isSubsetOf(set = []){
  85.         if(this.size() > set.size()) return false;
  86.         this.items.forEach*(item => {
  88.             if(!set.has(item)) return false;
  89.         });
  90.         return true;
  91.     }
  92. }

散列表/哈希表

散列是一种常用的存储技术，散列使用的数据结构叫做散列表/哈希表。在散列表上插入、删除和取用数据都非常快，但是对于查找操作来说却效率低下，比如查找一组数据中的最大值和最小值。查找的这些操作得求助其它数据结构，比如下面要讲的二叉树。

切入个案例感受下哈希表：

假如一家公司有1000个员工, 现在我们需要将这些员工的信息使用某种数据结构来保存起来。你会采用什么数据结构呢？

  • 方案一：数组
  • 按照顺序将所有员工信息依次存入一个长度为1000的数组中。每个员工的信息都保存在该数组的某个位置上。
  • 但是我们要查看某个员工的信息怎么办呢？一个个查找吗？不太好找。
  • 数组最大的优势是什么？通过下标值获取信息。
  • 所以为了可以通过数组快速定位到某个员工，最好给员工信息中添加一个员工编号，而编号对应的就是员工的下标值。
  • 当查找某个员工信息时，通过员工号可以快速定位到员工的信息位置。
  • 方案二：链表
  • 链表对应插入和删除数据有一定的优势。
  • 但是对于获取员工的信息，每次都必须从头遍历到尾，这种方式显然不是特别适合我们这里。
  • 最终方案：
  • 这么看最终方案似乎就是数组了，但是数组还是有缺点，什么缺点呢？
  • 假如我们想查看下张三这位员工的信息，但是我们不知道张三的员工编号，怎么办呢？
  • 当然，我们可以问他的员工编号。但是我们每查找一个员工都是要问一下这个员工的编号吗？不合适。【那我们还不如直接问他的信息嘞】
  • 能不能有一种办法，让张三的名字和他的员工编号产生直接的关系呢？
  • 也就是通过张三这个名字，我们就能获取到他的索引值，而再通过索引值我们就能获取张三的信息呢？
  • 这样的方案已经存在了，就是使用哈希函数，让某个key的信息和索引值对应起来。

那么散列表的原理和实现又是怎样的呢，我们来聊聊。

我们的哈希表是基于数组完成的，我们从数组这里切入解析下。数组可以通过下标直接定位到相应的空间，哈希表的做法就是类似的实现。哈希表把key(键)通过一个固定的算法函数（此函数称为哈希函数/散列函数）转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value(值)存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value。

结合下面的代码，也许你会更容易理解：

  1. // 哈希表
  2. class HashTable {
  4.     constructor(){
  6.         this.table = new Array(137);
  7.     }
  8.     /**
  9.      * @method hashFn 哈希函数
  10.      * @param { String } data 传入的字符串
  11.      * @return { Number } 返回取余的数字
  12.      */
  13.     hashFn(data){
  15.         let total = 0;
  16.         for(let i = 0; i < data.length; i++){
  18.             total += data.charCodeAt(i);
  19.         }
  20.         return total % this.table.length;
  21.     }
  22.     /**
  23.      * 
  24.      * @param { String } data 传入的字符串
  25.      */
  26.     put(data){
  28.         let pos = this.hashFn(data);
  29.         this.table[pos] = data;
  30.         return this;
  31.     }
  32.     // 展示
  33.     show(){
  35.         this.table && this.table.forEach((item, index) => {
  37.             if(item != undefined){
  39.                 console.log(index + ' => ' + item);
  40.             }
  41.         })
  42.     }
  43.     // ...获取值get函数等看官感兴趣的话自己补充测试啦
  44. }

640?wx\_fmt=png

hashtable_demo

针对上面的问题，我们存储数据的时候，产生冲突的话我们可以像下面这样解决：

1. 线性探测法

当发生碰撞（冲突）时，线性探测法检查散列表中的下一个位置【有可能非顺序查找位置，不一定是下一个位置】是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。该技术是基于一个事实：每个散列表都有很多空的单元格，可以使用它们存储数据。

2. 开链法

但是，当发生碰撞时，我们任然希望将key（键）存储到通过哈希函数产生的索引位置上，那么我们可以使用开链法。开链法是指实现哈希表底层的数组中，每个数组元素又是一个新的数据结构，比如另一个数组（这样结合起来就是二位数组了），链表等，这样就能存储多个键了。使用这种技术，即使两个key（键）散列后的值相同，依然是被保存在同样的位置，只不过它们是被保存在另一个数据结构上而已。以另一个数据结构是数组为例，存储的数据如下：

640?wx\_fmt=png open_link_method

二叉查找树

  • 树的定义：

  • 树（Tree）：n(n >= 0)个节点构成的有限集合。

    • 当`n = 0`时，称为空树；
    • 对任意一棵空树`(n > 0)`，它具备以下性质：
    • 树中有一个称为根(Root)的特殊节点，用`r(root)`表示；
    • 其余节点可分为`m(m > 0)`个互不相交的有限集`T1,T2,…Tm`，其中每个集合本省又是一棵树，称为原来树的子树（SubTree）

  • 注意：

    • 子树之间`不可以相交`；
    • 除了根节点外，每个节点有且仅有一个父节点；
    • 一个`N`个节点的树有`N-1`条边。
  • 树的术语：
  • 节点的度（Degree）：节点的子树个数。
  • 树的度：树的所有节点中最大的度数（树的度通常为节点个数的N-1）。
  • 叶节点（Leaf）：度为0的节点（也称叶子节点）。
  • 父节点（Parent）：有子树的节点是其子树的父节点。
  • 子节点（Child）：若A节点是B节点的父节点，则称B节点是A节点的子节点。
  • 兄弟节点（Sibling）：具有同一个父节点的各节点彼此是兄弟节点。
  • 路径和路径长度：从节点n1到nk的路径为一个节点序列n1,n2,n3,…,nk，ni是ni+1的父节点。路径所包含边的个数为路径长度。
  • 节点的层次（Level）：规定根节点在第0层，它的子节点是第1层，子节点的子节点是第2层，以此类推。
  • 树的深度（Depth）：树中所有节点中的最大层次是这棵树的深度（因为上面是从第0层开始，深度 = 第最大层数 + 1）

如下图：

640?wx\_fmt=png tree_intro

  • 二叉树的定义：
  • 二叉树可以为空，也就是没有节点
  • 二叉树若不为空，则它是由根节点和称为其左子树TL和右子树RT的两个不相交的二叉树组成
  • 二叉树每个节点的子节点不允许超过两个
  • 二叉树的五种形态：
  • 空
  • 只有根节点
  • 只有左子树
  • 只有右子树
  • 左右子树均有

对应下图（从左至右）：

640?wx\_fmt=png five_style_binary_tree

我们接下来要讲的是二叉查找树（BST，Binary Search Tree）。二叉查找树，也称二叉搜索树或二叉排序树，是一种特殊的二叉树，相对值较小的值保存在左节点中，较大的值保存在右节点中。二叉查找树特殊的结构使它能够快速的进行查找、插入和删除数据。下面我们来实现下：

  1. // 二叉查找树
  2. // 辅助节点类
  3. class Node {
  5.     constructor(data, left, right){
  7.         this.data = data;
  8.         this.left = left;
  9.         this.right = right;
  10.     }
  11.     // 展示节点信息
  12.     show(){
  14.         return this.data;
  15.     }
  16. }
  17. class BST {
  19.     constructor(){
  21.         this.root = null;
  22.     }
  23.     // 插入数据
  24.     insert(data){
  26.         let n = new Node(data, null, null);
  27.         if(this.root == null){
  29.             this.root = n;
  30.         }else{
  32.             let current = this.root,
  33.                 parent = null;
  34.             while(true){
  36.                 parent = current;
  37.                 if(data < current.data){
  39.                     current = current.left;
  40.                     if(current == null){
  42.                         parent.left = n;
  43.                         break;
  44.                     }
  45.                 }else{
  47.                     current = current.right;
  48.                     if(current == null){
  50.                         parent.right = n;
  51.                         break;
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.         return this;
  57.     }
  58.     // 中序遍历
  59.     inOrder(node){
  61.         if(!(node == null)){
  63.             this.inOrder(node.left);
  64.             console.log(node.show());
  65.             this.inOrder(node.right);
  66.         }
  67.     }
  68.     //   先序遍历
  69.     preOrder(node){
  71.         if(!(node == null)){
  73.             console.log(node.show());
  74.             this.preOrder(node.left);
  75.             this.preOrder(node.right);
  76.         }
  77.     }
  78.     // 后序遍历
  79.     postOrder(node){
  81.         if(!(node == null)){
  83.             this.postOrder(node.left);
  84.             this.postOrder(node.right);
  85.             console.log(node.show());
  86.         }
  87.     }
  88.     // 获取最小值
  89.     getMin(){
  91.         let current = this.root;
  92.         while(!(current.left == null)){
  94.             current = current.left;
  95.         }
  96.         return current.data;
  97.     }
  98.     // 获取最大值
  99.     getMax(){
  101.         let current = this.root;
  102.         while(!(current.right == null)){
  104.             current = current.right;
  105.         }
  106.         return current.data;
  107.     }
  108.     // 查找给定的值
  109.     find(data){
  111.         let current = this.root;
  112.         while(current != null){
  114.             if(current.data == data){
  116.                 return current;
  117.             }else if(data < current.data){
  119.                 current = current.left;
  120.             }else{
  122.                 current = current.right;
  123.             }
  124.         }
  125.         return null;
  126.     }
  127.     // 移除给定的值
  128.     remove(data){
  130.         root = this.removeNode(this.root, data);
  131.         return this;
  132.     }
  133.     // 移除给定值的辅助函数
  134.     removeNode(node, data){
  136.         if(node == null){
  138.             return null;
  139.         }
  140.         if(data == node.data){
  142.             // 叶子节点
  143.             if(node.left == null && node.right == null){
  145.                 return null; // 此节点置空
  146.             }
  147.             // 没有左子树
  148.             if(node.left == null){
  150.                 return node.right;
  151.             }
  152.             // 没有右子树
  153.             if(node.right == null){
  155.                 return node.left;
  156.             }
  157.             // 有两个子节点的情况
  158.             let tempNode = this.getSmallest(node.right); // 获取右子树
  159.             node.data = tempNode.data; // 将其右子树的最小值赋值给删除的那个节点值
  160.             node.right = this.removeNode(node.right, tempNode.data); // 删除指定节点的下的最小值，也就是置其为空
  161.             return node;
  162.         }else if(data < node.data){
  164.             node.left = this.removeNode(node.left, data);
  165.             return node;
  166.         }else{
  168.             node.right = this.removeNode(node.right, data);
  169.             return node;
  170.         }
  171.     }
  172.     // 获取给定节点下的二叉树最小值的辅助函数
  173.     getSmallest(node){
  175.         if(node.left == null){
  177.             return node;
  178.         }else{
  180.             return this.getSmallest(node.left);
  181.         }
  182.     }
  183. }

看了上面的代码之后，你是否有些懵圈呢？我们借助几张图来了解下，或许你就豁然开朗了。

在遍历的时候，我们分为三种遍历方法—先序遍历，中序遍历和后序遍历：

640?wx\_fmt=png travel_tree

删除节点是一个比较复杂的操作，考虑的情况比较多：

  • 该节点没有叶子节点的时候，直接将该节点置空；
  • 该节点只有左子树，直接将该节点赋予左子树
  • 该节点只有右子树，直接将该节点赋予右子树
  • 该节点左右子树都有，有两种方法可以处理
  • 方案一：从待删除节点的左子树找节点值最大的节点A，替换待删除节点值，并删除节点A
  • 方案二：从待删除节点的右子树找节点值最小的节点A，替换待删除节点值，并删除节点A【?上面的示例代码中就是这种方案】

删除两个节点的图解如下：

640?wx\_fmt=png

remove_tree_node

图

图由边的集合及顶点的集合组成。

我们来了解下图的相关术语：

  • 顶点：图中的一个节点。
  • 边：表示顶点和顶点之间的连线。
  • 相邻顶点：由一条边连接在一起的顶点称为相邻顶点。
  • 度：一个顶点的度是相邻顶点的数量。比如0顶点和其它两个顶点相连，0顶点的度就是2

  • 路径：路径是顶点

    1. v1,v2...,vn

    的一个连续序列。

  • 简单路径：简单路径要求不包含重复的顶点。
  • 回路：第一个顶点和最后一个顶点相同的路径称为回路。
  • 有向图和无向图
  • 有向图表示图中的边是有方向的。
  • 无向图表示图中的边是无方向的。
  • 带权图和无权图
  • 带权图表示图中的边有权重。
  • 无权图表示图中的边无权重。

如下图：

640?wx\_fmt=png

graph_concept_intro

图可以用于现实中的很多系统建模，比如：

  • 对交通流量建模
  • 顶点可以表示街道的十字路口, 边可以表示街道.
  • 加权的边可以表示限速或者车道的数量或者街道的距离.
  • 建模人员可以用这个系统来判定最佳路线以及最可能堵车的街道.

图既然这么方便，我们来用代码实现下：

  1. // 图
  2. class Graph{
  4.     constructor(v){
  6.         this.vertices = v; // 顶点个数
  7.         this.edges = 0; // 边的个数
  8.         this.adj = []; // 邻接表或邻接表数组
  9.         this.marked = []; // 存储顶点是否被访问过的标识
  10.         this.init();
  11.     }
  12.     init(){
  14.         for(let i = 0; i < this.vertices; i++){
  16.             this.adj[i] = [];
  17.             this.marked[i] = false;
  18.         }
  19.     }
  20.     // 添加边
  21.     addEdge(v, w){
  23.         this.adj[v].push(w);
  24.         this.adj[w].push(v);
  25.         this.edges++;
  26.         return this;
  27.     }
  28.     // 展示图
  29.     showGraph(){
  31.         for(let i = 0; i < this.vertices; i++){
  33.             for(let j = 0; j < this.vertices; j++){
  35.                 if(this.adj[i][j] != undefined){
  37.                     console.log(i +' => ' + this.adj[i][j]);
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     // 深度优先搜索
  43.     dfs(v){
  45.         this.marked[v] = true;
  46.         if(this.adj[v] != undefined){
  48.             console.log("visited vertex: " + v);
  49.         }
  50.         this.adj[v].forEach(w => {
  52.             if(!this.marked[w]){
  54.                 this.dfs(w);
  55.             }
  56.         })
  57.     }
  58.     // 广度优先搜索
  59.     bfs(v){
  61.         let queue = [];
  62.         this.marked[v] = true;
  63.         queue.push(v); // 添加到队尾
  64.         while(queue.length > 0){
  66.             let v = queue.shift(); // 从对首移除
  67.             if(v != undefined){
  69.                 console.log("visited vertex: " + v);
  70.             }
  71.             this.adj[v].forEach(w => {
  73.                 if(!this.marked[w]){
  75.                     this.marked[w] = true;
  76.                     queue.push(w);
  77.                 }
  78.             })
  79.         }
  80.     }
  81. }

对于搜索图，在上面我们介绍了深度优先搜索 - DFS（Depth First Search）和广度优先搜索 - BFS（Breadth First Search），结合下面的图再回头看下上面的代码，你会更加容易理解这两种搜索图的方式。

640?wx\_fmt=png graph_search

推荐阅读

拜托，面试官别问我「布隆」了

数据结构与算法： 三十张图弄懂「图的两种遍历方式」

昨天，终于拿到了腾讯 offer

几道和「二叉树」有关的算法面试题

几道和散列（哈希）表有关的面试题

一道看完答案你会觉得很沙雕的「动态规划算法题」

几道和「堆栈、队列」有关的面试算法题

链表算法面试问题？看我就够了！

640?wx\_fmt=jpeg

欢迎关注640?wx\_fmt=png

640戳 “阅读原文”前往小吴的个人博客一起充电学习!

发表评论

表情：
评论列表 （有 0 条评论，255人围观）

还没有评论，来说两句吧...

相关阅读

    相关 30张图带你彻底理解红黑树

    本文转自安卓大叔 写在前面 当在10亿数据中只需要进行10几次比较就能查找到目标时，不禁感叹编程之魅力！人类之伟大呀！ —— 学红黑树有感。 终于，在学习了几天的红黑

    傷城~傷城~/ 0 赞/ 352 阅读