6-1.二叉树类

/* 数组表示下的二叉树类 */
class ArrayBinaryTree {
  #tree;

  /* 构造方法 */
  constructor(arr) {
    this.#tree = arr;
  }

  /* 列表容量 */
  size() {
    return this.#tree.length;
  }

  /* 获取索引为 i 节点的值 */
  val(i) {
    // 若索引越界，则返回 null ，代表空位
    if (i < 0 || i >= this.size()) return null;
    return this.#tree[i];
  }

  /* 获取索引为 i 节点的左子节点的索引 */
  left(i) {
    return 2 * i + 1;
  }

  /* 获取索引为 i 节点的右子节点的索引 */
  right(i) {
    return 2 * i + 2;
  }

  /* 获取索引为 i 节点的父节点的索引 */
  parent(i) {
    return Math.floor((i - 1) / 2); // 向下整除
  }

  /* 层序遍历 */
  levelOrder() {
    let res = [];
    // 直接遍历数组
    for (let i = 0; i < this.size(); i++) {
      if (this.val(i) !== null) res.push(this.val(i));
    }
    return res;
  }

  /* 深度优先遍历 */
  #dfs(i, order, res) {
    // 若为空位，则返回
    if (this.val(i) === null) return;
    // 前序遍历
    if (order === "pre") res.push(this.val(i));
    this.#dfs(this.left(i), order, res);
    // 中序遍历
    if (order === "in") res.push(this.val(i));
    this.#dfs(this.right(i), order, res);
    // 后序遍历
    if (order === "post") res.push(this.val(i));
  }

  /* 前序遍历 */
  preOrder() {
    const res = [];
    this.#dfs(0, "pre", res);
    return res;
  }

  /* 中序遍历 */
  inOrder() {
    const res = [];
    this.#dfs(0, "in", res);
    return res;
  }

  /* 后序遍历 */
  postOrder() {
    const res = [];
    this.#dfs(0, "post", res);
    return res;
  }
}

6-2.数组BFS

假设 /data/tree.js 文件中有如下数据：

module.exports = [
  {
    id: 'a',
    children: [
      {
        id: 'a-1',
        children: [
          {
            id: 'a-1-1'
          }
        ]
      },
      {
        id: 'a-2'
      }
    ]
  },
  {
    id: 'b',
    children: [
      {
        id: 'b-1',
        children: [
          {
            id: 'b-1-1'
          }
        ]
      },
      {
        id: 'b-2'
      }
    ]
  }
]

6-2-1.循环实现

// 广度优先搜索 Breadth First Search
const array = require('./data/tree')

function bfs(tree) {
  let queue = [...tree] // 初始时将所有根节点加入队列
  const result = []

  while (queue.length > 0) {
    const node = queue.shift() // 从队列中移除第一个节点
    result.push(node.id) // 将节点的 id 加入结果数组

    // 如果节点有子节点，将它们加入队列
    if (node.children) {
      queue.push(...node.children)
    }
  }

  return result
}

console.log(bfs(array))

打印结果为：

[
  'a',     'b',
  'a-1',   'a-2',
  'b-1',   'b-2',
  'a-1-1', 'b-1-1'
]

6-2-2.递归实现

// 递归方式 实现BFS
const array = require('./data/tree')

function bfsRecursive(nodes, result = []) {
  if (nodes.length === 0) return result

  const nextLevel = []
  for (const node of nodes) {
    result.push(node.id) // 将当前层节点的 id 加入结果
    if (node.children) {
      nextLevel.push(...node.children) // 收集下一层的节点
    }
  }

  return bfsRecursive(nextLevel, result) // 递归处理下一层
}

console.log(bfsRecursive(array))

打印结果为：

[
  'a',     'b',
  'a-1',   'a-2',
  'b-1',   'b-2',
  'a-1-1', 'b-1-1'
]

6-3.数组DFS

// 深度优先搜索 Deep First Search
const array = require('./data/tree')

const list = []
function search (array = []) {
  for (let i = 0;i < array.length; i++) {
    const item = array[i]
    list.push(item.id)
    if (item.children) {
      search(item.children)
    }
  }
}

search(array)

console.log(list)

打印结果为：

[
  'a',     'a-1',
  'a-1-1', 'a-2',
  'b',     'b-1',
  'b-1-1', 'b-2'
]