react源碼ReactTreeTraversal.js之數據結構與算法

makeFoxPlay 發布于2019-08-23 15:29 / 3507人閱讀

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

面試中，經常遇到的一個簡單算法題：查找兩個單鏈表的公共節點
最近在讀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算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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