7-9 高频面试题回答

Question

1. 常见的树型表结构设计有哪些？

设计1：邻接表，即本项目中采取的设计方式，表中包含parentId字段，这样是最常见的设计，能正确的表达菜单的树状结构且没有冗余数据，但在跨层级查询需要递归处理。不使用递归情况下无法查询某节点所有父级，所有子集

设计2：路径枚举
在设计1基础上新增一个parentIds字段，用来存储所有父集，多个以固定分隔符分隔，比如逗号。
优点:方便查询所有的子集 ，可以因此通过比较字符串parentIds长度获取当前节点层级 ;
缺点：新增节点时需要将parentIds字段值处理好 。parentIds字段的长度很难确定，无论长度设为多大，都存在不能够无限扩展的情况 。节点移动复杂，需要同时变更所有子集中的parentIds字段值 ;

设计3：闭包表
需要额外创建了一张TreePaths表，它记录了树中所有节点间的关系 ;
包含两列，祖先列与后代列，即使这两个节点之间不是直接的父子关系；同时增加一行指向节点自己 ;
参考文章

2. 编程题：递归算法

/**
 * 递归算法套路
 * 在if里调用自己，或者在else里调用自己都可以
 * 下面是以在if里调用自己为例
 */
public static func () {
  if (...) {
    // 触发条件时，自己调用自己
    func()
  } else {
    // 不再调用自己
  }
  return ;
}

使用递归方法将数组转为树形结构

/**
 * 使用递归将数组转为树形结构
 * 父ID属性为parent
 */
public static array2Tree (array: any, parentId: number) {
  if (Tool.isEmpty(array)) {
    return [];
  }

  const result = [];
  for (let i = 0; i < array.length; i++) {
    const c = array[i];
    // console.log(Number(c.parent), Number(parentId));
    if (Number(c.parent) === Number(parentId)) {
      result.push(c);

      // 递归查看当前节点对应的子节点
      const children = Tool.array2Tree(array, c.id);
      if (Tool.isNotEmpty(children)) {
        c.children = children;
      }
    }
  }
  return result;
}

Answer 1

甲蛙 2021-09-30 20:40:20

点赞！点赞！

下载视频          

• 提问者 Rainary #1

  非常感谢！

• weixin_慕仔5035165 回复 提问者 Rainary #2

  回复 Rainary:老师的下载视频怎么用