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

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

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

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

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

实现这个树的代码：

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