Basic knowledge is like the foundation of a building, it determines the height of our technology. And want to do something quickly, the premise must be the basic ability is excellent, “internal work” to be in place. — Beauty of data structures and algorithms

Data structures and algorithms are the foundation of all computer languages and one of the key variables that determine how far a programmer can go in coding. This article is a summary of “Learning javascript data structures and algorithms”, focusing on taking you to understand the common data structures, as well as their JS implementation. So although this article is a little longer, it is not difficult to understand.

## Xiao gang teacher

- Big O notation
- An array of
- The stack
- The queue
- The list
- Sets and dictionaries
- The tree
- figure

## Big O notation

The big O notation is the full name of the big O time complexity notation, which shows the trend of the code execution time as the data size increases. The big O notation is used to roughly estimate the efficiency of an algorithm, so the big O notation focuses only on the piece of code with the highest magnitude (which is generally the piece of code that has been iterated the most times).

- O(1): there is no loop statement and recursive statement in the code, even thousands of lines, complexity is ALSO O(1);
- O(n) : there are loop statements and recursive statements in the code, as follows:

```
const print = n= > {
for (let i = 0; i< n; i++) {
console.log(i)
}
}
Copy the code
```

In this method, the for loop in print method is executed n times, so the time complexity is O(n).

- O(logn) : there is a loop in the code, but the loop condition is:

```
const print = n= > {
let i = 1
while (i <= n) {
i = i * 2
console.log(i)
}
}
Copy the code
```

The loop condition variable I in the code is multiplied by 2 each time it loops, and the loop ends when I is greater than 2. So the number of code loops is x as shown below:

Most of us have probably forgotten what we learned in high school about geometric sequences, let alone logarithms.

In the expression method of logarithmic time complexity, we ignore the “base” of logarithm and express it as O(logn) uniformly.

If the print method is executed n times in the loop, the time complexity is O(nlogn).

- O(m*n) and O(m+n) : If there are two loops in the code, they loop separately
`m`

Time and`n`

Times. If the two loops are nested, the complexity is`O(m*n)`

, if there is no nesting relationship, its complexity is`O(m+n)`

。

## An array of

An array is a linear table data structure. It uses a contiguous set of memory Spaces to store a set of data of the same type. — Beauty of data structures and algorithms

Js originally has no real array, because the ARRAY of JS can store different types of data, and different data types need different sizes of storage space, which leads to the memory address used to store the array can not be continuous. Therefore, js arrays are stored in a similar way to hash mapping, which is relatively inefficient to read and write arrays.

The V8 engine optimizes arrays so that if all the types in an array are the same, a contiguous space in memory is created to store the array. However, if a different type is added to the array, the V8 engine reconstructs the array the same way it did before, which becomes even less efficient.

New to ES6 is ArrayBuffer, which can create arrays of contiguous memory space. Obviously, it’s faster to iterate over an array created with an ArrayBuffer.

Array is a very important data structure in programming. Most languages implement array data structure natively. Js array is more flexible, and the native implementation of many array operation methods, these methods to often use must be familiar with the heart.

Array.prototype.falt() array.of () array.form ().

## Stack data structure

Stacks and queues, which are also arrays in nature, are special.

A stack is a last-in, first-out ordered collection, such as the execution stack of JS.

The new element is added to the top of the stack, and the element to be removed must be removed only from the top of the stack, like a cylinder with only one port:

### The realization of the stack

In the book, the author uses WeakMap of ES6 to write a stack function:

Essentially using instance this as a bridge to get the stack.

```
let Stack = (function(){
let items = new WeakMap(a)class Stack {
constructor () {
items.set(this, [])
}
pop () { / / out of the stack
return items.get(this).pop()
}
push (v) { / / into the stack
items.get(this).push(v)
}
peek () { // Get the current top of the stack
return items.get(this)[items.get(this).length - 1]
}
size () { / / the stack length
return items.get(this).length
}
isEmpty () { // Whether the stack is empty
return items.get(this).length === 0
}
clear () { / / empty stack
items.get(this).length = 0}}return Stack
})()
Copy the code
```

Let’s first introduce WeakMap of ES6. WeakMap only accepts the object type as the key name, and the key name is of weak reference type. Weak references are a type that is easily collected by the garbage collection mechanism. Whenever the garbage collection mechanism finds that an object is referenced only by weak reference types, the object is collected. This in the above code is itself a strong reference type, but this is also treated as the weak reference key name of WeakMap. Therefore, when this instance is destroyed, there is only weak reference to WeakMap in the memory address of the object that this originally points to. Therefore, the corresponding key-value pairs in WeakMap will be destroyed when the garbage collection mechanism runs.

Still do not understand WeakMap weak reference again look at this article.

The stack function is a good example of using WeakMap weak references:

As shown in the figure, variables A and B create two stack instances and add a numeric element to each stack. There are two stacks in the items closure. Then set variable B to NULL, at this time, the stack instance object created by variable B loses the strong reference, only the weak reference of WeakMap key name is left, but there are still two stacks in the printed items, because the garbage collection mechanism is not running at this time. Ten seconds later, Chrome’s garbage collection mechanism triggers and removes the invalid stacks from the items, leaving only one stack left in the printed ITmes. (P.S. tests have found that the current version of the V8 engine garbage collection mechanism cleans up every 10 seconds at most)

### The application of the stack

Decimal to binary is dividing a decimal number by 2, rounding down each time and continuing to divide by 2 until the result is 0. Then the reverse order of the array is the binary result:

```
10 / 2= >5... 0
5 / 2= >2..1.
2 / 2= >1... 0
1 / 2= >0..1.
// The binary conversion results in 1010
Copy the code
```

The following implementation cannot be used to convert to hexadecimal because hexadecimal contains letters:

```
function baseConverter(number, base = 2) {
let remStack = new Stack()
let baseResult = ' '
while (number > 0) {
remStack.push(number % base) // Store the remainder on the execution stack
number = Math.floor(number / base)
}
while(! remStack.isEmpty()) { baseResult += remStack.pop()// Remove the top of the stack and store string concatenation
}
return baseResult
}
baseConverter(10.2) / / 1010
Copy the code
```

That’s how stack data structures are used. It is very difficult to use stack to deal with the data structure in our daily front-end coding, because the native array is basically enough. But if you encounter a FIFO data structure, for rigor and professionalism, use queues!

## Queue data structure

Queue data structures are ordered collections that follow first-in, first-out, such as JS task queues.

Compared with a queue, a stack is like a tube, with only one port, last in first out; A queue is like a pipe with two ports, one in and the other out.

As the name implies, a task queue in JS is a queue data structure.

And the queue in our daily life is the queue. The first one in the queue is the first one to receive the service, such as the cashier and the bathroom.

### Normal queue

```
let Queue = (function() {
let items = new WeakMap(a)class Queue {
constructor () {
items.set(this, [])
}
enqueue (v) { / / loaded
items.get(this).push(v)
}
dequeue () { / / dequeue
return items.get(this).shift()
}
front () { // Get the first digit of the current queue
return items.get(this) [0]
}
size () { / / the stack length
return items.get(this).length
}
isEmpty () { // Whether the stack is empty
return items.get(this).length === 0
}
clear () { / / empty stack
items.get(this).length = 0}}return Queue
})()
Copy the code
```

The implementation is the same as the stack data structure, but the specific implementation method is different. Out of the stack implements the array pop, out of the column implements the array shift.

### Priority queue

Priority queues are data structures that are queued in order of rank. For example, in the airport queue, ordinary tickets are at the back of the ordinary queue, while VIP tickets are at the back of the VIP queue, and ordinary queues are at the back of the VIP queue.

```
The lower the level is, the higher the level is: 0 > 1 > 2
let PriorityQueue = (function() {
let items = new WeakMap(a)let QueueElement = function (value, level) {
this.value = value
this.level = level
}
class PriorityQueue {
constructor () {
items.set(this, [])
}
enqueue (value, level) { / / loaded
let queueElement = new QueueElement(value, level)
let arr = items.get(this)
let added = arr.some((item, index) = > {
if (level < item.level) { // If the level of the element to be added is lower than that of item, it is added before that object
arr.splice(index, 0, queueElement)
return true}})if(! added) arr.push(queueElement) } dequeue () {/ / dequeue
return items.get(this).shift()
}
front () { // Get the first digit of the current queue
return items.get(this) [0]
}
size () { / / the stack length
return items.get(this).length
}
isEmpty () { // Whether the stack is empty
return items.get(this).length === 0
}
clear () { / / empty stack
items.get(this).length = 0}}return Queue
})()
Copy the code
```

### Queue application

Below with the ordinary queue to achieve a drum pass flower game. Passing flowers means that everyone forms a circle and passes the flowers to the person next to them as soon as possible at the beginning of the game. At the end of the game, whoever has the flowers will be out. Until the last person left is the winner.

```
function hotPotato (nameList) {
let queue = new Queue()
nameList.map(name= > queue.enqueue(name))
return function (num) {
if (queue.isEmpty()) {
console.log('The game is over')
return
}
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue())
}
let outer = queue.dequeue()
console.log(outer + '出局了')
if (queue.size() === 1) {
let winner = queue.dequeue()
queue = null // Enable the garbage collection mechanism to automatically clear weak reference memory
console.log(winner + 'won')
return winner
} else {
return outer
}
}
}
let nameList = ['rat'.'cattle'.'the tiger'.'rabbit'.'dragon'.'snakes'.'the horse'.'sheep'.'monkey'.'chicken'.'dog'.'pig']
let game = hotPotato(nameList)
game(12) // The mouse is out
game(22) // The cow is out. game(32) / / the dragon wins
Copy the code
```

Both stacks and queues are essentially variants of arrays. The stability and security of the data structure are guaranteed by the encapsulation method that exposes only what the structure should have.

## The list

Although arrays are convenient for accessing elements, the cost of inserting or removing elements at the beginning and middle of an array is high because arrays are stored in a contiguous memory space, and inserting a node changes the insertion point and the position of all subsequent elements. When there are enough elements in the array, the cost of inserting an element becomes apparent.

One advantage of linked lists over traditional arrays is that you don’t need to move other elements when you add or remove them. A linked list is also a collection of ordered elements, but the elements in the list are not placed consecutively in memory, but have a pointer to the next adjacent element. So while linked lists are quick to insert and remove nodes, querying nodes is slow because you have to traverse the query from beginning to end. Arrays are quick to query nodes, but slow to insert and remove nodes.

There are many types of linked lists:

### Singly linked list

As the name implies, a one-way list is a linked list data structure with only next and no PreV. The implementation of one-way linked list is as follows:

```
const LinkedList = (function() {
const Node = function (element) { // Construct a new node
this.element = element
this.next = null
}
class LinkedList {
constructor () { // Generate the head node head and the list length during initialization
this.head = null
this.length = 0
}
append (element) { // Add nodes from the tail
let newNode = new Node(element)
if (!this.head) { // If there is no head node, set the new node as the head node
this.head = newNode
} else { If there is a head node, add a new node to the end of the list
let current = this.head
while (current.next) { // Find the end of the list
current = current.next
}
current.next = newNode
}
this.length++
}
insert (position, element) { // Insert nodes by position
if (position < 0 || position > this.length) { // boundary judgment
return false
}
let newNode = new Node(element)
if (position === 0) { // Add a new node to the head of the list
newNode.next = this.head
this.head = newNode
} else { // Add a new node to the unlinked list head
let index = 0, previous , current = this.head // index Indicates whether the index is the current position
while (index++ < position) {// IfindexLess thanpositionIncrementing and moving the variable to the next nodeprevious = current
current = current.next
}
newNode.next = current
previous.next = newNode
}
this.length++
return true
}
removeAt (position) {// Remove nodes by locationif (position < 0 || position > this.length) {
return null
}
let index = 0, previous , current = this.head
if (position === 0) {
this.head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
}
toString (symbol) {// String the list valueslet current = this.head, str = ' '
while (current) {
str+ =current.element
current = current.next
if (current) {
str+ =symbol ? symbol :', '}}return str
}
indexOf (element) {// Find the first occurrence of the valuelet current = this.head, index = 0
while (current) {
if (current.element= = =element) {
return index
}
current = current.next
index++
}
return - 1
}
find (element) {// Find the node where the value first appearedlet current = this.head
while (current) {
if (current.element= = =element) {
return current
}
current = current.next
}
return false
}
isEmpty() {// Check whether the list is emptyreturn this.length= = =0
}
size() {// Return the length of the listreturn this.length
}
getHead() {// Get the list head nodereturn this.head}}return LinkedList}) ()Copy the code
```

### Two-way linked list

In a bidirectional list, nodes have next pointing to the next node and prev pointing to the previous node. Bidirectional lists have the advantage of being able to iterate from beginning to end as well as from end to end. If you want to go from the beginning to the end to the middle, and you want to go from the end to the end, you can do that.

Although bidirectional linked lists occupy more memory than unidirectional linked lists, the biggest advantage of bidirectional linked lists is that when deleting a given pointer operation, there is no need to go through again to find the node pointed to by its PREV. Therefore, the time complexity of the deletion operation of unidirectional linked lists is O(n), while that of bidirectional linked lists is O(1).

```
const DoubleLinkedList = (function(){
let Node = function (element) {
this.element = element
this.prev = this.next = null
}
class DoubleLinkedList {
constructor () {
this.head = this.tail = null
this.length = 0
}
append (element) {
let newNode = new Node(element)
if (!this.head) {
this.head = this.tail = newNode
} else {
let current = this.head
while (current) {
current = current.next
}
current = this.tail
current.next = this.tail = newNode
newNode.prev = current
}
}
insert (position, element) {
if (position < 0 || position > this.length) {
return false
}
let newNode = new Node(element)
let previous, current = this.head, index = 0
if (position === 0) {
if (!this.head) {
this.head = this.tail = newNode
} else {
newNode.next = current
current.prev = newNode
this.head = newNode
}
} else if (position === this.length) {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
} else {
while (index++ < position) {
previous = current
current = newNode
}
previous.next = newNode
newNode.prev = previous
newNode.next = current
current.prev = newNode
}
this.length++
return true
}
removeAt (position) {
if (position < 0 || position >= this.length) { return false } let previous, current = this.head, Index = 0 if (position === 0) {this.head = current. Next if (this.length === 1) {this.tail = null Current. Next is null, Else {this.head. Prev = null}} else if (position === this.length - 1) {current = this.tail this.tail = current.prev this.tail.next = null } else { while (index++< positon) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
this.length--
return current.element} // Delete the specified noderemoveByNode (node) {
if (!node.prev) {
this.head = node.next
this.head.prev = null
return
}
if (!node.next) {
return
}
let prev = node.prev
let next = node.next
prev.next = next
next.prev = prev} // Other methods implement the same as unidirectional lists}return DoubleLinkedList
})
Copy the code
```

### Circular linked list

A circular list refers to a circle formed by references between the head and tail of the list.

Unidirectional cyclic linked list:

The implementation of a one-way list is almost the same as that of a one-way list, but when adding and head and tail nodes, it is necessary to set current. Next = this.head.

Bidirectional circular linked list:

The implementation of a bidirectional circular list is similar to that of a bidirectional list.

A linked list is a data structure that has no original implementation in JS. Compared to arrays, linked lists are more efficient in adding and removing elements. So when you need to add and remove large numbers of elements, the best choice is a linked list.

## Sets and dictionaries

Collections and dictionaries are used to store non-repeating values. Elements in collections and dictionaries can be of any type.

### A collection of

A collection is a data structure composed of an unordered set of unique elements, whose keys are values because they are never repeated.

Like the set in mathematics, the set in JS can be “union”, “intersection”, “difference”, “subset” operations.

A union is an element of two sets joined together, an intersection is an element that is common to both sets, a difference is an element that is not in the other set, and a subset is an element of A that is present in b.

Because ES6 implements the Set class natively, we can use inheritance to implement four operations on the Set class:

```
class MySet extends Set {
constructor(... args) {super(... args) } union (otherSet) {/ / and set
return new MySet([...this, ...otherSet])
}
intersection (otherSet) { / / intersection
// return new Set([...this].filter(x => otherset.has (x))) // mark aa
let newSet = new MySet()
for (let a of this) {
if (otherSet.has(a)) {
newSet.add(a)
}
}
return newSet
}
difference (otherSet) { / / difference set
// return new Set([...this].filter(x => ! Otherset.has (x))) // mark bb
let newSet = new MySet()
for (let x of this) {
if(! otherSet.has(x)) { newSet.add(x) } }return newSet
}
isSubOf (otherSet) { / / the subset
if (this.size > otherSet.size) {
return false
} else {
// return [...this].every(item => otherset.has (item)) // mark cc
for (let x of this) {
if(! otherSet.has(item)) {return false}}return true}}}var a = new MySet([1.2.3.4])
var b = new MySet([3.4.5.6])
var c = new MySet([1.2])
a.intersection(b) // Set(2) {3, 4}
a.difference(b) // Set(2) {1, 2}
a.union(b) // Set(6) {1, 2, 3, 4, 5, 6}
c.isSubOf(a) // true
c.isSubOf(b) // false
Copy the code
```

A single line of code marked “AA BB cc” in the above code can do this, but with O(n²) time complexity, compared to O(n) time complexity in the code below. Because […this] iterates through all the elements in the set to an array, and then every iterates through the elements in the array.

### The dictionary

As the name suggests, a dictionary is a data structure that queries values based on keys, often referred to as “key-value pairs.”

The dictionary data structure is called Map in the ES6 implementation. A Map and an Object are composed of key-value pairs. The key-value pairs cannot be duplicated. The difference, however, is that the key of Object can only be a string and is unordered; Map keys can be any type of value, including objects, and are ordered.

```
let o = { 2: 2.1: 1 }
Object.keys(o) // ['1', '2'] keys can only be unordered strings
let map = new Map()
map.set(o, 1)
map.set(2.2)
for (let key of map) console.log(key) // [{...}, 1] [2, 2] keys can be of any type and are traversed in the order they are added
Copy the code
```

Note that since elements in collections and dictionaries can be of any type, if you add an object without a reference, it will never be retrieved:

```
let a = new MySet()
a.add({})
a.has({}) // false
let b = new Map()
b.set({}, 1)
b.get({}) // undefined
Copy the code
```

### WeakSet and WeakMap

In the implementation of stack and queue, we use the WeakMap class. In fact, WeakMap WeakSet class is almost the same as Map Set class, with only the following few differences:

- You can only use objects as keys
- The key is of weak reference type
`WeakMap WeakSet`

There is no traverser, so it cannot be called`Keys (), values(), entries()`

Method, no`size`

Properties and`clear()`

Methods, the most four increase, delete, change, check methods`Get (), set(), has(), delete()`

WeakMap WeakSet weak reference features it has already been said, if you have not understand place reference here.

## The tree

Tree is a hierarchical data abstraction model, which is the first non-sequential data structure introduced in this paper.

A tree consists of root nodes, child nodes, and leaf nodes. The root node is the node at the top of the tree and has no parent node. A node with a parent is called a child node, and a node without a child is called a leaf node.

The most common binary tree can have at most two children: the left child and the right child.

### Binary search tree

A binary search tree is a type of binary tree that only allows you to store values smaller than the parent on the left and larger than the parent on the right. This definition is very efficient for finding/inserting/removing nodes into the tree’s nodes.

Let’s implement a binary search tree:

```
const BinarySearchTree = (function(){
const Node = function (key) {
this.key = key
this.left = null
this.right = null
}
const insertNode = function (node, newNode) { // Insert node helper functions
if (newNode.key < node.key) {
if (node.left) {
insertNode(node.left, newNode)
} else {
node.left = newNode
}
} else {
if (node.right) {
insertNode(node.right, newNode)
} else {
node.right = newNode
}
}
}
const searchNode = function (node, key) { // Search node auxiliary functions
if(! node) {return false
}
if (key < node.key) {
return searchNode(node.left, key)
} else if (key > node.key) {
return searchNode(node.right, key)
} else {
return true}}const minNode = function (node) { // Find the smallest node and return key
if(! node) {return null
}
if (node.left) {
return minNode(node.left)
} else {
return node.key
}
}
const maxNode = function (node) { // Find the largest node and return key
if(! node) {return null
}
if (node.right) {
return maxNode(node.right)
} else {
return node.key
}
}
const findMinNode = function (node) { // Find the smallest node and return the node object
if(! node) {return null
}
if (node.left) {
return findMinNode(node.left)
} else {
return node
}
}
const removeNode = function (node, key) { // Remove the node and return the passed node
if (node === null) {
return null
}
if (key < node.key) { // In this case, node.left needs to be updated, and a new node with updated Node.left is returned
node.left = removeNode(node.left, key)
return node
} else if (key > node.key) { // In this case, node.right needs to be updated, and a new node with node.right updated is returned
node.right = removeNode(node.right, key)
return node
} else { // In this case, node.key or other update means (including null node, or updating node.right) are required, and the updated node is returned
// In case 1, the leaf node is removed
if (node.left === null && node.right === null) {
node = null
return node
}
// In case 2, a node with only one child node is removed
if (node.left === null) { // There are only right child nodes
node = node.right
return node
} else if (node.right === null) {// Only left child node
node = node.left
return node
}
// In case 3, the node with two children is removed
const aux = findMinNode(node.right) // Find the smallest node in the subtree, which must be a leaf node
node.key = aux.key // Set node's key to aux's key, but there are two identical keys
node.right = removeNode(node.right, aux.key) // Remove duplicate aux.key from the tree with node.right as root
return node
}
}
class BinarySearchTree {
constructor () {
this.root = null
}
insert (key) { // Insert the node
let newNode = new Node(key)
if (!this.root) {
this.root = newNode
} else {
insertNode(this.root, newNode)
}
}
serach (key) { // Search the node and return a Boolean value
return searchNode(this.root, key)
}
min () { // The smallest node
return minNode(this.root)
}
max () { // Maximum node
return maxNode(this.root)
}
remove (key) { // Delete a node
this.root = removeNode(this.root, key)
}
}
return BinarySearchTree
})()
Copy the code
```

Among them, only the remove method is complicated. The nodes to be deleted may be “leaf node”, “only right child node”, “only left child node”, “both left and right child node”, etc.

First, the removeNode method takes two parameters: the node of the node you want to remove, and the key of the node you want to remove, which returns the new node of the removed node. Why return to the node? If you want to delete the attribute of an object in JS, you must be able to obtain the Reference type composed of “object + attribute”, for example, obj + name in delete obj. Name consists of Reference type. The function parameter node is a reference type, and the variable node in the function body refers to the reference of the node. If you set node = null, the variable node in the function body is released, and the node is not deleted. If the node to be deleted is this node, you must find the parent node of the node, which obviously cannot be found here. So what to do? We can return the new node after deleting the node and assign the value to the old node. This is a good idea because it takes less code to pass functions and is cleaner.

Then, on the basis of the above, if the leaf node is to be removed, then simply assign null to the node and return it to the node. If the only node to be removed is right, the node is assigned the value of Node. right and returned to the node where the deletion effect is achieved. If the node has left right at the same time, the key of the smallest node in the right is replaced by the current node and the smallest node in the right repetition is deleted, and then the node is returned to the corresponding node.

In addition to the above code to achieve the add and delete check, binary search tree has an important function is traversal. According to the different traversal order, it can be divided into sequential traversal (which is superior to sequential access of descendant nodes), middle-order traversal (sequential access of nodes from the smallest to the largest), and post-order traversal (visit descendants of nodes first, and then visit nodes themselves).

Sequential traversal of binary search trees :(itself -> left -> right)

The sequential traversal code is as follows:

```
const BinarySearchTree = (function(){... const preOrder =function (node, callback) {
if (node) {
callback(node.key)
preOrder(node.left, callback)
preOrder(node.right, callback)
}
}
...
class BinarySearchTree {
...
preOrderTraverse (callback) {
preOrder(this.root, callback)
}
...
}
return BinarySearchTree
})()
Copy the code
```

Middle order traversal of binary search tree :(minimum -> maximum)

The sequence traversal code is as follows:

```
const BinarySearchTree = (function(){... const inOrder =function (node, callback) {
if (node) {
inOrder(node.left, callback)
callback(node.key)
inOrder(node.right, callback)
}
}
...
class BinarySearchTree {
...
inOrderTraverse (callback) {
inOrder(this.root, callback)
}
...
}
return BinarySearchTree
})()
Copy the code
```

Backward traversal of binary search trees :(descendant -> itself)

The sequence traversal code is as follows:

```
const BinarySearchTree = (function(){... const postOrder =function (node, callback) {
if (node) {
postOrder(node.left, callback)
postOrder(node.right, callback)
callback(node.key)
}
}
...
class BinarySearchTree {
...
postOrderTraverse (callback) {
postOrder(this.root, callback)
}
...
}
return BinarySearchTree
})()
Copy the code
```

As you can see, all three traversals are recursive, but the only difference is that the callback function is called in a different order. Sequential traversal callback is called first, middle traversal callback is called in the middle, and callback is called last.

In addition to binary search tree, there are AVL self-balancing tree, red and black book, multi-fork tree, etc., in the future study.

## figure

A graph is an abstract model of a mesh structure, consisting of edges and vertices. For maps, vertices are places and edges are routes connecting two places. For wechat QQ, the vertex is the user, the edge is two users added friends to establish a relationship.

The graph is divided into directed graph and undirected graph. Directed graph is one-way, such as Weibo fans and Weibo boda V. Fans follow BIG V, but big V does not follow fans. An undirected graph is a graph that has no direction between vertices, such as between wechat friends.

One way to store graphs is an adjacency matrix. The adjacency matrix is A two-dimensional array, A[I][j] === A[j][I].

The adjacency matrix records the relationship between all vertices, but in fact many vertices are not related, so this causes a waste of storage space. But adjacency matrices are very efficient at getting the relationship between two vertices.

Another way to store graphs is an adjacency list. Each vertex in the adjacency list has a linked list that points to the vertex it points to. In this way, there are no unrelated vertices in the table, saving storage space. On the other hand, searching for adjacent vertices can be time-consuming.

## conclusion

This article has been stranded for several months. I wanted to continue writing after in-depth study, but due to the adjustment of my learning plan, I will not focus on the knowledge of data structure and type for the time being. However, data structure and algorithm must be learned. I will continue to work hard in this aspect after I learn what I need to learn well, and I will update a new chapter related to data structure and algorithm. If you are interested in data structures and algorithms, you can buy geek Time’s course “The Beauty of Data Structures and Algorithms” to learn, I believe you will benefit a lot after reading (the article is excerpted from the course).