数据结构

二叉树

满二叉树

一个二叉树，每一层的结点数都达到了最大值。

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树

二叉查找树

左结点小于根结点，右结点大于根结点。子树也如此。

平衡二叉树

左右子树的高度差不能大于1。子树也如此。

通过旋转结点来保持二叉树的平衡。

二叉树的创建

class Node {
    constructor(data, left, right) {
        Object.assign(this, {
            data,
            left,
            right
        })
    }
}

class BST {
    constructor() {
        this.root = null
    }

    insert(data) {
        let node = new Node(data)
        if (!this.root) {
            this.root = node
        }
        else {
            let current = this.root
            while (true) {
                if (data < current.data) {
                    if (current.left) {
                        current = current.left
                    }
                    else {
                        current.left = node
                        break
                    }
                }
                else {
                    if (current.right) {
                        current = current.right
                    }
                    else {
                        current.right = node
                        break
                    }
                }
            }
        }
    }
}


// 使用
let tree = new BST()
tree.insert(10)
tree.insert(20)
tree.insert(15)
tree.insert(12)
tree.insert(5)

树的遍历

二叉树的递归遍历

// 递归的先序遍历
function preOrder (node, cb) {
    if (node) {
        cb(node.data)
        preOrder(node.left, cb)
        preOrder(node.right, cb)
    }
}

// 递归的中序遍历
function inOrder (node, cb) {
    if (node) {
        inOrder(node.left, cb)
        cb(node.data)
        inOrder(node.right, cb)
    }
}

// 递归的后序遍历
function postOrder (node, cb) {
    if (node) {
        postOrder(node.left, cb)
        postOrder(node.right, cb)
        cb(node.data)
    }
}

二叉树的非递归遍历

// 非递归的先序遍历
function preOrder(node) {
    let stack = [], res = []
    stack.push(node)
    while (stack.length > 0) {
        let node = stack.pop()
        res.push(node.data)
        if (node.right) {
            stack.push(node.right)
        }
        if (node.left) {
            stack.push(node.left)
        }
    }
    return res
}

// 非递归的中序遍历
function inOrder(node) {
    let stack = [], res = []
    while (stack.length > 0 || node) {
        if (node) {
            stack.push(node)
            node = node.left
        } else {
            node = stack.pop()
            res.push(node.data)
            node = node.right
        }
    }
    return res
}

// 非递归的后序遍历 方法1
function postOrder(node, cb) {
    let stack = []
    let res = []
    while (stack.length > 0 || node) {
        res.unshift(node.data)
        if (node.right) {
            stack.push(node.right)
        }
        if (node.left) {
            stack.push(node.left)
        }
        node = stack.pop()
    }
    return res
}

// 方法2，其实就是在先序遍历的基础上把返回数组进行reverse处理
function postOrder(node) {
    let stack = [], res = []
    stack.push(node)
    while (stack.length > 0) {
        let node = stack.pop()
        res.push(node.data)
        if (node.left) {
            stack.push(node.left)
        }
        if (node.right) {
            stack.push(node.right)
        }
    }
    return res.reverse()
}

深度优先遍历

递归的深度优先遍历

function DFS(node, nodeList = []) {
    if (node !== null) {
        nodeList.push(node)
        let children = node.children
        for (let i = 0; i < children.length; i++) {
            DFS(children[i], nodeList)
        }
    }
    return nodeList
}

非递归的深度优先遍历

function DFS(node) {
    let nodes = []
    let stack = []
    stack.push(node)

    while(stack.length) {
        let item = stack.pop()
        let children = item.children
        nodes.push(item)
        // node = [] stack = [parent]
        // node = [parent] stack = [child3,child2,child1]
        // node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
        // node = [parent, child1, child1-1] stack = [child3,child2,child1-2]
        for (let i = children.length - 1; i >= 0; i--) {
            stack.push(children[i])
        }
    }
    return nodes
}

广度优先遍历

function BFS(node) {
    let nodes = []
    let stack = []
    stack.push(node)
    while(stack.length) {
        let item = stack.shift()
        let children = item.children
        nodes.push(item)
        // 队列，先进先出
        // nodes = [] stack = [parent]
        // nodes = [parent] stack = [child1,child2,child3]
        // nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
        // nodes = [parent,child1,child2] stack = [child3, ...]
        for (let i = 0; i < children.length; i++) {
            stack.push(children[i])
        }
    }

    return nodes
}

链表

链表的建立

class Node {
    constructor(data) {
        this.next = null
        this.data = data
    }
}

class List {
    constructor() {
        this.head = null
        this.length = 0
    }

    append(data) {
        let node = new Node(data)
        if (this.head) {
            let current = this.head
            while(current.next !== null) {
                current = current.next
            }
            current.next = node
        }
        else {
            this.head = node
        }
        this.length++
    }

    insert(data, position) {
        let node = new Node(data)
        if (position >= 0 && position <= this.length) {
            let currentNode = this.head
            let previousNode = null
            let index = 0
            if ( position === 0 ) {
                node.next = this.head
                this.head = node
            }
            else {
                while( index++ < position ) {
                    previousNode = currentNode
                    currentNode = currentNode.next
                }
                previousNode.next = node
                node.next = currentNode
            }
            this.length++
        }
    }

    size() {
        return this.length
    }

    isEmpty() {
        return this.length === 0
    }
}

let list = new List()

反转单向链表

function reverseList(list) {
    let head = list.head
    let currentNode = head
    let pre
    while (currentNode) {
        let nextNode = currentNode.next
        currentNode.next = pre
         pre = currentNode
         currentNode = nextNode
    }
    return pre
}