一线大厂高级前端编写,前端初中阶面试题,帮助初学者应聘,需要联系微信:javadudu

JS中树的实现以及二叉树的遍历

树是一种数据结构,而二叉树是一种特殊的树形结构。

树是由若干个节点和它们之间的连接组成,其中一个节点被指定为根节点。每个节点可以有多个子节点,但每个节点最多只有一个父节点。树的节点可以没有子节点,这样的节点称为叶子节点。树的深度是指从根节点到某个节点的路径长度,树的高度是指树中任意节点的最大深度。

二叉树是一种特殊的树形结构,每个节点最多只有两个子节点,分别称为左子节点和右子节点。二叉树的子节点位置不能交换,即左子节点始终在右子节点的左侧。二叉树的遍历方式有前序遍历、中序遍历和后序遍历,可以用来实现树的搜索、排序等算法。

在 JavaScript 中,可以使用对象来实现树的数据结构。

JS中树的实现以及二叉树的遍历

实现这个树的代码:

function TreeNode(val) {
    this.val = val
    this.left = null
    this.right = null
}
let node = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val:'D',
        },
        right: {
            val:'E',
        },
    },
    right: {
        val:'C',
        left:null,
        right:{
            val:'F'
        },
    }
    }

二叉树的遍历

二叉树的遍历是指按照一定的规则访问二叉树中的所有节点,可以分为三种方式:前序遍历、中序遍历和后序遍历。

  • 前序遍历

前序遍历就是先访问根节点,然后递归地遍历左子树,最后递归地遍历右子树。

function preorderTraversal(node) {
    if (!node) return[]

    let res = []
    res.push(node.val);// 先将根节点push到数组中
    let L=preorderTraversal(node.left); // 遍历左子树
    let r=preorderTraversal(node.right); // 遍历右子树
    return res.concat(L).concat(r)//拼接
}
console.log(preorderTraversal(node));

  • 中序列遍历

中序遍历就是先递归地遍历左子树,然后访问根节点,最后递归地遍历右子树。

function preorderTraversal(node) {
    if (!node) return[]
    let res = []
    
    let L=preorderTraversal(node.left); // 遍历左子树
    res.push(node.val);// 将根节点push到数组中
    let r=preorderTraversal(node.right); // 遍历右子树
    return L.concat(res).concat(r)
}
console.log(preorderTraversal(node));

  • 后序遍历

后序遍历就是先递归地遍历左子树,然后递归地遍历右子树,最后访问根节点。

function preorderTraversal(node) {
    if (!node) return[]
    let res = []
    
    let L=preorderTraversal(node.left); // 遍历左子树
    let r=preorderTraversal(node.right); // 遍历右子树
    res.push(node.val);// 先访问根节点
    return L.concat(r).concat(res)
}
console.log(preorderTraversal(node));

  • 用迭代的方法遍历树
var preorderTraversal = function (root) {
    if (!root) return []
    // 合理安排入栈和出栈的顺序
    const res = []
    const stack = []
    stack.push(root)
    while (stack.length > 0) {
        const cur = stack.pop()
        res.push(cur.val)

        if (cur.right) {
            stack.push(cur.right)
        }
        if (cur.left) {
            stack.push(cur.left)
        }
    }
    return res
}

总结

树这一数据结构可以提供一种有效的方式来组织、操作和分析具有层次关系的数据。它在许多领域都有广泛的应用,是计算机科学中重要的基础数据结构之一。

掌握和理解树这一数据结构对于计算机科学和软件开发非常重要。它是许多实际问题的基础,提高算法效率的关键,深入理解递归的基础,扩展其他数据结构的手段,以及培养问题解决能力的工具之一。

原文链接:https://juejin.cn/post/7325495601269080073 作者:Yhuh

(0)
上一篇 2024年1月19日 下午4:53
下一篇 2024年1月19日 下午5:03

相关推荐

发表评论

登录后才能评论