树遍历

js 中关于树的一些操作

树的遍历与查找

一般通过递归的方式遍历一颗树

一般遍历一棵树是为了查找里面的元素，比较保险的方法是先遍历树，保存为一个数组，然后再通过 array.find 方法查找元素

/**
 * 根据id在tree获取相对应的item
 * @param tree 搜索的tree对象，类型{}
 * @param id 需要搜索的item对应的id
 * @memberof TreeSearch
 */
findItemInTree = (tree, id) => {
  let list = [];
  // 遍历tree，存储到list
  const loop = (tree) => {
    if (tree == null) {
      return;
    }
    list.push(tree);
    if (tree.children && tree.children.length > 0) {
      for (let i = 0; i < tree.children.length; i++) {
        loop(tree.children[i]);
      }
    }
  };
  loop(tree);
  let item = list.find((listItem) => {
    return listItem.id === id;
  });
  return item;
};

获取元素 path

一般我们还有一个需求，就是获取树的 path
可以遍历树，存储为一个键值对结构，比如{}或者 map，然后再通过 parentId 直接循环查找，获取 path 数组

/**
 * 根据id获得item在tree中的路径
 *  @param tree tree对象
 *  @param id item对应的id
 * @memberof TreeSearch
 */
findItemPath = (tree, id) => {
  let listMap = new Map();
  // 遍历tree，存储到listMap
  const loop = (tree) => {
    if (tree == null) {
      return;
    }
    listMap.set(tree.id, tree);
    if (tree.children && tree.children.length > 0) {
      for (let i = 0; i < tree.children.length; i++) {
        loop(tree.children[i]);
      }
    }
  };
  loop(tree);
  let path = [];
  let currentNodeId = id;
  // 根节点上没有parentId字段，所以直接循环得出path数组
  while (currentNodeId) {
    path.unshift(currentNodeId);
    currentNodeId = listMap.get(currentNodeId).parentId;
  }
  return path;
};

树的遍历方式

深度优先

test = () => {
  let tree = {
    key: 1,
    value: 1,
    children: [
      {
        key: 2,
        value: 2,
        children: [
          {
            key: 4,
            value: 4,
          },
          {
            key: 5,
            value: 5,
          },
        ],
      },
      {
        key: 3,
        value: 3,
        children: [
          {
            key: 6,
            value: 6,
          },
          {
            key: 7,
            value: 7,
          },
        ],
      },
    ],
  };
  console.log(tree, "tree");
  // 递归方式
  const DFS = (tree) => {
    let list = [];
    const loop = (tree) => {
      list.push(tree);
      if (tree.children && tree.children.length > 0) {
        for (let i = 0; i < tree.children.length; i++) {
          loop(tree.children[i]);
        }
      }
    };
    loop(tree);
    return list;
  };
  let array = DFS(tree);
  console.log(array, "array");
};

广度优先

// 非递归方式
const BFS = (tree) => {
  let list = [];
  if (tree !== null) {
    // 借用队列实现，队列先进先出，借用数组模拟队列
    let queue = [];
    queue.unshift(tree);
    while (queue.length !== 0) {
      let item = queue.shift();
      list.push(item);
      let children = item.children;
      if (children) {
        for (let i = 0; i < children.length; i++) {
          queue.push(children[i]);
        }
      }
    }
  }
  return list;
};

let array2 = BFS(tree);
console.log(array2, "array2");