devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构在JavaScript中的体现

作者：Monodyee | 2024-02-16 03:46:26

赞

踩

数据结构在JavaScript中的体现

一.概述

        数据结构是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法，其实算法并不是一个很高级的东西，它充斥在每一种代码组织方式中；而且各种语言关于数据结构方面的内容都是大同小异的，会了一种语言的数据结构方面的内容就可以快速掌握其它语言的的数据结构；有一部分人对JavaScript有偏见，觉得这种语言没有档次，但又有多少人在学完JavaScript敢说精通它。

二.见识数据结构

(1)>>数组

        你没有看错，常见的数组就是一种数据结构，对于数组就是掌握一下它的各种方法，如push(),pop(),shift(),unshift(),indexOf(),sort(),slice(),splice()等，在这里就不赘述了。

(2)>>栈

 A.图解

               遵循的是后进先出

  B.封装代码 

  1. class Stack {
  2.     //加#是为了保证其是私有属性,不让外界随意调用
  3.     #items = [];
  4.     pop() {
  5.         return this.#items.pop()
  6.     }
  7.     push(data) {
  8.         return this.#items.push(data)
  9.     }
  10.     //返回栈顶
  11.     peek() {
  12.         return this.#items.at(-1)
  13.     }
  14.     isEmpty() {
  15.         return this.#items.length > 0 ? false : true
  16.     }
  17.     size() {
  18.         return this.#items.length
  19.     }
  20.     clear() {
  21.         this.#items = []
  22.     }
  23.     toString(){
  24.         return this.#items.join(' ')
  25.     }
  26. }

C.应用场景

        将十进制数转换为其它进制的数时用到了辗转相除法，刚好是把得到的余数从后到前输出得到对应进制下的数，如果把这些数从前到后推到栈里，再取出来岂不妙哉。

  1. function convert(decNumber, binaryNumber) {
  2.     let number = decNumber
  3.     let stack = new Stack()
  4.     let string = ''
  5.     //防止转换成十六进制的时候乱码
  6.     let baseString = '0123456789ABCDEF'
  7.     while (number > 0) {
  8.         stack.push(number % binaryNumber)
  9.         number = Math.floor(number / binaryNumber)
  10.     }
  11.     while (!(stack.isEmpty())) {
  12.         string += baseString[stack.pop()]
  13.     }
  14.     return string
  15. }
  16.  
  17. console.log(convert(50, 2));

(3)>>队列

 A.图解

        先进先出，后端进，前端出，类似于排队

 B.封装代码

             有缺点的封装方式
  1. class Queue {
  2.     #items = [];
  3.     //一旦元素变多，还用shift会造成运行效率低
  4.     deleteQueue() {
  5.         return this.#items.shift()
  6.     }
  7.     enterQueue(data) {
  8.         return this.#items.push(data)
  9.     }
  10.     //返回队头
  11.     frontQueue() {
  12.         return this.#items.at(0)
  13.     }
  14.     isEmpty() {
  15.         return this.#items.length > 0 ? false : true
  16.     }
  17.     size() {
  18.         return this.#items.length
  19.     }
  20.     clear() {
  21.         this.#items = []
  22.     }
  23.     toString() {
  24.         return this.#items.join(' ')
  25.     }
  26. }
        修正之后的封装方式 
  1. class Queue {
  2.     #items = {};
  3.     #count = 0;
  4.     #lowCount = 0;
  5.     //出队
  6.     deleteQueue() {
  7.         if (this.isEmpty()) {
  8.             return undefined
  9.         }
  10.         let res = this.#items[this.#lowCount]
  11.         delete this.#items[this.#lowCount]
  12.         this.#lowCount++
  13.         return res
  14.     }
  15.     //进队
  16.     enterQueue(data) {
  17.         this.#items[this.#count] = data
  18.         this.#count++
  19.     }
  20.     //返回队头
  21.     frontQueue() {
  22.         return this.#items[this.#lowCount]
  23.     }
  24.     isEmpty() {
  25.         return this.size === 0
  26.     }
  27.     size() {
  28.         return this.#count - this.#lowCount
  29.     }
  30.     clear() {
  31.         this.#items = {}
  32.         this.#count = 0
  33.         this.#lowCount = 0
  34.     }
  35.     toString() {
  36.         let str = ""
  37.         for (let i = this.#lowCount; i < this.#count; i++) {
  38.             str += `${this.#items[i]} `
  39.         }
  40.         return str.trim()
  41.     }
  42. }

C.应用场景 

类似于击鼓传花，传指定次数，最终东西在谁手上谁淘汰，一直淘汰到队列里只剩一个人为最终的胜者

  1. function game(list, num) {
  2.     let queue = new Queue()
  3.     for (let i = 0; i < list.length; i++) {
  4.         queue.enterQueue(list[i])
  5.     }
  6.     while (queue.size() > 1) {
  7.         for (i = 0; i < num; i++) {
  8.             queue.enterQueue(queue.deleteQueue())
  9.         }
  10.         console.log(queue.deleteQueue(), '淘汰');
  11.     }
  12.     console.log(queue.deleteQueue());
  13.     //最终获胜者
  14.     return queue.deleteQueue()
  15. }
  16.  
  17. game(['aks', 'uej', 'jsm', 'duj', 'llq'], 7)

D.双端队列

与一般的队列有所不同的情况是，可以从队头进队，队尾可以出队，简而言之就是两端都能进出队伍。

  1. class DeQueue {
  2.     #items = {};
  3.     #count = 0;
  4.     #lowCount = 0;
  5.     removeFront() {
  6.         if (this.isEmpty()) {
  7.             return undefined
  8.         }
  9.         let res = this.#items[this.#lowCount]
  10.         delete this.#items[this.#lowCount]
  11.         this.#lowCount++
  12.         return res
  13.     }
  14.     addBack(data) {
  15.         this.#items[this.#count] = data
  16.         this.#count++
  17.     }
  18.     //在队头添加
  19.     addFront(data) {
  20.         if (this.isEmpty()) {
  21.             this.addBack()
  22.         } else {
  23.             if (this.#lowCount > 0) {
  24.                 this.#lowCount--
  25.                 this.#items[this.#lowCount] = data
  26.             } else {
  27.                 for (let i = this.#count; i > 0; i--) {
  28.                     this.#items[i] = this.#items[i - 1]
  29.                 }
  30.                 this.#items[0] = data
  31.                 this.#count++
  32.             }
  33.         }
  34.  
  35.     }
  36.     //在队尾删除
  37.     removeBack() {
  38.         if (this.isEmpty()) {
  39.             return
  40.         } else {
  41.             this.#count--
  42.             let res = this.#items[this.#count]
  43.             delete this.#items[this.#count]
  44.             return res
  45.         }
  46.     }
  47.     //返回队头
  48.     peekFront() {
  49.         return this.#items[this.#lowCount]
  50.     }
  51.     //返回队尾
  52.     peekBack() {
  53.         return this.#items.at(-1)
  54.     }
  55.     isEmpty() {
  56.         return this.size === 0
  57.     }
  58.     size() {
  59.         return this.#count - this.#lowCount
  60.     }
  61.     clear() {
  62.         this.#items = {}
  63.         this.#count = 0
  64.         this.#lowCount = 0
  65.     }
  66.     toString() {
  67.         let str = ""
  68.         for (let i = this.#lowCount; i < this.#count; i++) {
  69.             str += `${this.#items[i]} `
  70.         }
  71.         return str.trim()
  72.     }
  73. }
  74.  
  75.  
  76. //回文应用
  77. function test(str) {
  78.     //将输入有空格的字符串转化为无空格的
  79.     const lowStr = str.toLocaleLowerCase().split(' ').join('') 
  80.     let dequeue = new DeQueue()
  81.     for (let i = 0; i < lowStr.length; i++) {
  82.         dequeue.addBack(lowStr[i])
  83.     }
  84.     while (dequeue.size() > 1) {
  85.         if (dequeue.removeFront() !== dequeue.removeBack()) {
  86.             console.log('不是回文');
  87.             break
  88.         } else {
  89.             console.log('是回文结构');
  90.         }
  91.     }
  92. }
  93.  
  94. test('dadadb') //不是回文

(4)>>链表

1.单链表

A.图解

        可以把next看成一个指针，其能指向表中下一个存储的数据

B.封装代码
  1. //根据节点的需要创建相应的元素
  2. class Node {
  3.     constructor(element) {
  4.         this.element = element
  5.         this.next = null
  6.     }
  7. }
  8. //单链表
  9. class LinkList {
  10.     constructor() {
  11.         this.head = null
  12.         this.count = 0
  13.     }
  14.     //从表尾放入新节点
  15.     push(element) {
  16.         const node = new Node(element)
  17.         if (this.head === null) {
  18.             this.head = node
  19.         } else {
  20.             let current = this.head
  21.             while (current.next != null) {
  22.                 current = current.next
  23.             }
  24.             current.next = node
  25.         }
  26.         this.count++
  27.     }
  28.  
  29.     size() {
  30.         return this.count
  31.     }
  32.  
  33.     isEmpty() {
  34.         return this.size() === 0
  35.     }
  36.  
  37.     //指定位置删除
  38.     removeAt(index) {
  39.         if (index >= 0 && index < this.count) {
  40.             let current = this.head
  41.             if (index === 0) {
  42.                 this.head = this.head.next
  43.             } else {
  44.                 let previous
  45.                 for (let i = 0; i < index; i++) {
  46.                     previous = current
  47.                     current = current.next
  48.                 }
  49.                 previous.next = current.next
  50.             }
  51.             this.count--
  52.             return current.element
  53.         }
  54.         return undefined
  55.     }
  56.     //同样也是指定位置删除，但用到了后面封装的getNodeAt方法
  57.     removeAt2(index) {
  58.         if (index >= 0 && index < this.count) {
  59.             let current = this.head
  60.             if (index === 0) {
  61.                 this.head = this.head.next
  62.             } else {
  63.                 let previous = this.getNodeAt(index - 1)
  64.                 current = previous.next
  65.                 previous.next = current.next
  66.             }
  67.             this.count--
  68.             return current.element
  69.         }
  70.         return undefined
  71.     }
  72.     //根据索引值找到相应的节点
  73.     getNodeAt(index) {
  74.         if (index >= 0 && index < this.count) {
  75.             let node = this.head
  76.             for (let i = 0; i < index; i++) {
  77.                 node = node.next
  78.             }
  79.             return node
  80.         }
  81.         return undefined
  82.     }
  83.  
  84.  
  85.     indexOf(element) {
  86.         let current = this.head
  87.         for (let i = 0; i < this.count; i++) {
  88.             //防止其直接输入一个对象变量
  89.             if (JSON.stringify(element) === JSON.stringify(current.element)) {
  90.                 return i
  91.             }
  92.             current = current.next
  93.         }
  94.         return -1
  95.     }
  96.     //指定元素删除
  97.     remove(element) {
  98.         let index = this.indexOf(element)
  99.         let removeElement = this.removeAt(index)
  100.         return removeElement
  101.     }
  102.  
  103.     insert(element, index) {
  104.         if (index >= 0 && index <= this.count) {
  105.             const node = new Node(element)
  106.             if (index === 0) {
  107.                 let current = this.head
  108.                 node.next = current
  109.                 this.head = node
  110.                 this.count++
  111.             } else {
  112.                 let previous = this.getNodeAt(index - 1)
  113.                 let current = previous.next
  114.                 previous.next = node
  115.                 node.next = current
  116.                 this.count++
  117.             }
  118.             return true
  119.         }
  120.         return false
  121.     }
  122. }

2.双向链表

A.图解        

节点除了存储数据以外，还有两个指针分别指向前一个节点地址（prev）和下一个节点地址（next） 

B.封装代码
  1. //前人栽树，后人乘凉，继承自之前的Node类
  2. class DoubleNode extends Node {
  3.     constructor(element) {
  4.         super(element)
  5.         this.prev = null
  6.     }
  7. }
  8.  
  9. //继承自LinkList类加方法重写
  10. class DoubleLinkList extends LinkList {
  11.     constructor() {
  12.         super()
  13.         this.tail = null
  14.     }
  15.     push(element) {
  16.         const doubleNode = new DoubleNode(element)
  17.         if (this.head === null) {
  18.             this.head = doubleNode
  19.             this.tail = doubleNode
  20.         } else {
  21.             this.tail.next = doubleNode
  22.             doubleNode.prev = this.tail
  23.             this.tail = doubleNode
  24.         }
  25.         this.count++
  26.     }
  27.  
  28.     insert(element, index) {
  29.         if (index >= 0 && index <= this.count) {
  30.             const doubleNode = new DoubleNode(element)
  31.             if (index === 0) {
  32.                 //分链表是否有元素
  33.                 if (this.head === null) {
  34.                     this.head = doubleNode
  35.                     this.tail = doubleNode
  36.                 } else {
  37.                     this.head.prev = doubleNode
  38.                     doubleNode.next = this.head
  39.                     this.head = doubleNode
  40.                 }
  41.             } else if (index === this.count) {
  42.                 this.tail.next = doubleLinkList
  43.                 doubleLinkList.prev = this.tail
  44.                 this.tail = doubleLinkList
  45.             } else {
  46.                 let previous
  47.                 let current = this.head
  48.                 for (let i = 0; i < index; i++) {
  49.                     current = current.next
  50.                     previous = current.prev
  51.                 }
  52.                 current.prev = doubleNode
  53.                 doubleNode.next = current
  54.                 doubleNode.prev = previous
  55.                 previous.next = doubleNode
  56.             }
  57.             this.count++
  58.             return true
  59.         }
  60.         return false
  61.     }
  62.  
  63.     removeAt(index) {
  64.         if (index >= 0 && index < this.count) {
  65.             let current = this.head
  66.             if (index === 0) {
  67.                 this.head = current.next
  68.                 if (this.count === 1) {
  69.                     this.tail = null
  70.                 } else {
  71.                     this.head.prev = null
  72.                 }
  73.             } else if (index === this.count - 1) {
  74.                 current = this.tail
  75.                 this.tail = current.prev
  76.                 this.tail.next = null
  77.             } else {
  78.                 current = this.getNodeAt(index)
  79.                 let previous = current.prev
  80.                 let future = current.next
  81.                 previous.next = future
  82.                 future.prev = previous
  83.             }
  84.             this.count--
  85.             return current.element
  86.         }
  87.         return undefined
  88.     }
  89.  
  90. }

3.循环链表 

A.图解

B.封装代码
  1. //循环链表类继承自单链表类
  2. class CirculateLinkList extends LinkList {
  3.     constructor() {
  4.         super()
  5.     }
  6.     push(element) {
  7.         const node = new Node(element)
  8.         let current
  9.         if (this.head === null) {
  10.             this.head = node
  11.         } else {
  12.             current = this.getNodeAt(this.size() - 1)
  13.             current.next = node
  14.         }
  15.         node.next = this.head
  16.         this.count++
  17.     }
  18.  
  19.     insert(element, index) {
  20.         if (index >= 0 && index <= this.count) {
  21.             const node = new Node(element)
  22.             let current = this.head
  23.             if (index === 0) {
  24.                 if (this.head === null) {
  25.                     this.head = node
  26.                     node.next = this.head
  27.                 } else {
  28.                     node.next = this.head
  29.                     current = this.getNodeAt(this.size() - 1)
  30.                     this.head = node
  31.                     current.next = node
  32.                 }
  33.             } else {
  34.                 if (index === this.count) {
  35.                     current = this.getNodeAt(index - 1)
  36.                     current.next = node
  37.                     node.next = this.head
  38.                 } else {
  39.                     let previous = this.getNodeAt(index - 1)
  40.                     previous.next = node
  41.                     node.next = previous.next
  42.                 }
  43.             }
  44.             this.count++
  45.             return true
  46.         }
  47.         return false
  48.     }
  49.  
  50.     removeAt(index) {
  51.         if (index >= 0 && index < this.count) {
  52.             let current = this.head
  53.             if (index === 0) {
  54.                 if (this.count === 1) {
  55.                     this.head = null
  56.                 } else {
  57.                     let last = this.getNodeAt(this.size() - 1)
  58.                     this.head = current.next
  59.                     last.next = this.head
  60.                 }
  61.             } else {
  62.                 let previous = this.getNodeAt(index - 1)
  63.                 current = previous.next
  64.                 previous.next = current.next
  65.             }
  66.             this.count--
  67.             return current.element
  68.         }
  69.         return undefined
  70.     }
  71. }

(5)>>集合

Set结构，其实已经是JavaScript里封装好的，它是以值：值进行存储，且存入的值不能够重复

A.封装代码
  1. class Set {
  2.     items = {}
  3.     add(element) {
  4.         if (!this.has(element)) {
  5.             this.items[element] = element
  6.             return true
  7.         }
  8.         return false
  9.     }
  10.     delete(element) {
  11.         if (this.has(element)) {
  12.             delete this.items[element]
  13.             return true
  14.         }
  15.         return false
  16.     }
  17.     has(element) {
  18.         return element in this.items
  19.     }
  20.     clear() {
  21.         this.items = {}
  22.     }
  23.     size() {
  24.         return Object.keys(this.items).length
  25.     }
  26.     values() {
  27.         return Object.values(this.items)
  28.     }
  29. }
  30.  
  31. const mySet = new Set()
  32. let arr = [2, 1, 3, 3, 4, 5, 2, 1]
  33. arr.forEach((item) => {
  34.     mySet.add(item)
  35. })
  36. console.log(mySet.values());//[ 1, 2, 3, 4, 5 ]
 B.原装set使用

Set结构生成的是一个迭代器的结构，并且由于是集合，可以进行相关的并集交集差集等运算，可以进行相关的,详细的相关使用请查看下方代码

  1. let mySet = new Set()
  2. mySet.add(1)
  3. mySet.add(2)
  4. mySet.add(3)
  5.  
  6. let item = mySet.values() //生成的是一个迭代器
  7. console.log(item); //[Set Iterator] { 1, 2, 3 }
  8. console.log(item.next()); //{ value: 1, done: false }
  9. console.log(item.next()); //{ value: 2, done: false }
  10. console.log(item.next()); //{ value: 3, done: false }
  11.  
  12. // for (let i of item) {
  13. //     console.log(i);
  14. // } //1 2 3
  15.  
  16. // console.log([...item]);   //[ 1, 2, 3 ]
  17.  
  18.  
  19. // const A = new Set([1, 2, 3, 4])
  20. // const B = new Set([2, 3, 4, 5])
  21. // //取并集
  22. // const C = new Set([...A, ...B])
  23. // console.log(C);  //Set(5) { 1, 2, 3, 4, 5 }
  24.  
  25. // //取交集
  26. // const D = new Set([...A].filter(item => B.has(item)))
  27. // console.log(D);  //Set(3) { 2, 3, 4 }
  28.  
  29. // //取差集
  30. // const E = new Set([...A].filter(item => !B.has(item)))
  31. // console.log(E);  //Set(1) { 1 }

(6)>>字典

字典和集合很相似，集合以[值，值]的形式存储元素，字 典则是以[键，值]的形式来存储元素。字典也称作映射、符号表或关联数组。

A.字典的封装

  1. class Dictionary {
  2.     table = {}
  3.     //保证当存入的键是对象的时候，强制它转换为json字符串的形式
  4.     toStrFn(item) {
  5.         if (item === null) {
  6.             return "null"
  7.         } else if (item === undefined) {
  8.             return "undefined"
  9.         } else if (typeof item === 'string' || item instanceof String) {
  10.             return item
  11.         }
  12.         return JSON.stringify(item)
  13.     }
  14.     hasKey(key) {
  15.         return this.table[this.toStrFn(key)] != null
  16.     }
  17.     set(key, value) {
  18.         if (key != null && value != null) {
  19.             const tableKey = this.toStrFn(key)
  20.             // this.table[tableKey] = value
  21.             this.table[tableKey] = new ValuePair(key, value)
  22.  
  23.             return true
  24.         }
  25.         return false
  26.     }
  27.     get(key) {
  28.         let result = this.table[this.toStrFn(key)]
  29.         return result == null ? undefined : result.value
  30.     }
  31.     remove(key) {
  32.         if (this.hasKey(key)) {
  33.             delete this.table[this.toStrFn(key)]
  34.             return true
  35.         }
  36.         return false
  37.     }
  38.     keys() {
  39.         return this.keyValues().map(item => item.key)
  40.     }
  41.     values() {
  42.         return this.keyValues().map(item => item.value)
  43.     }
  44.     keyValues() {
  45.         return Object.values(this.table)
  46.     }
  47.     size() {
  48.         return Object.keys(this.table).length
  49.     }
  50.     isEmpty() {
  51.         return this.size() === 0
  52.     }
  53.     clear() {
  54.         this.table = {}
  55.     }
  56.     forEach(ch) {
  57.         const valuePair = this.keyValues()
  58.         for (let i = 0; i < valuePair; i++) {
  59.             ch(valuePair[i].key, valuePair[i].value)
  60.         }
  61.     }
  62. }
  63.  
  64. class ValuePair {
  65.     constructor(key, value) {
  66.         this.key = key
  67.         this.value = value
  68.     }
  69. }

B.散列表

HashMap 类，它是 Dictionary 类的一种散列表 实现方式。.散列算法的作用是尽可能快地在数据结构中找到一个值。这样在面对海量数据的时候可以加快查询的速度

  1. class HashTable {
  2.     table = {}
  3.     toStrFn(item) {
  4.         if (item === null) {
  5.             return "null"
  6.         } else if (item === undefined) {
  7.             return "undefined"
  8.         } else if (typeof item === 'string' || item instanceof String) {
  9.             return item
  10.         }
  11.         return JSON.stringify(item)
  12.     }
  13.  
  14.     // hashCode(key) {
  15.     //     if (typeof key === 'number') {
  16.     //         return key
  17.     //     } else {
  18.     //         const tableKey = this.toStrFn(key)
  19.     //         let hash = 0
  20.     //         for (let i = 0; i < tableKey.length; i++) {
  21.     //             hash += tableKey.charCodeAt(i)
  22.     //         }
  23.     //         return hash % 35
  24.     //     }
  25.     // }
  26.     //将对应字符串或对象转成的字符串的ASCII值进行转换生成相应的数值
  27.     hashCode(key) {
  28.         const tableKey = this.toStrFn(key)
  29.         let hash = 5381
  30.         for (let i = 0; i < tableKey.length; i++) {
  31.             hash = (hash * 33) + tableKey.charCodeAt(i)
  32.         }
  33.         return hash % 1013
  34.     }
  35.  
  36.     set(key, value) {
  37.         if (key != null && value != null) {
  38.             let position = this.hashCode(key)
  39.             this.table[position] = new ValuePair(key, value)
  40.         }
  41.     }
  42.  
  43.     get(key) {
  44.         let result = this.table[this.hashCode(key)]
  45.         return result == null ? undefined : result.value
  46.     }
  47.  
  48.     remove(key) {
  49.         if (this.table[this.hashCode(key)] != null) {
  50.             delete this.table[this.hashCode(key)]
  51.             return true
  52.         }
  53.         return false
  54.     }
  55. }
  56.  
  57. class ValuePair {
  58.     constructor(key, value) {
  59.         this.key = key
  60.         this.value = value
  61.     }
  62. }

3.ES6中的Map

  1. var mymap = new Map()
  2. mymap.set("name","kerwin")
  3. mymap.set({a:1},"aaaaaa")
  4.  
  5. mymap.get("name")
  6. mymap.delete("name")

 (7)>>树

树是一种分层数据的抽象模型。

 1.二叉树

         二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。

2.二叉搜索树

        二叉搜索树（BST）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值， 在右侧节点存储（比父节点）大的值。

  >>关于遍历

  • 中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是以从最小到最大的顺序 访问所有节点。 中序遍历的一种应用就是对树进行排序操作。

  • 先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构 化的文档。（访问根节点，遍历左子树，遍历右子树）

  • 后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目 录及其子目录中所有文件所占空间的大小。(简而言之就是在树中从最末尾的那一代开始从左到右打印，一直到整个树都被遍历完成)

>>关于移除要考虑的情况

A.封装代码
  1. class Node {
  2.     constructor(key) {
  3.         this.key = key
  4.         this.left = null
  5.         this.right = null
  6.     }
  7. }
  8.  
  9. class BST {
  10.     constructor() {
  11.         this.root = null
  12.     }
  13.  
  14.     insert(key) {
  15.         if (this.root == null) {
  16.             this.root = new Node(key)
  17.         } else {
  18.             this.insertNode(this.root, key)
  19.         }
  20.     }
  21.  
  22.     insertNode(node, key) {
  23.         if (this.compareFn(key, node.key) === -1) {
  24.             if (node.left == null) {
  25.                 node.left = new Node(key)
  26.             } else {
  27.                 this.insertNode(node.left, key)
  28.             }
  29.         } else {
  30.             if (node.right == null) {
  31.                 node.right = new Node(key)
  32.             } else {
  33.                 this.insertNode(node.right, key)
  34.             }
  35.  
  36.         }
  37.     }
  38.  
  39.     compareFn(a, b) {
  40.         if (a === b) {
  41.             return 0
  42.         }
  43.         return a < b ? -1 : 1
  44.     }
  45.  
  46.     //中序遍历，注意递归调用的顺序
  47.     middleMap(callback) {
  48.         this.middleMapNode(this.root, callback)
  49.     }
  50.  
  51.     middleMapNode(node, callback) {
  52.         if (node != null) {
  53.             this.middleMapNode(node.left, callback)
  54.             callback(node.key)
  55.             this.middleMapNode(node.right, callback)
  56.         }
  57.     }
  58.  
  59.     //先序遍历
  60.     prevMap(callback) {
  61.         this.prevMapNode(this.root, callback)
  62.     }
  63.  
  64.     prevMapNode(node, callback) {
  65.         if (node != null) {
  66.             callback(node.key)
  67.             this.prevMapNode(node.left, callback)
  68.  
  69.             this.prevMapNode(node.right, callback)
  70.         }
  71.     }
  72.  
  73.     //后序遍历
  74.     behindMap(callback) {
  75.         this.behindMapNode(this.root, callback)
  76.     }
  77.  
  78.     behindMapNode(node, callback) {
  79.         if (node != null) {
  80.             this.behindMapNode(node.left, callback)
  81.             this.behindMapNode(node.right, callback)
  82.             callback(node.key)
  83.         }
  84.     }
  85.  
  86.     min() {
  87.         return this.minNode(this.root)
  88.     }
  89.  
  90.     minNode(node) {
  91.         let current = node
  92.         while (current != null && current.left != null) {
  93.             current = current.left
  94.         }
  95.         return current.key
  96.     }
  97.  
  98.     max() {
  99.         return this.maxNode(this.root)
  100.     }
  101.  
  102.     maxNode(node) {
  103.         let current = node
  104.         while (current != null && current.right != null) {
  105.             current = current.right
  106.         }
  107.         return current.key
  108.     }
  109.  
  110.     search(key) {
  111.         return this.searchNode(this.root, key)
  112.     }
  113.  
  114.     searchNode(node, key) {
  115.         if (node === null) {
  116.             return false
  117.         }
  118.         if (this.compareFn(key, node.key) === -1) {
  119.             return this.searchNode(node.left, key)
  120.         } else if (this.compareFn(key, node.key) === 1) {
  121.             return this.searchNode(node.right, key)
  122.         } else {
  123.             return true
  124.         }
  125.     }
  126.  
  127.     remove(key) {
  128.         this.removeNode(this.root, key)
  129.     }
  130.  
  131.     removeNode(node, key) {
  132.         if (node == null) {
  133.             return null
  134.         }
  135.         if (this.compareFn(key, node.key) === -1) {
  136.             node.left = this.removeNode(node.left, key)
  137.             console.log(node);
  138.             return node
  139.         } else if (this.compareFn(key, node.key) === 1) {
  140.             node.right = this.removeNode(node.right, key)
  141.             console.log(node);
  142.             return node
  143.  
  144.         } else {
  145.             if (node.left == null && node.right == null) {
  146.                 node = null
  147.                 return node
  148.             }
  149.             if (node.left == null) {
  150.                 node = node.right
  151.                 return node
  152.             } else if (node.right == null) {
  153.                 node = node.left
  154.                 return node
  155.             }
  156.             const target = this.minNode(node.right)
  157.             node.key = target.key
  158.             node.right = this.removeNode(node.right, target.key)
  159.             return node
  160.         }
  161.     }
  162. }
  163.  
  164. const tree = new BST()
  165. tree.insert(6)
  166. tree.insert(4)
  167. tree.insert(8)
  168. tree.insert(3)
  169. tree.insert(5)
  170. tree.middleMap((value) => console.log(value)) //3 4 5 6 8
  171. tree.prevMap((value) => console.log(value))   //6 4 3 5 8
  172. tree.behindMap((value) => console.log(value)) //3 5 4 8 6
  173.

(8)>>二叉堆

二叉堆是一种特殊的二叉树，有两种特性

  • 它是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点）， 并且最后一层的叶节点尽可能都是左侧子节点，这叫作结构特性。

  • 二叉堆不是最小堆就是最大堆。最小堆允许你快速导出树的最小值，最大堆允许你快速 导出树的最大值。所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子 节点。这叫作堆特性。

1.最小堆

  1. //把二叉堆的数据按数组的格式存储起来
  2. class minHeap {
  3.     heap = []
  4.     //根据现有节点计算左子节点
  5.     getLeftSonIndex(index) {
  6.         return 2 * index + 1
  7.     }
  8.     getRightSonIndex(index) {
  9.         return 2 * index + 2
  10.     }
  11.     getParentIndex(index) {
  12.         if (index === 0) {
  13.             return undefined
  14.         } else {
  15.             return Math.floor((index - 1) / 2)
  16.         }
  17.     }
  18.  
  19.     insert(value) {
  20.         if (value != null) {
  21.             this.heap.push(value)
  22.             this.shiftUp(this.heap.length - 1)
  23.             return true
  24.         }
  25.         return false
  26.     }
  27.  
  28.     shiftUp(index) {
  29.         let parent = this.getParentIndex(index)
  30.         while (index > 0 && this.compareFn(this.heap[parent], this.heap[index]) === 1) {
  31.             this.swap(this.heap, parent, index)
  32.             index = parent
  33.             parent = this.getParentIndex(index)
  34.         }
  35.     }
  36.  
  37.     compareFn(a, b) {
  38.         if (a === b) {
  39.             return 0
  40.         }
  41.         return a < b ? -1 : 1
  42.     }
  43.  
  44.     swap(arr, a, b) {
  45.         let temp = arr[a]
  46.         arr[a] = arr[b]
  47.         arr[b] = temp
  48.     }
  49.  
  50.     size() {
  51.         return this.heap.length
  52.     }
  53.  
  54.     isEmpty() {
  55.         return this.size() === 0
  56.     }
  57.  
  58.     findMinimun() {
  59.         return this.heap[0]
  60.     }
  61.     //去除根节点及后面的操作
  62.     extractFirst() {
  63.         if (this.isEmpty()) {
  64.             return undefined
  65.         }
  66.         if (this.size() === 1) {
  67.             return this.heap.shift()
  68.         }
  69.         const removedValue = this.heap[0]
  70.         this.heap[0] = this.heap.pop()
  71.         this.shiftDown(0)
  72.         return removedValue
  73.     }
  74.  
  75.     shiftDown(index) {
  76.         let current = index
  77.         let left = this.getLeftSonIndex(index)
  78.         let right = this.getRightSonIndex(index)
  79.         if (left < this.size() && this.compareFn(this.heap[current], this.heap[left]) === 1) {
  80.             current = left
  81.         }
  82.         if (right < this.size() && this.compareFn(this.heap[current], this.heap[right]) === 1) {
  83.             current = right
  84.         }
  85.         if (index !== current) {
  86.             this.swap(this.heap, index, current)
  87.             this.shiftDown(current)
  88.         }
  89.     }
  90. }

2.最大堆

可以偷个懒，直接继承并随便改写一下比较两数大小的方法

  1.  
  2. class maxHeap extends minHeap {
  3.     constructor() {
  4.         super()
  5.     }
  6.     compareFn(a, b) {
  7.         if (a === b) {
  8.             return 0
  9.         }
  10.         return a > b ? -1 : 1
  11.     }
  12. }

三.总结

        数据结构是个神奇的东西，它充斥在代码中，却仿佛离我们那么遥远，学习数据结构不仅是在面对不同的数据时要施加不同的策略，而且可以提高我们的代码阅读能力。当然了，对于数据结构的学习依然任重而道远，各位同仁加油吧，希望可以点赞收藏加关注嘿嘿。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/90454?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号