Comment équilibrer l'arbre binaire en PHP sans rotation de parent?

Question

Je vais essayer de me rendre aussi clair que possible. Basé de contiguïté Liste Modèle: http://articles.sitepoint.com/article/hierarchical-data-database

je besoin d'un moyen d'équilibrer cet arbre

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

à quelque chose comme:

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

Sur la base de l'exemple de code:

<?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); 
    } 
} 
?> 

J'ai modifié le code afin qu'il puisse produire une table html plate comme ceci:

$ super_parent = « 0000 » gauche entrées de nœud dans la liste plate:

____________________________________________________ 
| 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  | 
------------------------------------------------------ 

Mais je besoin d'un moyen de réorganiser tout cela dans un arbre équilibré sans bouger ou tourner le parent. Bien que je peux penser à la création d'une table en double dans la db et faire une deuxième requête pour afficher ou créer un autre arbre Binaray, je pensais qu'il peut être possible de réorganiser un arbre plat comme celui-ci dans:

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

De gauche à droite. 0 représente le parent ou super_parent 0000.

La raison pour laquelle je voudrais faire ceci est que je puisse créer un arbre virtuel à partir de l'arbre d'origine qui sera la base d'un autre algorithme dans mon projet.

Merci d'avance.

Bob

Answer 1

J'ai décidé de répondre à ma propre question avec cette découverte. En général, cela peut être appelé la "méthode de distribution" de l'automatisation récursive d'un arbre binaire équilibré de gauche à droite. Cet algorithme assure de prendre soin de 64 paires par niveau et le reste sera évacuée:)

<?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); 
?> 

Le nœud de première ligne gauche de parent super devrait être comptée comme 1. Pour 8 entrées gauche, il suffit d'appeler:

makeBTree(8,1,1); 

Merci

Oliver Bob Lagumen

Answer 2

Ceci est le code complet je l'ai utilisé pour construire une structure de données d'arbre binaire et ses opérations correspondantes:

<?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 
?>