首页 > 其他分享 >JS数据结构之树和二叉树

JS数据结构之树和二叉树

时间：2024-11-08 20:45:39浏览次数：6  
标签：遍历 const val JS 之树 二叉树 root 节点

一、树

树（Tree）是一种非常常见的数据结构，它模拟了自然界中树的结构，由节点（或称为顶点）组成，并且具有层次化的组织形式。树结构在计算机科学中广泛应用，例如在组织数据、管理信息层次以及算法设计中。

1.基本概念

节点（Node）

  • 根节点（Root）：树的最顶端节点，没有父节点。
  • 内部节点（Internal Node）：至少有一个子节点的节点。
  • 叶节点（Leaf Node）或外部节点（External Node）：没有子节点的节点。
  • 子节点（Child）：直接连接到另一个节点的节点。
  • 父节点（Parent）：有子节点的节点。
  • 兄弟节点（Sibling）：共享相同父节点的节点。

边（Edge）

连接两个节点的线称为边，表示节点之间的关系。

层（Level）

  • 根节点位于第0层。
  • 每个节点的层数是其父节点的层数加1。

高度（Height）和深度（Depth）

  • 高度：节点的高度是指从该节点到最远叶子节点的最长路径上的边的数目。树的高度是其根节点的高度。
  • 深度：节点的深度是指从根节点到该节点的路径上的边的数目。

树的种类

  • 二叉树（Binary Tree）：每个节点最多有两个子节点的树。
    • 满二叉树：每个节点都有0个或2个子节点。
    • 完全二叉树：除了最后一层外，每一层都被完全填满，最后一层的节点都靠左排列。
    • 平衡二叉树（AVL Tree）：任何节点的两个子树的高度差都不超过1。
  • 多叉树（N-ary Tree）：每个节点可以有多个子节点。
  • 二叉搜索树（Binary Search Tree, BST）：左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。
  • 堆（Heap）：是一种特殊的完全二叉树，通常用于实现优先队列。

树的遍历

树结构的应用非常广泛，例如在文件系统的目录结构、组织结构、决策树、XML和HTML文档解析等领域都有应用。树的实现和操作通常比线性数据结构（如数组、链表）更复杂，但它们提供了强大的功能和灵活性。

深度优先遍历（DFS）：从根节点开始，优先深入每个分支的子节点，直到叶节点，之后再回溯到父节点处理下一个分支。DFS 在普通树中的常见方式是先序遍历（pre-order traversal），即先访问节点本身，然后递归访问它的所有子节点。

广度优先遍历（BFS）：层次遍历，从根节点开始，逐层访问每一层的节点。在普通树中，BFS 也叫做层次遍历（Level Order Traversal）。

2.深度优先遍历实现

在普通树中，DFS 的顺序通常是：先访问节点本身，再递归访问它的所有子节点。

class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];   // children 是一个子节点数组
    }
}

深度优先遍历 - 递归实现

//深度优先遍历
const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd',
                    children: [],
                },
                {
                    val: 'e',
                    children: [],
                }
            ],
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f',
                    children: [],
                },
                {
                    val: 'g',
                    children: [],
                }
            ],
        }
    ],
};

const dfs = (root) => {
    console.log(root.val);
    // root.children.forEach((child) => { dfs(child) });//可以直接写成下一行的样式
    root.children.forEach(dfs);
};
dfs(tree);

深度优先遍历 - 非递归实现（使用栈）

function dfsIterative(root) {
    if (root === null) return;
    const stack = [root];
    while (stack.length > 0) {
        const node = stack.pop();
        console.log(node.value);        // 访问当前节点
        for (let i = node.children.length - 1; i >= 0; i--) {
            stack.push(node.children[i]); // 逆序将子节点压栈
        }
    }
}

3.广度优先遍历实现

对于普通树的 BFS，可以使用队列来实现逐层遍历：

function bfs(root) {
    if (root === null) return;
    const queue = [root];
    while (queue.length > 0) {
        const node = queue.shift();
        console.log(node.value);        // 访问当前节点
        for (let child of node.children) {
            queue.push(child);          // 将所有子节点入队
        }
    }
}

//广度优先遍历算法口诀
//1.新建一个队列，把根节点入队；2.把队头出队并访问；
//3.把队头的children挨个入队；4.重复第二、第三步，直到队列为空。
//广度优先遍历
const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd',
                    children: [],
                },
                {
                    val: 'e',
                    children: [],
                }
            ],
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f',
                    children: [],
                },
                {
                    val: 'g',
                    children: [],
                }
            ],
        }
    ],
};

const bfs = (root) => {
    const q = [root];
    while (q.length > 0) {
        const n = q.shift();
        console.log(n.val);
        n.children.forEach((child) => {
            q.push(child);
        });
    }
}

bfs(tree);

二、二叉树

二叉树（Binary Tree）是一种特殊的树结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。

1.基本概念

基本定义

  • 节点（Node）：二叉树的基本单元，包含数据元素和两个指向其他节点的指针（可能为空）。
  • 根节点（Root）：二叉树的顶端节点，没有父节点。
  • 子节点（Child）：由父节点的指针指向的节点。
  • 左子节点（Left Child）：父节点的左侧子节点。
  • 右子节点（Right Child）：父节点的右侧子节点。
  • 叶节点（Leaf）：没有子节点的节点。
  • 内部节点（Internal Node）：至少有一个子节点的节点。
  • 兄弟节点（Sibling）：共享相同父节点的节点。

特殊类型的二叉树

  • 满二叉树：每一层的节点数都是最大节点数，即每一层都是满的。
  • 完全二叉树：除了最后一层外，每一层都是满的，并且最后一层的节点都靠左排列。
  • 平衡二叉树（AVL Tree）：任何节点的两个子树的高度差都不超过1。
  • 二叉搜索树（Binary Search Tree, BST）：左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。

二叉树的性质

  • 二叉树的第 i 层最多有 2^i 个节点（i 从 0 开始）。
  • 高度为 h 的二叉树最多有 2^(h+1) - 1 个节点。
  • 对于任何非空二叉树，如果叶子数为 N0，度为 2 的节点数为 N2，则有 N0 = N2 + 1。

二叉树的遍历

二叉树的遍历是指按照某种顺序访问树中的每个节点，以下是四种常见的遍历方法：

  • 前序遍历（Pre-order Traversal）：

    1. 访问根节点。
    2. 前序遍历左子树。
    3. 前序遍历右子树。

  • 中序遍历（In-order Traversal）：

    1. 中序遍历左子树。
    2. 访问根节点。
    3. 中序遍历右子树。

  • 后序遍历（Post-order Traversal）：

    1. 后序遍历左子树。
    2. 后序遍历右子树。
    3. 访问根节点。

  • 层序遍历（Level-order Traversal）：

    1. 从根节点开始，按从上到下、从左到右的顺序访问每一层的节点。

二叉树的实现

在计算机中，二叉树通常通过指针或引用来实现。以下是一个简单的二叉树节点的JavaScript实现：

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

通过创建 TreeNode 实例并适当地链接它们，我们可以构建出各种二叉树结构。

二叉树是许多高级数据结构和算法的基础，例如堆、优先队列、平衡树和二叉搜索树等。它们在计算机科学中扮演着重要角色，因为它们提供了一种有效的组织和处理数据的方法。

//先序遍历二叉树
const bt = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null,   
        },
        right: {
            val: 5,
            left: null,
            right: null,
        },
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right:null,
        },
        right: {
            val: 7,
            left: null,
            right:null,
        }
    } 
}
module.exports = bt;

2.二叉树的先序遍历

非递归实现思路：
  1. 初始化一个空栈。
  2. 将根节点压入栈中。
  3. 当栈不为空时：
    • 弹出栈顶节点，并访问它。
    • 先将右子节点压入栈（如果存在）。
    • 再将左子节点压入栈（如果存在）
//先序遍历
//导入二叉树的结构
const bt = require('./bt.js');
// 递归的方法
// console.log(bt);

// const preorder = (root) => {
//     if (!root) return;
//     console.log(root.val);
//     preorder(root.left);
//     preorder(root.right);
// }


// 非递归的方法
const preorder = (root) => {
    if (!root) return;
    const stack = [root];
    while (stack.length) {
        const n = stack.pop();
        console.log(n.val);
   // 先右后左，因为栈是后进先出
        if (n.right) stack.push(n.right);
        if (n.left) stack.push(n.left);
    }
}
preorder(bt);

3.二叉树的中序遍历

非递归实现思路：
  1. 初始化一个空栈。
  2. 将当前节点压入栈，并将当前节点更新为其左子节点，重复此操作直到当前节点为空。
  3. 弹出栈顶节点，并访问它，然后将当前节点更新为其右子节点。
  4. 重复步骤2和3，直到栈为空且当前节点为空。
//中序遍历
//导入二叉树的结构
// 递归版
const bt = require('./bt.js');
// console.log(bt);

// const inorder = (root) => {
//     if (!root) return;
//     inorder(root.left);
//     console.log(root.val);
//     inorder(root.right);
// }

// 非递归的方法
const inorder = (root) => {
    if (!root) return;
    const stack = [];
    let p = root;
    while (p || stack.length) {
        while (p) {
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop();
        console.log(n.val);
        p = n.right;
    }
};

inorder(bt);

 

4.二叉树的后序遍历

非递归实现思路：

后序遍历的非递归实现相对复杂，因为需要确保在访问一个节点之前，它的左右子节点已经被访问过。一种方法是在先序遍历的基础上稍作修改，然后反转结果。

  1. 初始化一个空栈。
  2. 将根节点压入栈中。
  3. 当栈不为空时：
    • 弹出栈顶节点，并访问它。
    • 先将左子节点压入栈（如果存在）。
    • 再将右子节点压入栈（如果存在）。
  4. 将遍历的结果反转。
function postOrderTraversalIterative(root) {
  if (!root) return;
  const stack = [root];
  const result = [];
  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.value); // 先将节点值加入结果数组
    // 先左后右，因为最后需要反转结果
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  // 反转结果数组得到后序遍历的顺序
  while (result.length > 0) {
    console.log(result.pop());
  }
}

也可以使用两个栈。

//后序遍历
//导入二叉树的结构
const bt = require('./bt.js');
// console.log(bt);

// const postorder = (root) => {
//     if (!root) return;
//     postorder(root.left);
//     postorder(root.right);
//     console.log(root.val);
// }


// 非递归的方法
const postorder = (root) => {
    if (!root) return;
    const stack = [root];
    const outputstack = [];
    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);  
    }
};


postorder(bt);

 

5.二叉树的深度优先遍历

// 二叉树的深度优先遍历
const bt = require('./bt.js');

const bdfs = (root) => {
    if (!root) return;
    console.log(root.val);
    bdfs(root.left);
    bdfs(root.right);
};

bdfs(bt);

6.二叉树的广度优先遍历

// 二叉树的广度优先遍历
const bt = require('./bt.js');

const bbfs = (root) => {
    if (!root) return;
    const q = [root];
    while (q.length > 0) {
        const n = q.shift();
        console.log(n.val);
        if (n.left) q.push(n.left);
        if (n.right) q.push(n.right);
    }
}

// 如果想知道每个结点是第几层
// const bbfs = (root) => {
//     if (!root) return;
//     const q = [[root, 1]];
//     while (q.length > 0) {
//         const [n, l] = q.shift();
//         console.log(n.val, l);
//         if (n.left) q.push([n.left, l + 1]);
//         if (n.right) q.push([n.right, l + 1]);
//     }
// };


bbfs(bt);

标签：遍历,const,val,JS,之树,二叉树,root,节点
From： https://blog.csdn.net/qq_56101688/article/details/143608855

相关文章

  • JS之正则表达式
    一、什么是正则表达式<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>Document<......
  • Leecode热题100-104.二叉树中的最大路径和
    二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。示例......
  • 【前端知识】JS模块规范
    JS模块规范概述CommonJS规范代码示例AMD规范代码示例ES6Module规范代码示例IIFE规范代码示例全局变量代码示例CommonJS模块和ES6模块有什么区别？1.语法和声明方式2.动态和静态导入3.循环依赖4.默认导出和命名导出5.文件扩展名6.环境和应用7.工具和构......
  • js实现漂亮的注册页面（js动态注册页面）
    代码：<!DOCTYPEhtml><htmllang="zh-CN"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>注册</title>......
  • JS实现漂亮的登录页面（氛围感页面）
    代码：<!DOCTYPEhtml><htmllang="zh-CN"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>登录</title>......
  • JS DOM获取
    一、DOM初相识DOM简介文档对象模型（DocumentObjectModel，简称DOM），它就是一些系列编程接口，有了这些接口，就可以改变页面内容，结构和样式DOM树：  文档：一个页面就是一个文档，DOM中使用document表示元素：页面中所有的标签都是元素，DOM中使用element表示节点：网页中所有内容都是节......
  • JS正则表达式
    一、概念正则表达式（规则表达式）用于定义一些字符串的规则，计算机可以根据正则表达式，来检查一个字符串是否符合规则，将字符串中符合规则的内容提取出来二、创建正则方式一：构造函数创建var变量=newRegExp("正则表达式","匹配模式");参数一：规则参数二：i忽略大小写g全局匹......
  • JS操作元素
    一、事件基础事件概述JS使我们有能力创建动态页面，而事件是可以被JS侦测的行为简单理解：触发----响应机制网页中每个元素都可以产生某些可以触发JS的事件，例如点击事件事件是由三部分组成事件源事件类型事件处理程序称为事件三要素事件源：事件被触发的对象谁被触发事......
  • 代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之
    110.平衡二叉树文章链接：https://programmercarl.com/0110.平衡二叉树.html#题外话题目链接：https://leetcode.cn/problems/balanced-binary-tree/description/classSolution{public://每次都要比较左右子树的高度差是否在1以内，所以递归是要统计子树的高度的intg......
  • 二叉树遍历
    二叉树遍历这个问题，以前一直没搞懂，只是模糊的了解。先序遍历:先访问根节点，再从左到右依次访问各子树。ABDECFG中序遍历:先访问左节点，再访问根节点，最后再访问右节点。DBEACGF后序遍历:先从左到右遍历各棵子树，再访问根节点。DEBGFCA先中后实际上对应的是根遍历的位置。层次遍历......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99