关于前端:二叉树一-遍历

什么是二叉树

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具备左右秩序，不能随便颠倒。
二叉树的第i层至少有2^{i-1}个结点；
深度为k的二叉树至少有2^k-1个结点；
对任何一棵二叉树T，若树叶总数为 n_0，分支度为2的总数为n_2，则n_0=n_2+1。
一棵深度为k，且有2^k-1个节点称之为满二叉树；
深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为齐全二叉树。

非凡类型

深度优先遍历

英文缩写为DFS即Depth First Search。 在深度优先级中，咱们心愿从根结点拜访最远的结点。前序，中序和后序遍历都是深度优先遍历的特例。

先来看一张图, 一眼理解这三种遍历:

作为前端, 我是必定先用 JS 来实现这些遍历的, 先定义一个二叉树的构造:

 const nodes = {
    node: 6,
    left: {
        node: 5,
        left: {
            node: 4
        },
        right: {
            node: 3
        }
    },
    right: {
        node: 2,
        right: {
            node: 1
        }
    }
}

先序遍历

let list = []

function preOrder(node) {
    if (!(node == null)) {
        list.push(node.node);
        preOrder(node.left);
        preOrder(node.right);
    }
}

执行: preOrder(nodes)

打印 list 后果: [6, 5, 4, 3, 2, 1]

中序遍历

let list = []

function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);
        list.push(node.node);
        inOrder(node.right);
    }
}

执行: inOrder(nodes)

打印 list 后果: [4, 5, 3, 6, 2, 1]

后序遍历

let list = []

function postOrder(node) {
    if (!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        list.push(node.node);
    }
}

执行: postOrder(nodes)

打印 list 后果: [4, 3, 5, 1, 2, 6]

广度优先遍历

英文缩写为BFS即Breadth FirstSearch。其过程测验来说是对每一层节点顺次拜访，拜访完一层进入下一层，而且每个节点只能拜访一次。 广度遍历即咱们寻常所说的档次遍历。

const levelOrder = function (root) {
    if (root == null) {
        return []
    }
    let result = []
    let queue = [root]
    while (queue.length) {
        // 每一层的节点数
        let level = queue.length
        let currLevel = []
        // 每次遍历一层元素
        for (let i = 0; i < level; i++) {
            // 以后拜访的节点出队
            let curr = queue.shift()
            curr.left && queue.push(curr.left)
            curr.right && queue.push(curr.right)
            currLevel.push(curr.node)
        }
        result.push.apply(result, currLevel)
    }
    return result
}

打印后果: [6, 5, 2, 4, 3, 1]
currLevel 中的打印: [6] [5,2] [4,3,1]

这个思路比拟好了解, 倒是还不够好

优化

const levelOrder = function (root) {
    if (!root) return [];
    let queue = [root];
    let res = [];
    while (queue.length) {
        let item = queue.shift();
        res.push(item.node);
        item.left && queue.push(item.left);
        item.right && queue.push(item.right);
    }
    return res;
}

打印后果: [6, 5, 2, 4, 3, 1]

这种算法只是用了一个队列, 成果较好

总结

这是二叉树相干的第一篇, 比拟根底, 后续还会更新

仓库地址: https://github.com/Grewer/notes

参考:

• https://zh.wikipedia.org/wiki…
• https://blog.csdn.net/weixin_…

相干系列

• 二叉树(一): 遍历
• 二叉树(二): 补充
• 二叉树(三): 二叉查找树