关于前端:js中的二叉树

二叉树

原文链接：https://note.noxussj.top/?source=sifo

什么是二叉树？

树中每个节点最多只能有两个子节点，在 JavaScript 中个别都是通过 Object 来模仿二叉树。

罕用操作

• 前序遍历
• 中序遍历
• 后序遍历

前序遍历

根左右。

口诀：

1. 拜访根节点
2. 对根节点的左子树进行前序遍历
3. 对根节点的右子树进行前序遍历

通过递归形式实现

    function preorder(root) {    if (!root) return        console.log(root.val)    preorder(root.left)    preorder(root.right)    }

通过迭代形式实现

    function preorder(root) {    if (!root) return        const stack = [root]        while (stack.length) {    const n = stack.pop()        console.log(n)    if (n.right) stack.push(n.right)    if (n.left) stack.push(n.left)    }    }

中序遍历

左根右。

口诀：

1. 对根节点的左子树进行中序遍历
2. 拜访根节点
3. 对根节点的右子树进行中序遍历

通过递归形式实现

    function inorder(root) {    if (!root) return        inorder(root.left)    console.log(root.val)    inorder(root.right)    }

通过迭代形式实现

    function inorder(root) {        if (!root) return            const stack = [root]            while (stack.length) {            const n = stack.pop()                console.log(n)            if (n.right) stack.push(n.right)            if (n.left) stack.push(n.left)        }    }

后序遍历

左右根。

口诀：

1. 对根节点的左子树进行后序遍历
2. 对根节点的右子树进行后序遍历
3. 拜访根节点

通过递归形式实现

    function postorder(root) {        if (!root) return            postorder(root.left)        postorder(root.right)        console.log(root.val)    }    

通过迭代形式实现

    function postorder(root) {        if (!root) return            const outputStack = []        const stack = [root]            while (stack.length) {            const n = stack.pop()                outputStack.push(n)            if (n.left) stack.push(n.left)            if (n.right) stack.push(n.right)        }            while (outputStack.length) {            const n = outputStack.pop()            console.log(n.val)        }    }

原文链接：https://note.noxussj.top/?source=sifo