当前位置： 首页 > article >正文

Javascript数据结构——二叉树篇

article 2024/12/24 20:03:36

二叉树内容详解

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树常用于实现数据结构如堆、二叉搜索树等，以及算法如快速排序、表达式树等。

基本术语
  • 根节点：二叉树的起始节点。
  • 子节点：一个节点的直接后继节点，分为左子节点和右子节点。
  • 父节点：一个节点的直接前驱节点。
  • 叶子节点：没有子节点的节点。
  • 深度（高度）：从根节点到最远叶子节点的最长路径上的节点数。
  • 层次（Level）：根节点在第1层，根的子节点在第2层，以此类推。
常见类型
  • 完全二叉树：除了最后一层外，每一层都是满的，并且最后一层的节点都靠左对齐。
  • 满二叉树：除了叶子节点外，每个节点都有两个子节点。
  • 二叉搜索树（BST）：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
常见应用场景

在前端开发中，二叉树作为一种重要的数据结构，具有广泛的应用。以下是一些主要的应用场景：

  1. 数据的组织与搜索：

    • 二叉搜索树（BST）是一种常见的二叉树，它可以快速地查找、插入和删除数据。通过比较节点的值，可以有效地定位数据项，这在数据库索引和搜索引擎等领域很有用。例如，在一个包含许多单词的二叉搜索树中搜索一个特定的单词，可以快速定位到该单词并提供相关信息。

  2. 排序：

    • 二叉树可以用于实现一些排序算法。例如，通过构建二叉搜索树并进行中序遍历，可以获得有序的数据。具体地，对一组数字进行排序，将它们构建成二叉搜索树，然后进行中序遍历，即可得到有序的数字序列。

  3. 表达式求值：

    • 二叉树可以用于表示数学表达式，并对其进行求值。在这种情况下，二叉树的每个节点表示一个运算符或操作数，而节点的子节点表示操作数。表达式树就是一种用于表示数学表达式的二叉树，它可以帮助进行表达式求值和运算。例如，将数学表达式如“(3 + 4) * 5”表示成对应的二叉树结构，便于进行运算和求值。

  4. 图形处理：

    • 在计算机图形学中，二叉树结构可以用来表示场景图或层次结构，例如场景中的物体组织结构。例如，用二叉树表示一个计算机游戏中的场景，每个节点代表一个物体或者一个场景元素，并用树的结构表示它们之间的层次关系。

  5. 实现决策树：

    • 在机器学习中，决策树是一种重要的算法，它可以用于分类和回归问题。在这种情况下，二叉树被用来表示决策过程，每个节点表示一个决策条件，而子节点表示不同的结果。

  6. 数据压缩：

    • 在数据压缩中，二叉树可以用于编码和解码数据。在这种情况下，二叉树的每个节点表示一个符号或一组符号的编码，而子节点表示编码的上下文。

  7. 编译器中的应用：

    • 在编译器中，二叉树被用来表示源代码的结构，并对源代码进行语法分析和语义分析。在这种情况下，二叉树的每个节点表示一个语法或语义结构，而子节点表示语法或语义规则。

此外，二叉树还有其他一些应用，如用于解决任意两个节点的最小祖先问题（如二叉树的最近公共祖先问题）等。这些应用展示了二叉树在前端开发中的多样性和重要性。

总的来说，二叉树作为一种高效的数据结构，在前端开发中发挥着重要作用，它能够帮助开发者更好地组织、搜索、排序和处理数据，从而提高应用程序的性能和用户体验。

常见算法题目及代码

以下是常见的二叉树算法题目及其实现代码（使用JavaScript）。

1. 前序遍历（Preorder Traversal）
function preorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node) {
            result.push(node.val);
            traverse(node.left);
            traverse(node.right);
        }
    }
    traverse(root);
    return result;
}
2. 中序遍历（Inorder Traversal）
function inorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node) {
            traverse(node.left);
            result.push(node.val);
            traverse(node.right);
        }
    }
    traverse(root);
    return result;
}
3. 后序遍历（Postorder Traversal）
function postorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node) {
            traverse(node.left);
            traverse(node.right);
            result.push(node.val);
        }
    }
    traverse(root);
    return result;
}
4. 层次遍历（Level Order Traversal）
function levelOrderTraversal(root) {
    let result = [];
    if (!root) return result;
    let queue = [root];
    while (queue.length) {
        let level = [];
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            level.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(level);
    }
    return result;
}
5. 判断二叉树是否为空
function isEmpty(root) {
    return root === null;
}
6. 二叉树的深度
function maxDepth(root) {
    if (!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
7. 二叉树的最小深度
function minDepth(root) {
    if (!root) return 0;
    if (!root.left && !root.right) return 1;
    if (!root.left) return minDepth(root.right) + 1;
    if (!root.right) return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
8. 翻转二叉树
function invertTree(root) {
    if (!root) return null;
    let temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);
    return root;
}
9. 二叉搜索树中的最小值
function minValue(root) {
    let current = root;
    while (current.left) {
        current = current.left;
    }
    return current.val;
}
10. 二叉搜索树中的最大值
function maxValue(root) {
    let current = root;
    while (current.right) {
        current = current.right;
    }
    return current.val;
}
11. 查找二叉树中的值
function search(root, val) {
    if (!root || root.val === val) return root;
    return search(root.left, val) || search(root.right, val);
}
12. 插入到二叉搜索树
function insertIntoBST(root, val) {
    if (!root) return { val, left: null, right: null };
    if (val < root.val) root.left = insertIntoBST(root.left, val);
    else root.right = insertIntoBST(root.right, val);
    return root;
}
13. 删除二叉搜索树中的节点
function deleteNode(root, val) {
    if (!root) return null;
    if (val < root.val) root.left = deleteNode(root.left, val);
    else if (val > root.val) root.right = deleteNode(root.right, val);
    else {
        if (!root.left) return root.right;
        if (!root.right) return root.left;
        let temp = minValueNode(root.right);
        root.val = temp.val;
        root.right = deleteNode(root.right, temp.val);
    }
    return root;
}

function minValueNode(node) {
    let current = node;
    while (current.left) {
        current = current.left;
    }
    return current;
}
14. 路径和等于给定值的路径
function pathSum(root, sum) {
    let result = [];
    function traverse(node, path, currentSum) {
        if (!node) return;
        path.push(node.val);
        currentSum += node.val;
        if (!node.left && !node.right && currentSum === sum) result.push([...path]);
        traverse(node.left, path, currentSum);
        traverse(node.right, path, currentSum);
        path.pop();
    }
    traverse(root, [], 0);
    return result;
}
15. 判断是否为平衡二叉树
function isBalanced(root) {
    if (!root) return true;
    function getHeight(node) {
        if (!node) return 0;
        let leftHeight = getHeight(node.left);
        let rightHeight = getHeight(node.right);
        if (leftHeight === -1 || rightHeight === -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
    return getHeight(root) !== -1;
}
16. 二叉树的镜像
function mirrorTree(root) {
    if (!root) return null;
    [root.left, root.right] = [mirrorTree(root.right), mirrorTree(root.left)];
    return root;
}
17. 二叉树的根到叶子节点之和
function sumRootToLeaf(root) {
    function traverse(node, sum) {
        if (!node) return 0;
        sum = (sum << 1) + node.val;
        if (!node.left && !node.right) return sum;
        return traverse(node.left, sum) + traverse(node.right, sum);
    }
    return traverse(root, 0);
}

http://www.kler.cn/a/449745.html

相关文章：

  • 顶顶通呼叫中心中间件mod_cti模块安全增强，预防盗打风险(mod_cti基于FreeSWITCH)
  • 我用Cursor+DeepSeek做了个飞书文档一键同步插件，免费使用！
  • RabbitMQ 的7种工作模式
  • react中使用ResizeObserver来观察元素的size变化
  • 0009.基于springboot+layui的ERP企业进销存管理系统
  • 如何利用Python爬虫获得1688按关键字搜索商品
  • 微信小程序xr-frame透明视频实现
  • 服务器证书原理
  • WebContainerapi 基础（Web IDE 技术探索 一）
  • DevOps工程技术价值流：制品库Nexus与Harbor的实战探索
  • 重温设计模式--适配器模式
  • Spring - 12 ( 7000 字 Spring 入门级教程 )
  • Echarts之yAxis属性超超超级详情版学习
  • 灵当CRM getMyAmbassador SQL注入漏洞复现
  • Unity3D VFX事件系统详解
  • 在 Docker 中部署 Jenkins，并完成项目的构建和发布
  • 【C#】List求并集、交集、差集
  • Postman接口测试工具使用详解
  • 中国信通院致信感谢易保全：肯定贡献能力，期许未来合作
  • 【QSS样式表 - ⑥】：QPushButton控件样式
  • nginx采用域名访问后台接口时报400
  • git管理
  • Canoe E2E校验自定义Checksum算法
  • sed正则表达式元字符 和使用示例 sed变量替换示例
  • python3.6搭建pytorch环境
  • MySQL体系架构