react源碼ReactTreeTraversal.js之數(shù)據(jù)結(jié)構(gòu)與算法

makeFoxPlay 發(fā)布于2019-08-23 15:29 / 3513人閱讀

摘要：面試中，經(jīng)常遇到的一個簡單算法題查找兩個單鏈表的公共節(jié)點最近在讀源碼的時候發(fā)現(xiàn)一個樹中對該算法的運用見函數(shù)，在此做簡單的記錄。地址在樹中獲取當前實例節(jié)點的父節(jié)點實例組件對應(yīng)的，比如的表示為類組件，其為對應(yīng)元素。

面試中，經(jīng)常遇到的一個簡單算法題：查找兩個單鏈表的公共節(jié)點
最近在讀react源碼的時候發(fā)現(xiàn)一個react樹中對該算法的運用（見getLowestCommonAncestor函數(shù)），在此做簡單的記錄。
git地址

getParent

在react樹中獲取當前實例節(jié)點的父節(jié)點實例

//HostComponent組件對應(yīng)的DOM，比如App的tag=3, 表示為類組件，其child為tag=5對應(yīng)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

獲取節(jié)點A與B的最近的公共祖先節(jié)點

算法題：找到兩個鏈表的公共節(jié)點

export function getLowestCommonAncestor(instA, instB) {
  //獲取子節(jié)點A在樹中的深度
  let depthA = 0;
  for (let tempA = instA; tempA; tempA = getParent(tempA)) {
    depthA++;
  }
    //獲取子節(jié)點B在樹中的深度
  let depthB = 0;
  for (let tempB = instB; tempB; tempB = getParent(tempB)) {
    depthB++;
  }

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

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

  // Walk in lockstep until we find a match.
  // 現(xiàn)在，指針所處的位置的高度一致，可以同時往上查找，直到找到公共的節(jié)點
  let depth = depthA;
  while (depth--) {
    if (instA === instB || instA === instB.alternate) {
      return instA;
    }
    instA = getParent(instA);
    instB = getParent(instB);
  }
  return null;
}

isAncestor

判斷A節(jié)點是否是B節(jié)點的祖先節(jié)點

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及其以上的樹執(zhí)行冒泡捕獲的操作，執(zhí)行fn。類似事件的冒泡捕獲

export function traverseTwoPhase(inst, fn, arg) {
  const path = [];
  //將inst的父節(jié)點入棧，數(shù)組最后的為最遠的祖先
  while (inst) {
    path.push(inst);
    inst = getParent(inst);
  }
  let i;
  //從最遠的祖先開始向inst節(jié)點捕獲執(zhí)行fn
  for (i = path.length; i-- > 0; ) {
    fn(path[i], "captured", arg);
  }
    //從inst節(jié)點開始向最遠的祖先節(jié)點冒泡執(zhí)行fn
  for (i = 0; i < path.length; i++) {
    fn(path[i], "bubbled", arg);
  }
}

traverseEnterLeave

當關(guān)注點從from節(jié)點移出然后移入to節(jié)點的時候,在from執(zhí)行執(zhí)行類似移入移出的操作,from節(jié)點

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節(jié)點到from與to節(jié)點的最近公共祖先節(jié)點（不包括公共祖先節(jié)點）push到pathFrom數(shù)組
  //以上代碼將to節(jié)點到from與to節(jié)點的最近公共祖先節(jié)點（不包括公共祖先節(jié)點）push到pathTo數(shù)組

  // 以下代碼用于對pathFrom冒泡，執(zhí)行fn
  for (let i = 0; i < pathFrom.length; i++) {
    fn(pathFrom[i], "bubbled", argFrom);
  }
    // 以下代碼用于對pathTo捕獲，執(zhí)行fn
  for (let i = pathTo.length; i-- > 0; ) {
    fn(pathTo[i], "captured", argTo);
  }
}

云服務(wù)器 GPU云服務(wù)器 React 源碼 React源碼源碼中文說明之 webrtc之vad算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/102128.html

發(fā)表評論

登陸后可評論

0條評論

makeFoxPlay

男|高級講師

我要關(guān)注我要私信

TA的文章

提問！軟件自動化測試的出現(xiàn)！會不會導致件測試點工崗位直接消失？

閱讀 3725·2021-10-12 10:11
CSS實現(xiàn)空心三角指示箭頭

閱讀 1992·2019-08-30 15:53
【譯】2016 年 JavaScript 回顧

閱讀 1599·2019-08-30 13:15
前端面試重點之——多列布局

閱讀 2312·2019-08-30 11:25
BFC與自適應(yīng)淺析

閱讀 1810·2019-08-29 11:24
一站式前端資源上傳工具

閱讀 1658·2019-08-26 13:53
個人簡歷生成器

閱讀 3533·2019-08-26 13:22
vue項目props傳值類型影響：單項數(shù)據(jù)流及雙向數(shù)據(jù)流

閱讀 1776·2019-08-26 10:24

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

react源碼ReactTreeTraversal.js之數(shù)據(jù)結(jié)構(gòu)與算法

相關(guān)文章

**Deep In React 之詳談 React 16 Diff 策略(二)**

**淺談React Fiber**

**FE.SRC-React實戰(zhàn)與原理筆記**

React 源碼剖析系列－不可思議的 react diff

論一個前端工程師如何快速學習，成長。準備自己的35歲【-原創(chuàng)精讀】

發(fā)表評論

0條評論

makeFoxPlay

男|高級講師

TA的文章

提問！軟件自動化測試的出現(xiàn)！會不會導致件測試點工崗位直接消失？

CSS實現(xiàn)空心三角指示箭頭

【譯】2016 年 JavaScript 回顧

前端面試重點之——多列布局

BFC與自適應(yīng)淺析

一站式前端資源上傳工具

個人簡歷生成器

vue項目props傳值類型影響：單項數(shù)據(jù)流及雙向數(shù)據(jù)流

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

react源碼ReactTreeTraversal.js之數(shù)據(jù)結(jié)構(gòu)與算法

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！