php - PHP二叉树配对

Question

我想就二叉树的配对寻求一些帮助。考虑以下二叉树：

                          A
                          |
                  ------------------
                  |                |
                  B                C
                  |                |
            ----------        ----------
            |        |        |        |
            F        D        G        Z
            |                          |
     ----------------          ----------------
     |              |          |              |
     W              Y          M              N
     |              |          |              |
  ----------  ----------   ----------  ----------
  |        |  |        |   |        |  |        |
  X        E  O        P   R        Q  S        T

如何在这个二叉树中执行“中心配对”？

这些是每个节点可能的中心对：

• A 的中心对： B - C、F - Z、D - G、W - N、Y - M、X - T、E - S、O - Q、P - R
• B的中心对： F - D
• C的中心对： G - Z
• F的中心对： W - Y，X - P，E - O
• Z的中心对： M - N，R - T，Q - S

下面是我的代码。但它只适用于第 2 级。我想做一个动态函数——我可以传递树中的“X”级别，然后该函数可以找到“T”是否可用。

  function GetNodeLevel($accUname) {
    $x = 1;
    $level = 0;
    $placement = $accUname; 
    while($x > 0) {
      $placement = getPlacement($placement);
      if(strlen($placement) > 0) {
        $level++;
      } else {
        $x=0;
      }
    }

    return $level;
  }

  // 2ND LEVEL PARENT OF THE NODE
  function FindMy2ndLevelParent($accUname) {
    require('connection.php');

    $my_level = GetNodeLevel($accUname) - 1;

    for($x=1;$x <= $my_level;$x++) {
      $accUname = getPlacement($accUname); 
    }
    return $accUname;    
  }

  // OUTER MOST CENTER PAIR IN 2ND LEVEL
  function FindMy2ndLevelOuterCenterPair($accUname,$side) {
    require('connection.php');

    $my_uname = $accUname;
    $my_side = $side;
    $my_level = GetNodeLevel($accUname) - 1;

    for($x=1;$x <= $my_level;$x++) {
      $accUname = getPlacement($accUname);  
    }

   for($y=1;$y <= $my_level;$y++) {
      if ($side == 'left'){
       $tree = genealogy($accUname);
       $accUname = $tree['right_side']; 
      } else {
       $tree = genealogy($accUname);
       $accUname = $tree['left_side']; 
      }      
    }

    return $accUname;
  }

  // INNER MOST CENTER PAIR IN 2ND LEVEL
  function FindMy2ndLevelInnerCenterPair($accUname,$side) {
    require('connection.php');

    $my_uname = $accUname;
    $my_side = $side;
    $my_level = GetNodeLevel($accUname) - 1;

    for($x=1;$x <= $my_level;$x++) {
      $accUname = getPlacement($accUname);  
    }

    for($y=1;$y <= $my_level;$y++) {
      if ($y == 1 && $side == 'left') {
        $tree = genealogy($accUname);
        $accUname = $tree['left_side'];        
      } else if ($y == 1 && $side == 'right') {
        $tree = genealogy($accUname);
        $accUname = $tree['right_side'];        
      } else if ($y > 1 && $side == 'right')  {
        $tree = genealogy($accUname);
        $accUname = $tree['left_side'];                 
      } else if ($y > 1 && $side == 'left')  {
        $tree = genealogy($accUname);
        $accUname = $tree['right_side'];                 
      }       
    }

    return $accUname;
  }

此外，我的函数有一个预定义的位置，可以在树的另一侧进行。但这不是一个聪明的解决方案，因为如果我想在第三层获得它的中心对，我必须定义它的路径。

标签： phpalgorithmbinary-tree