树是一种分层数据的抽象模型。二叉树中的节点最多只能有两个子节点:一个是左侧子节点，另一个是右侧子节点。

## 二叉搜索树

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

### 插入

    const COMPARE = {
      less: -1,
      more: 1,
      equal: 0,
    }
    class Node {
    constructor(key) {
    this.key = key
    this.left = null
    this.right = null
    }
    }
    class BST {
    constructor(key) {
    this.root = null
    }
    // 插入
    insert(key) {
    if (this.root == null) {
    this.root = new Node(key)
    } else {
    this.insertNode(this.root, key)
    }
    }
    compareFn(a, b) {
    if (a === b) {
    return COMPARE.equal
    }
    return a &lt; b ? COMPARE.less : COMPARE.more
    
    }
    insertNode(node, key) {
    if (this.compareFn(key, node.key) === COMPARE.less) {
    if (node.left == null) {
    node.left = new Node(key)
    } else {
    this.insertNode(node.left, key)
    }
    } else {
    if (node.right == null) {
    node.right = new Node(key)
    } else {
    this.insertNode(node.right, key)
    }
    }
    }
    }
    const mytree = new BST()
    mytree.insert(100)
    mytree.insert(90)
    mytree.insert(110)
    mytree.insert(60)
    mytree.insert(80)
    console.log(mytree)

### 遍历

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

    // 中序遍历
    inOrderMap(cb) {
    this.inOrderMapNode(this.root, cb)
    }
    inOrderMapNode(node, cb) {
    if (node != null) {
    this.inOrderMapNode(node.left, cb)
    cb(node.key)
    this.inOrderMapNode(node.right, cb)
    }
    }
    mytree.inOrderMap((value) => {
    console.log(value)
    })

**先序遍历**是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

    // 先序遍历
    preOrderMap(cb) {
    this.preOrderMapNode(this.root, cb)
    }
    preOrderMapNode(node, cb) {
    if (node != null) {
    cb(node.key)
    this.preOrderMapNode(node.left, cb)
    this.preOrderMapNode(node.right, cb)
    }
    }
    mytree.preOrderMap((value) => {
    console.log(value)
    })

**后序遍历**则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小。

    // 后序遍历
    postOrderMap(cb) {
    this.postOrderMapNode(this.root, cb)
    }
    postOrderMapNode(node, cb) {
    if (node != null) {
    this.postOrderMapNode(node.left, cb)
    this.postOrderMapNode(node.right, cb)
    cb(node.key)
    }
    }
    mytree.postOrderMap((value) => {
    console.log(value)
    })

### 查询

    // 最小值
    min() {
    return this.minNode(this.root)
    }
    minNode(node) {
    let current = node
    while (current != null && current.left != null) {
    current = current.left
    }
    return current
    }
    // 最大值
    max() {
    return this.maxNode(this.root)
    }
    maxNode(node) {
    let current = node
    while (current != null && current.right != null) {
    current = current.right
    }
    return current
    }
    // 搜索某个值
    search(key) {
    return this.searchNode(this.root, key)
    }
    searchNode(node, key) {
    if (node == null) {
    return false
    }
    if (this.compareFn(key, node.key) === COMPARE.less) {
    return this.searchNode(node.left, key)
    } else if (this.compareFn(key, node.key) === COMPARE.more) {
    return this.searchNode(node.right, key)
    } else {
    return true
    }
    }

### 移除

    remove(key) {
    this.root = this.removeNode(this.root, key)
    }
    removeNode(node, key) {
    if (node == null) {
    return null
    }
    if (this.compareFn(key, node.key) === COMPARE.less) {
    node.left = this.removeNode(node.left, key)
    return node
    } else if (this.compareFn(key, node.key) === COMPARE.more) {
    node.right = this.removeNode(node.right, key)
    return node
    } else {
    // 第一种情况：叶节点
    if (node.left == null && node.right == null) {
    node = null
    return node
    }
    // 第二种情况：移除有一个左侧或右侧子节点的节点
    if (node.left == null) {
    node = node.right
    return node
    } else if (node.right == null) {
    node = node.left
    return node
    }
    // 第三种情况：移除有两个子节点的节点
    const target = this.minNode(node.right) //找到最小
    node.key = target.key
    node.right = this.removeNode(node.right, target.key)
    return node
    }
    }


JavaScript数据结构与算法(二叉搜索树)

    v1 = bin(25)  # 十进制转二进制
    print(v1)  # 0b11001
    
    v2 = oct(25)  # 十进制转八进制
    print(v2)  # 0o31
    
    v3 = hex(25)  # 十进制转十六进制
    print(v3)  # 0x19
    
    i1 = int("0b11001", base=2)
    print(i1)  # 25
    
    i2 = int("0o31", base=8)
    print(i2)  # 25
    
    i3 = int("0x19", base=16)
    print(i3)  # 25

手动转换：

    def to_bin(n):
    result = &quot;&quot;
    while n &gt; 0:
        result = str(n % 2) + result
        n //= 2
    return &quot;0b&quot; + result or &quot;0&quot;
    
    print(to_bin(2522))


Python进制转换

## 看刊宝

是一款安卓端软件，收录全网期刊杂志，国内外都有，里面的分类非常的全面，包括文学小说、文摘文萃、时政综合、商业财经、娱乐、军事、体育、美食、汽车等等，全部免费在线观看阅读，而且可以按照分类查看，还可以查看各本读物往期的版本，非常实用方便。

## 下载地址

看刊宝1.2.2版本：[https://gaga.lanzoum.com/iq2Ig17c822d](https://gaga.lanzoum.com/iq2Ig17c822d)
密码:3gkt


看刊宝-全网期刊杂志免费看

## 数组结构

参考：[http://8.129.6.198/post/173/](http://8.129.6.198/post/173/)

## 栈结构

栈(stack)又名堆栈，是一种运算受限的线性表，限定仅在表尾进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈，从一个栈删除元素称作出栈。

特点：**后进先出**，即 Last in First out (LIFO)。

    class Stack {
      #items = [] //# 符号声明私有属性，ES13 新特性
    pop() {
    return this.#items.pop() //出栈
    }
    push(data) {
    return this.#items.push(data) //进栈
    }
    peek() {
    return this.#items.at(-1) //栈顶
    }
    isEmpty() {
    return this.#items.length === 0
    }
    size() {
    return this.#items.length
    }
    clear() {
    this.#items = []
    }
    toString() {
    return this.#items.join(" ")
    }
    }
    // 十进制转 2 8 16 进制
    function convert(decNumber, base) {
    let remStack = new Stack()
    let number = decNumber
    let string = ""
    let baseString = "0123456789ABCDEF"
    while (number > 0) {
    remStack.push(number % base)
    number = Math.floor(number / base)
    }
    while (!remStack.isEmpty()) {
    string += baseString[remStack.pop()]
    }
    return string
    }
    convert(500, 16)

## 队列结构

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾（入队），进行删除操作的端称为队头（出队）。队列中没有元素时，称为空队列。

特点：先进先出，即 First in First out(FIFO)。

### 封装与应用

    class Queue {
    #items = {}
    #lowCount = 0
    #count = 0
    dequeue() {
    if (this.isEmpty()) {
    return undefined
    }
    let res = this.#items[this.#lowCount]
    delete this.#items[this.#lowCount]
    this.#lowCount++
    return res //出队
    
    }
    enqueue(data) {
    this.#items[this.#count] = data //入队
    this.#count++
    }
    front() {
    return this.#items[this.#lowCount] //队头
    }
    isEmpty() {
    return this.size() === 0
    }
    size() {
    return this.#count - this.#lowCount
    }
    clear() {
    this.#items = {}
    this.#count = 0
    this.#lowCount = 0
    }
    toString() {
    let str = ""
    for (let i = this.#lowCount; i < this.#count; i++) {
    str += ${this.#items[i]} 
    }
    return str
    
    }
    }
    // 击鼓传花游戏
    function game(list, num) {
    let queue = new Queue()
    for (let i = 0; i < list.length; i++) {
    queue.enqueue(list[i])
    }
    while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
    queue.enqueue(queue.dequeue())
    }
    console.log(queue.dequeue(), &quot;淘汰了&quot;)
    
    }
    return queue.dequeue() + " 获胜"
    }
    game(["张三", "李四", "王五", "赵六", "孙七"], 7)

### 双端队列

    class DeQueue {
    #items = {}
    #lowCount = 0 //队头索引
    #count = 0
    removeFront() {
    if (this.isEmpty()) {
    return undefined
    }
    let res = this.#items[this.#lowCount]
    delete this.#items[this.#lowCount]
    this.#lowCount++
    
    return res
    
    }
    removeBack() {
    if (this.isEmpty()) {
    return
    }
    this.#count--
    const res = this.#items[this.#count]
    delete this.#items[this.#count]
    
    return res
    
    }
    addFront(data) {
    if (this.isEmpty()) {
    this.addBack(data)
    } else {
    if (this.#lowCount > 0) {
    this.#lowCount--
    this.#items[this.#lowCount] = data
    } else {
    // #lowCount=0
    for (let i = this.#count; i > 0; i--) {
    this.#items[i] = this.#items[i - 1]
    }
    }
    }
    }
    addBack(data) {
    this.#items[this.#count] = data
    this.#count++
    }
    peekFront() {
    return this.#items[this.#lowCount]
    }
    peekBack() {
    return this.#items[this.#count - 1]
    }
    isEmpty() {
    return this.size() === 0
    }
    size() {
    return this.#count - this.#lowCount
    }
    clear() {
    this.#items = {}
    this.#count = 0
    this.#lowCount = 0
    }
    toString() {
    let str = ""
    for (let i = this.#lowCount; i < this.#count; i++) {
    str += ${this.#items[i]} 
    }
    return str
    
    }
    }
    // 回文字符串检查
    function test(str) {
    const lowstr = str.toLocaleLowerCase().split(" ").join("")
    let dequeue = new DeQueue()
    for (let i = 0; i < lowstr.length; i++) {
    dequeue.addBack(lowstr[i])
    }
    let isEqual = true
    while (dequeue.size() > 1) {
    if (dequeue.removeFront() != dequeue.removeBack()) {
    isEqual = false
    break
    }
    }
    return isEqual
    }
    test("上海自来水来自海上")

## 链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

**链表的特点**

1. 插入、删除数据效率高O(1)级别(只需更改指针指向即可)，随机访问效率低O(n)级别(需要从链头至链尾进行遍历)
2. 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

### 单链表

每个节点只包含一个指针，即后继指针。

    class Node {
    constructor(element) {
    this.element = element
    this.next = null
    }
    }
    class LinkedList {
    constructor() {
    this.count = 0
    this.head = null
    }
    push(element) {
    const node = new Node(element)
    if (this.head === null) {
      this.head = node
    } else {
      let current = this.head
    
      while (current.next !== null) {
        current = current.next
      }
    
      current.next = node
    }
    
    this.count++
    
    }
    getNodeAt(index) {
    if (index >= 0 && index < this.count) {
    let node = this.head
    for (let i = 0; i < index; i++) {
    node = node.next
    }
      return node
    }
    
    return
    
    }
    // 指定位置删除
    removeAt(index) {
    if (index >= 0 && index < this.count) {
    let current = this.head
    if (index === 0) {
    this.head = this.head.next
    } else {
    let previous = this.getNodeAt(index - 1)
    current = previous.next
    previous.next = current.next
    }
      this.count--
      return current.element
    }
    
    return
    
    }
    equalFn(a, b) {
    return JSON.stringify(a) === JSON.stringify(b)
    }
    indexOf(element) {
    let current = this.head
    for (let i = 0; i < index; i++) {
    if (this.equalFn(element, current.element)) {
    return i
    }
    current = current.next
    }
    return -1
    
    }
    // 指定元素删除
    remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
    }
    insert(element, index) {
    if (index >= 0 && index <= this.count) {
    const node = new Node(element)
    if (index === 0) {
    const current = this.head
    node.next = current
    this.head = node
    } else {
    const previous = this.getNodeAt(index - 1)
    const current = previous.next
        node.next = current
        previous.next = node
      }
    
      this.count++
      return true
    }
    
    return false
    
    }
    isEmpty() {
    return this.size() === 0
    }
    size() {
    return this.count
    }
    getHead() {
    return this.head
    }
    }
    // 回文字符串检查
    function test(str) {
    const lowstr = str.toLocaleLowerCase().split(" ").join("")
    let sll = new LinkedList()
    for (let i = 0; i < lowstr.length; i++) {
    sll.push(lowstr[i])
    }
    let isEqual = true
    while (sll.size() > 1) {
    if (sll.removeAt(0) !== sll.removeAt(sll.size() - 1)) {
    isEqual = false
    break
    }
    }
    return isEqual
    }
    test("上海自来水来自海上")

击鼓传花游戏使用单链表：

    // 击鼓传花游戏
    function game(list, num) {
    let queue = new LinkedList()
    for (let i = 0; i < list.length; i++) {
    queue.push(list[i])
    }
    while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
    queue.push(queue.removeAt(0))
    }
    console.log(queue.removeAt(0), &quot;淘汰了&quot;)
    
    }
    return queue.removeAt(0) + " 获胜"
    }
    game(["张三", "李四", "王五", "赵六", "孙七"], 7)

十进制转 2 8 16 进制：

    // 十进制转 2 8 16 进制
    function convert(decNumber, base) {
    let remStack = new LinkedList()
    let number = decNumber
    let string = ""
    let baseString = "0123456789ABCDEF"
    while (number > 0) {
    remStack.push(number % base)
    number = Math.floor(number / base)
    }
    while (!remStack.isEmpty()) {
    string += baseString[remStack.removeAt(remStack.size() - 1)]
    }
    return string
    }
    convert(500, 16)

### 双链表

    class DoublyNode extends Node {
    constructor(element) {
    super(element)
    this.prev = null
    }
    }
    class DoublyLinkedList extends LinkedList {
    constructor() {
    super()
    this.tail = null
    }
    push(element) {
    const node = new DoublyNode(element)
    if (this.head === null) {
    this.head = node
    this.tail = node
    } else {
    this.tail.next = node
    node.prev = this.tail
    this.tail = node
    }
    this.count++
    
    }
    remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
    }
    insert(element, index) {
    if (index >= 0 && index <= this.count) {
    const node = new DoublyNode(element)
    let current = this.head
    if (index === 0) {
    if (this.head === null) {
    this.head = node
    this.tail = node
    } else {
    node.next = this.head
    this.head.prev = node
    this.head = node
    }
    } else if (index === this.count) {
    current = this.tail
    current.next = node
    node.prev = current
    this.tail = node
    } else {
    const previous = this.getNodeAt(index - 1)
    current = previous.next
        node.next = current
        current.prev = node
        previous.next = node
        node.prev = previous
      }
    
      this.count++
      return true
    }
    
    return false
    
    }
    removeAt(index) {
    if (index >= 0 && index < this.count) {
    let current = this.head
    if (index === 0) {
    this.head = current.next
    if (this.count === 1) {
    this.tail = null
    } else {
    this.head.prev = null
    }
    } else if (index === this.count - 1) {
    current = this.tail
    this.tail = current.prev
    this.tail.next = null
    } else {
    let previous = this.getNodeAt(index - 1)
    current = previous.next
    previous.next = current.next
    current.next.prev = previous
    }
      this.count--
      return current.element
    }
    
    return
    
    }
    getHead() {
    return this.head
    }
    getTail() {
    return this.tail
    }
    }

### 循环链表

循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针(tail.next)不是undefined，而是指向第一个元素(head)。

    class CircularLinkedList extends LinkedList {
    constructor() {
    super()
    }
    push(element) {
    const node = new Node(element)
    let current
    if (this.head === null) {
    this.head = node
    } else {
    current = this.getNodeAt(this.size() - 1)
    current.next = node
    }
    node.next = this.head
    this.count++
    
    }
    insert() {
    if (index >= 0 && index <= this.count) {
    const node = new Node(element)
    let current = this.head
    if (index === 0) {
    if (this.head === null) {
    this.head = node
    node.next = this.head
    } else {
    node.next = current
    this.head = node
          current = this.getNodeAt(this.size() - 1)
          current.next = this.head
        }
      } else {
        const previous = this.getNodeAt(index - 1)
        node.next = previous.next
        previous.next = node
      }
    
      this.count++
      return true
    }
    
    return false
    
    }
    removeAt(index) {
    if (index >= 0 && index < this.count) {
    let current = this.head
    if (index === 0) {
    if (this.size() === 1) {
    this.head = null
    } else {
    let last = this.getNodeAt(this.size() - 1)
    this.head = this.head.next
    last.next = this.head
    }
    } else {
    const previous = this.getNodeAt(index - 1)
    current = previous.next
    previous.next = current.next
    }
      this.count--
      return current.element
    }
    
    return
    
    }
    }


JavaScript数据结构与算法

## 工程结构

在Python中，最顶级的叫做包，包 → 模块 → 类 → 方法、变量。

- 模块（module），一个py文件，模块名就是文件名
- 包（package），含有多个py文件的文件夹，只有包含了`__init__.py`模块的文件夹才能成为包

包中的`__init__.py`文件默认内容为空，一般用于描述当前包的信息（在导入包下面的模块时，会自动加载）。

## 导入

导入，其实就是将模块或包加载到内存中，以后再去内存中拿就行。在Python内部默认设置了一些路径，导入模块或包时，都会按照指定顺序逐一去特定的路径查找。

如果想要导入任意的模块或包，可以手动在sys.path中添加指定路径，然后再导入，例如：

    import sys
    sys.path.append("指定路径")
    import xxx # 导入指定路径下的一个xxx.py文件

### all列表

如果一个模块文件中有__all__变量，当使用 from xxx import * 导入时，只能导入这个列表中的元
素。

使用`from 包名 import *`必须在__init__.py文件中添加`**all** = []`，控制允许导入的模块列表。

## 主文件

执行一个py文件时：`**name** == "**main**"`；导入一个py文件时：`**name** == "模块名"`。`**name**`有2个作用：

- 作为这个模块的入口，类似其他语言中的main函数
- 作为调试使用

## 搜索顺序

导入模块时，先搜索当前目录指定模块名的文件，如果有就直接导入；如果没有，再搜索系统目录。

模块一般都有一个内置属性__file__，可查看模块的完整路径。

## **init**.py

要在外界使用包中的模块，需在__init__.py中指定对外界提供的模块列表：

    # 从当前目录导入模块列表
    from . import 模块名
    from . import 模块名


Python模块和包

这里是 aboss.top 的自留地。写了十几年野路子代码，攒了些摸爬滚打的经验，做成系列课程慢慢讲；也留了一小块地方，记记代码之外的胡思乱想。