学习JavaScript数据结构与算法之树(5)

时间:2021-1-8 作者:admin

1. 什么是树

  • 一种分层数据的抽象模型
  • 前端工作中常见的树包括:DOM树、级联选择、树形控间

用JS模拟一个树

const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd',
                    children: [],
                },
                {
                    val: 'e',
                    children: [],
                }
            ],
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f',
                    children: [],
                },
                {
                    val: 'g',
                    children: [],
                }
            ],
        }
    ],
};

2. 树的常用操作

1. 深度优先遍历

  • 尽可能深的搜索树的分支

步骤:

  • 访问根节点
  • 对根节点的 children 挨个进行深度优先遍历

如下图顺序

代码实现:

const dfs = root => {
  console.log(root.val)
  root.children.forEach(dfs)
}

2. 广度优先遍历

  • 先访问离根节点最近的节点

步骤:

  • 新建一个队列,把根节点入队
  • 把队头出队并访问
  • 把队头的 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);
        });
    }
};

3. 二叉树

什么是二叉树

  • 树中每个节点最多只能有两个子节点

模拟一个二叉树

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,
        },
    },
};

4. 二叉树的遍历

1. 先序遍历(根左右)

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

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

preorder(bt)

非递归版

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);
    }
};

2. 中序遍历(左根右)

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

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 (stack.length || p) {
        while (p) {
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop();
        console.log(n.val);
        p = n.right;
    }
};

3. 后序遍历(左右根)

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

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

非递归版

const postorder = (root) => {
    if (!root) { return; }
    const outputStack = [];
    const stack = [root];
    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);
    }
};

4. 二叉树的应用

104. 二叉树的最大深度

111. 二叉树的最小深度

102. 二叉树的层序遍历

94. 二叉树的中序遍历

112. 路径总和

遍历JSON所有节点值:

const json = {
    a: { b: { c: 1 } },
    d: [1, 2],
};

const json = {
    a: { b: { c: 1 } },
    d: [1, 2],
};

const dfs = (n, path) => {
    console.log(n, path);
    Object.keys(n).forEach(k => {
        dfs(n[k], path.concat(k));
    });
};

dfs(json, []);

渲染Antd 的树组件

const { Tree } = antd;
const { TreeNode } = Tree;

const json = [
  {
    title: '一',
    key: "1" ,
    children: [{ title: "三", key: "3", children: [] } ]
  },
  {
    title: '二',
    key: "2" ,
    children: [{ title: "四", key: "4", children: [] } ]
  }
];

class Demo extends React.Component {
  dfs = n => {
    return (
      <TreeNode title={n.title} key={n.key}>
        {n.children.map(this.dfs)}
       </TreeNode>
    )
  }
  render() {
    return (
      <Tree>
        {json.map(this.dfs)}
      </Tree>
    )
  }
}

ReactDom.render(<Demo />, mountNode)
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。