¿Cómo equilibrar árbol binario en PHP sin matriz de rotación?
https://stackoverflow.com/questions/3743519
-
04-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Voy a tratar de hacerme lo más claro posible. Sobre la base de Adyacencia Lista Modelo: http://articles.sitepoint.com/article/hierarchical- datos en la base de datos
Necesito una manera de equilibrar este árbol
0
/ \
1 2
/ / \
3 4 5
\ \
6 7
a algo como:
0
/ \
1 2
/ \ / \
3 4 5 6
/
7
Sobre la base del Código de ejemplo:
<?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);
}
}
?>
I modificado el código para que pueda salir una mesa plana HTML siguiente:
$ super_parent = '0000' entradas izquierda nodo en la lista plana:
____________________________________________________
| 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 |
------------------------------------------------------
Pero necesito una manera de reorganizar todo esto en un árbol equilibrado sin mover o girar la matriz. Aunque puedo pensar en la creación de una tabla duplicada en el PP y hacer una segunda consulta para mostrar o crear otro árbol Binaray, pensé que puede ser posible reorganizar un árbol plano como esto en:
0
/ \
1 2
/ \ / \
3 4 5 6
/
7
De izquierda a derecha. 0 representa el padre o super_parent 0000.
La razón me gustaría hacer esto es por lo que puede crear un árbol virtual del árbol original que será la base de otro algoritmo en mi proyecto.
Gracias de antemano.
Bob
Solución 2
he decidido responder a mi propia pregunta con este descubrimiento. En general, esto se puede llamar, el "Método de distribución" de automatizar de forma recursiva un árbol binario equilibrado de izquierda a derecha. Este algoritmo se asegura de que cuidar de 64 pares por nivel y el resto se enjuaga:)
<?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);
?>
El nodo de primera línea izquierda de los padres súper debe ser contado como 1. Por 8 entradas izquierda, justo llamar a:
makeBTree(8,1,1);
Gracias
Oliver Bob Lagumen
Otros consejos
Este es el código completo i utilizado para construir una estructura de datos de árbol binario y sus operaciones correspondientes:
<?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
?>
