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

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

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

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

getParent

在react樹中獲取當(dāng)前實(shí)例節(jié)點(diǎn)的父節(jié)點(diǎn)實(shí)例

//HostComponent組件對(duì)應(yīng)的DOM，比如App的tag=3, 表示為類組件，其child為tag=5對(duì)應(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é)點(diǎn)A與B的最近的公共祖先節(jié)點(diǎn)

算法題：找到兩個(gè)鏈表的公共節(jié)點(diǎn)

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

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

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

  // Walk in lockstep until we find a match.
  // 現(xiàn)在，指針?biāo)幍奈恢玫母叨纫恢拢梢酝瑫r(shí)往上查找，直到找到公共的節(jié)點(diǎn)
  let depth = depthA;
  while (depth--) {
    if (instA === instB || instA === instB.alternate) {
      return instA;
    }
    instA = getParent(instA);
    instB = getParent(instB);
  }
  return null;
}

isAncestor

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

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

getParentInstance

對(duì)getParent的export封裝：

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

traverseTwoPhase

對(duì)inst及其以上的樹執(zhí)行冒泡捕獲的操作，執(zhí)行fn。類似事件的冒泡捕獲

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

traverseEnterLeave

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

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

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