如何平衡PHP中的二叉树而不旋转父级？

Question

我会尽量让自己变得尽可能清晰。从邻接表基于模型的：http://articles.sitepoint.com/article/hierarchical-data-database

我需要一种方法来平衡这棵树

 0 
    /\ 
    1 2 
//\ 
3 4 5 
     \ \ 
     6 7 

到喜欢的东西：从示例代码基于

 0 
    / \ 
    1  2 
    /\ /\ 
    3 4 5 6 
/
7 

：

<?php 
function display_children($parent, $level) { 
    $result = mysql_query('SELECT title FROM tree '. 
          'WHERE parent="'.$parent.'";'); 
    while ($row = mysql_fetch_array($result)) { 
     echo str_repeat(' ',$level).$row['title']."\n"; 
     display_children($row['title'], $level+1); 
    } 
} 
?> 

我修改了代码，以便它可以输出这样的平面html表格：

$ super_parent =“0000” 左节点条目为平面列表：

____________________________________________________ 
| No. | Date of Entry  | Account ID | Placement| 
------------------------------------------------------ 
| 1 | 2010-08-24 11:19:19 | 1111a  | a  | 
| 2 | 2010-08-24 11:19:19 | 22221a_a | a  | 
| 3 | 2010-08-24 11:19:19 | 33_2aa  | b  | 
| 4 | 2010-08-24 11:19:19 | 33_2Ra  | a  | 
| 5 | 2010-08-24 11:19:19 | 22221a_b | b  | 
| 6 | 2010-08-24 11:19:19 | 33_2ba  | a  | 
| 7 | 2010-08-24 11:19:19 | 33_2bb  | b  | 
------------------------------------------------------ 

但我需要一种方法来重新组织成平衡树这一切，没有移动或旋转父。虽然我认为在数据库创建重复表，并做以显示或创建另一个Binaray树中的第二个查询，我认为这是可能的重组这样一个平树成：

 0 
    / \ 
    1  2 
    /\ /\ 
    3 4 5 6 
/
7 

从左对。 0表示父代或super_parent 0000.

我想这样做的原因是我可以从原始树创建一个虚拟树，这将成为我项目中另一种算法的基础。

在此先感谢。

鲍勃

Answer 1

我决定用这个发现来回答我自己的问题。一般来说，这可以称为递归自动化平衡二叉树从左到右的“分布方法”。该算法可以确保采取的每级64双照顾，其余的将被冲刷掉：）

<?php 
function makeBTree($load, $colMult, $levCount){ 
    $exCol=$colMult; 
    if($load<=$colMult){ 
     $exCol=$load; 
    } if($load>0) {echo "Load: $load ";} else {echo "Load: 0 ";} 
    echo "Level: $levCount "; 
    echo "Columns: "; 

    for($i=1;$i<=$exCol; $i++){ 

    } 

    if($i<=64) { 
     echo "<font color='violet'>".($exCol)." candidate for pairing if count matches with TEAM B</font> \n"; 
    } else { 
     $limiter = ($i)-64; 
     echo "<font color='orange'>$i</font> - <font color='black'>64</font> = 
     <font color='blue'>$limiter auto-flushout</font> \n"; 
    } 

    $load -=$colMult; if($load>0) {echo "Load: $load ";} else {echo "Load: 0";} 
    echo "<br />\n"; 

    if($load>=1){ 
     makeBTree($load,$colMult*2, $levCount+1); 
    } 
} 

makeBTree(1000,1,1); 
?> 

超级父的左前线节点应该算作1左8项，只要致电：

makeBTree(8,1,1); 

感谢

奥利弗·鲍勃Lagumen

Answer 2

这是我用来构建一个二叉树数据结构及其相应的操作的完整代码：

<?php 
class Node 
{ 
public $data; 
public $leftChild; 
public $rightChild; 

public function __construct($data) 
    { 
    $this->data=$data; 
    $this->leftChild=null; 
    $this->rightChild=null; 
    } 
public function disp_data() 
    { 
    echo $this->data; 
    } 


}//end class Node 
class BinaryTree 
{ 
public $root; 
//public $s; 
public function __construct() 
    { 
    $this->root=null; 
    //$this->s=file_get_contents('store'); 

    } 
//function to display the tree 
    public function display() 
    { 
    $this->display_tree($this->root); 

    } 
    public function display_tree($local_root) 
    { 

    if($local_root==null) 
    return; 
    $this->display_tree($local_root->leftChild); 
    echo $local_root->data."<br/>"; 
    $this->display_tree($local_root->rightChild); 

    } 
// function to insert a new node 
    public function insert($key) 
    { 
    $newnode=new Node($key); 
     if($this->root==null) 
     { 
     $this->root=$newnode; 
     return; 
     } 
     else 
     { 
     $parent=$this->root; 
     $current=$this->root; 
      while(true) 
      { 
       $parent=$current; 
       //$this->find_order($key,$current->data); 
       if($key==($this->find_order($key,$current->data))) 
        { 
         $current=$current->leftChild; 
         if($current==null) 
         { 
          $parent->leftChild=$newnode; 
          return; 
         }//end if2 
        }//end if1 
       else 
        { 
         $current=$current->rightChild; 
         if($current==null) 
         { 
          $parent->rightChild=$newnode; 
          return; 
         } //end if1      
        } //end else 
      }//end while loop 
     }//end else 

    } //end insert function 

//function to search a particular Node 
public function find($key) 
    { 
    $current=$this->root; 
    while($current->data!=$key) 
      { 
      if($key==$this->find_order($key,$current->data)) 
       { 
       $current=$current->leftChild; 
       } 
      else 
       { 
       $current=$current->rightChild; 
       } 
      if($current==null) 
       return(null); 

      } 
     return($current->data); 
    }// end the function to search 
public function delete1($key) 
    { 
    $current=$this->root; 
    $parent=$this->root; 

    $isLeftChild=true; 
    while($current->data!=$key) 
      { 
      $parent=$current; 
      if($key==($this->find_order($key,$current->data))) 
      { 
       $current=$current->leftChild; 
       $isLeftChild=true; 
      } 
      else 
      { 
       $current=$current->rightChild; 
       $isLeftChild=false; 
      } 
      if($current==null) 
       return(null); 
      }//end while loop 

     echo "<br/><br/>Node to delete:".$current->data; 
    //to delete a leaf node 
    if($current->leftChild==null&&$current->rightChild==null) 
     { 
      if($current==$this->root) 
       $this->root=null; 
      else if($isLeftChild==true) 
      { 
      $parent->leftChild=null; 
      } 
     else 
      { 
      $parent->rightChild=null; 
      } 
     return($current);  
     }//end if1 
    //to delete a node having a leftChild 
    else if($current->rightChild==null) 
     { 
      if($current==$this->root) 
      $this->root=$current->leftChild; 
      else if($isLeftChild==true) 
      { 
      $parent->leftChild=$current->leftChild; 
      } 
      else 
      { 
      $parent->rightChild=$current->leftChild; 
      } 
      return($current); 
     }//end else if1 
    //to delete a node having a rightChild 
    else if($current->leftChild==null) 
     { 
     if($current==$this->root) 
      $this->root=$current->rightChild; 
     else if($isLeftChild==true) 
      { 
      $parent->leftChild=$current->rightChild; 
      } 
     else 
      { 
      $parent->rightChild=$current->rightChild; 
      } 
      return($current); 
     } 
    //to delete a node having both childs 
    else 
     { 
     $successor=$this->get_successor($current); 
     if($current==$this->root) 
      { 
      $this->root=$successor; 

      } 
     else if($isLeftChild==true) 
      { 
      $parent->leftChild=$successor; 
      } 
     else 
      { 
      $parent->rightChild=$successor; 
      }  
     $successor->leftChild=$current->leftChild; 
     return($current); 
     } 


    }//end the function to delete a node 
//Function to find the successor node 
public function get_successor($delNode) 
    { 
    $succParent=$delNode; 
    $successor=$delNode; 
    $temp=$delNode->rightChild; 
    while($temp!=null) 
     { 
      $succParent=$successor; 
      $successor=$temp; 
      $temp=$temp->leftChild; 
     } 
    if($successor!=$delNode->rightChild) 
    { 
     $succParent->leftChild=$successor->rightChild; 
     $successor->rightChild=$delNode->rightChild; 
    } 
    return($successor); 
    } 
//function to find the order of two strings 
public function find_order($str1,$str2) 
    { 
    $str1=strtolower($str1); 
    $str2=strtolower($str2); 
    $i=0; 
    $j=0; 

    $p1=$str1[i]; 
    $p2=$str2[j]; 
    while(true) 
    { 
     if(ord($p1)<ord($p2)||($p1==''&&$p2=='')) 
     { 

      return($str1); 
     } 
     else 
     { 
      if(ord($p1)==ord($p2)) 
      { 
       $p1=$str1[++$i]; 
       $p2=$str2[++$j]; 
       continue; 
      } 
      return($str2); 
     } 
    }//end while 

    } //end function find string order 

public function is_empty() 
    { 
    if($this->root==null) 
     return(true); 
    else 
     return(false); 
    } 
}//end class BinaryTree 
?>