react源码ReactTreeTraversal.js之数据结构与算法

makeFoxPlay 发布于2019-08-23 15:29 / 3685人阅读

摘要：面试中，经常遇到的一个简单算法题查找两个单链表的公共节点最近在读源码的时候发现一个树中对该算法的运用见函数，在此做简单的记录。地址在树中获取当前实例节点的父节点实例组件对应的，比如的表示为类组件，其为对应元素。

面试中，经常遇到的一个简单算法题：查找两个单链表的公共节点
最近在读react源码的时候发现一个react树中对该算法的运用（见getLowestCommonAncestor函数），在此做简单的记录。
git地址

getParent

在react树中获取当前实例节点的父节点实例

//HostComponent组件对应的DOM，比如App的tag=3, 表示为类组件，其child为tag=5对应div元素。
function getParent(inst) {
  do {
    inst = inst.return;
    // TODO: If this is a HostRoot we might want to bail out.
    // That is depending on if we want nested subtrees (layers) to bubble
    // events to their parent. We could also go through parentNode on the
    // host node but that wouldn"t work for React Native and doesn"t let us
    // do the portal feature.
  } while (inst && inst.tag !== HostComponent);
  if (inst) {
    return inst;
  }
  return null;
}

getLowestCommonAncestor

获取节点A与B的最近的公共祖先节点

算法题：找到两个链表的公共节点

export function getLowestCommonAncestor(instA, instB) {
  //获取子节点A在树中的深度
  let depthA = 0;
  for (let tempA = instA; tempA; tempA = getParent(tempA)) {
    depthA++;
  }
    //获取子节点B在树中的深度
  let depthB = 0;
  for (let tempB = instB; tempB; tempB = getParent(tempB)) {
    depthB++;
  }

  // If A is deeper, crawl up.
  // 如果A的高度高，那么A节点先往上走depthA - depthB个节点，最后同时走，直到父节点是同一个
  while (depthA - depthB > 0) {
    instA = getParent(instA);
    depthA--;
  }

    // 如果B的高度高，那么B节点先往上走depthB - depthB个节点，最后同时走，直到父节点是同一个
  // If B is deeper, crawl up.
  while (depthB - depthA > 0) {
    instB = getParent(instB);
    depthB--;
  }

  // Walk in lockstep until we find a match.
  // 现在，指针所处的位置的高度一致，可以同时往上查找，直到找到公共的节点
  let depth = depthA;
  while (depth--) {
    if (instA === instB || instA === instB.alternate) {
      return instA;
    }
    instA = getParent(instA);
    instB = getParent(instB);
  }
  return null;
}

isAncestor

判断A节点是否是B节点的祖先节点

export function isAncestor(instA, instB) {
  while (instB) {
    if (instA === instB || instA === instB.alternate) {
      return true;
    }
    instB = getParent(instB);
  }
  return false;
}

getParentInstance

对getParent的export封装：

export function getParentInstance(inst) {
  return getParent(inst);
}

traverseTwoPhase

对inst及其以上的树执行冒泡捕获的操作，执行fn。类似事件的冒泡捕获

export function traverseTwoPhase(inst, fn, arg) {
  const path = [];
  //将inst的父节点入栈，数组最后的为最远的祖先
  while (inst) {
    path.push(inst);
    inst = getParent(inst);
  }
  let i;
  //从最远的祖先开始向inst节点捕获执行fn
  for (i = path.length; i-- > 0; ) {
    fn(path[i], "captured", arg);
  }
    //从inst节点开始向最远的祖先节点冒泡执行fn
  for (i = 0; i < path.length; i++) {
    fn(path[i], "bubbled", arg);
  }
}

traverseEnterLeave

当关注点从from节点移出然后移入to节点的时候,在from执行执行类似移入移出的操作,from节点

export function traverseEnterLeave(from, to, fn, argFrom, argTo) {
  const common = from && to ? getLowestCommonAncestor(from, to) : null;
  const pathFrom = [];
  while (true) {
    if (!from) {
      break;
    }
    if (from === common) {
      break;
    }
    const alternate = from.alternate;
    if (alternate !== null && alternate === common) {
      break;
    }
    pathFrom.push(from);
    from = getParent(from);
  }
  const pathTo = [];
  while (true) {
    if (!to) {
      break;
    }
    if (to === common) {
      break;
    }
    const alternate = to.alternate;
    if (alternate !== null && alternate === common) {
      break;
    }
    pathTo.push(to);
    to = getParent(to);
  }
  //以上代码将from节点到from与to节点的最近公共祖先节点（不包括公共祖先节点）push到pathFrom数组
  //以上代码将to节点到from与to节点的最近公共祖先节点（不包括公共祖先节点）push到pathTo数组

  // 以下代码用于对pathFrom冒泡，执行fn
  for (let i = 0; i < pathFrom.length; i++) {
    fn(pathFrom[i], "bubbled", argFrom);
  }
    // 以下代码用于对pathTo捕获，执行fn
  for (let i = pathTo.length; i-- > 0; ) {
    fn(pathTo[i], "captured", argTo);
  }
}

云服务器 GPU云服务器 React 源码 React源码源码中文说明之 webrtc之vad算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102128.html

Deep In React 之详谈 React 16 Diff 策略(二)

摘要：对于同一层级的一组子节点，它们可以通过唯一进行区分。基于以上三个前提策略，分别对以及进行算法优化。链表的每一个节点是，而不是在之前的虚拟节点。是当前层的第一个节点。再次提醒，是的一层。文章首发于个人博客这是我 Deep In React 系列的第二篇文章，如果还没有读过的强烈建议你先读第一篇：详谈 React Fiber 架构(1)。前言我相信在看这篇文章的读者一般都已经了解...

NSFish 2019-08-26 10:27 评论0 收藏0
浅谈React Fiber

摘要：因为版本将真正废弃这三生命周期到目前为止，的渲染机制遵循同步渲染首次渲染，更新时更新时卸载时期间每个周期函数各司其职，输入输出都是可预测，一路下来很顺畅。通过进一步观察可以发现，预废弃的三个生命周期函数都发生在虚拟的构建期间，也就是之前。 showImg(https://segmentfault.com/img/bVbweoj?w=559&h=300); 背景前段时间准备前端招聘事项...

izhuhaodev 2019-08-26 10:43 评论0 收藏0
FE.SRC-React实战与原理笔记

摘要：异步实战状态管理与组件通信组件通信其他状态管理当需要改变应用的状态或有需要更新时，你需要触发一个把和载荷封装成一个。的行为是同步的。所有的状态变化必须通过通道。前端路由实现与源码分析设计思想应用是一个状态机，视图与状态是一一对应的。 React实战与原理笔记概念与工具集 jsx语法糖;cli;state管理;jest单元测试; webpack-bundle-analyzer Sto...

PumpkinDylan 2019-08-26 14:04 评论0 收藏0
React 源码剖析系列－不可思议的 react diff

摘要：目前，前端领域中势头正盛，使用者众多却少有能够深入剖析内部实现机制和原理。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。目前，前端领域中 React 势头正盛，使用者众多却少有能够深入剖析内部实现机制和原理。本系列文章希望通过剖析 React 源码，理解其内部的实现原理，知其然更要知其所以然。 React diff 作为 Virtual DOM 的加速...

shuibo 2019-08-21 10:47 评论0 收藏0
论一个前端工程师如何快速学习，成长。准备自己的35岁【-原创精读】

showImg(https://segmentfault.com/img/bVbw3tK?w=1240&h=827); 前端工程师这个岗位，真的是反人性的我们来思考一个问题：一个6年左右经验的前端工程师：前面两年在用jQuery 期间一直在用React-native（一步一步踩坑过来的那种）最近两年还在写微信小程序下面一个2年经验的前端工程师：并不会跨平台技术，他的两年工作都是Reac...

RdouTyping 2019-08-30 15:44 评论0 收藏0