前端之数据结构（五）二叉树

Augus

关注

发布于: 1 小时前

上一章介绍的树的基本概念，并简单说了一下深度优先遍历和广度优先遍历。

这一章就来介绍一下树的另一种结构 二叉树 , 并唠唠它的先中后序遍历。

二叉树

树中每个节点最多只能有两个子节点。
下图就是一个现实中存在的二叉树，每个节点下都有两个字节点。说实话挺佩服拍照的人的，竟然真在现实生活中找到真实的二叉树。

在 JS 中通常用 Object 来模拟二叉树。如下代码：

const binaryTree = {    val: 1,    left: {        val: 2,        left: null,        right: null    }    right: {        val: 3,        left: null,        right: null    }}

复制代码

就是一个简单的一个通过 JS Object 模拟的二叉树。

先序遍历

访问根节点。
对根节点的左子树进行先序遍历。
对根节点的右子树进行先序遍历。

代码如下：

const binaryTree = {    val: 1,    left: {        val: 2,        left: {            val: 3,            left: null,            right: null        },        right: {            val: 4,            left: {                val: 5,                left: null,                right: null            },            right: null        }    },    right: {        val: 6,        left: null,        right: {            val: 7,            left: null,            right: null        }    }}

复制代码

进行线序遍历：

const preorder = (root) => {    if (!root) return    console.log(root.val)    preorder(root.left)    preorder(root.right)}
preorder(binaryTree)
// 1 2 3 4 5 6 7

复制代码

中序遍历

对根节点的左子树进行中序遍历。
访问根节点。
对根节点的右子树进行中序遍历。

代码如下：

const binaryTree = {    val: 5,    left: {        val: 2,        left: {            val: 1,            left: null,            right: null        },        right: {            val: 4,            left: {                val: 3,                left: null,                right: null            },            right: null        }    },    right: {        val: 6,        left: null,        right: {            val: 7,            left: null,            right: null        }    }}

复制代码

进行中序遍历：

const inorder = (root) => {    if (!root) return    inorder(root.left)    console.log(root.val)    inorder(root.right)}
inorder(binaryTree)// 1 2 3 4 5 6 7

复制代码

后序遍历

对根节点的左子树进行中序遍历。
对根节点的右子树进行中序遍历。
访问根节点。

代码结构如下：

const binaryTree = {    val: 7,    left: {        val: 4,        left: {            val: 1,            left: null,            right: null        },        right: {            val: 3,            left: {                val: 2,                left: null,                right: null            },            right: null        }    },    right: {        val: 6,        left: null,        right: {            val: 5,            left: null,            right: null        }    }}

复制代码

进行后序遍历：

const postorder = (root) => {    if (!root) return    postorder(root.left)    postorder(root.right)    console.log(root.val)}
postorder(binaryTree)// 1 2 3 4 5 6 7

复制代码

End~~~

发布于: 1 小时前阅读数: 4

Augus

关注

爱瞎搞的软件开发工程师 2021.06.10 加入

某摸鱼集团

发布

暂无评论

创作场景

前端之数据结构（五）二叉树

二叉树

先序遍历

中序遍历

后序遍历

Augus

评论