Come bilanciare albero binario in PHP senza genitore a rotazione?
https://stackoverflow.com/questions/3743519
-
04-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
cercherò di rendermi il più chiaro possibile. Sulla base di adiacenza Lista Modello: http://articles.sitepoint.com/article/hierarchical- data-base di dati
Ho bisogno di un modo per bilanciare questo albero
0
/ \
1 2
/ / \
3 4 5
\ \
6 7
a qualcosa di simile:
0
/ \
1 2
/ \ / \
3 4 5 6
/
7
In base dalla Esempio di codice:
<?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 modificato il codice in modo da poter inviare una tabella html piatto come questo:
$ super_parent = '0000' voci sinistra nodo nel semplice lista:
____________________________________________________
| 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 |
------------------------------------------------------
Ma ho bisogno di un modo per riorganizzare tutto questo in un albero bilanciato senza muovere o ruotare il genitore. Anche se mi viene in mente di creare una tabella duplicata nel db e fare una seconda query per visualizzare o creare un altro albero Binaray, ho pensato che potrebbe essere possibile riorganizzare un albero piatto come questo in:
0
/ \
1 2
/ \ / \
3 4 5 6
/
7
Da sinistra a destra. 0 rappresenta il genitore o super_parent 0000.
Il motivo che mi piacerebbe fare questo è così posso creare un albero virtuale dalla albero originale che sarà la base di un altro algoritmo nel mio progetto.
Grazie in anticipo.
Bob
Soluzione 2
ho deciso di rispondere alla mia domanda con questa scoperta. In generale, questo può essere chiamato, la "Distribuzione Method" di ricorsivamente l'automazione di un albero binario bilanciato da sinistra a destra. Questo algoritmo fa in modo di prendersi cura di 64 coppie per livello e il resto sarebbe lavata:)
<?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);
?>
Il nodo prima linea sinistra del genitore eccellente dovrebbe essere considerato come 1. Per 8 voci a sinistra, basta chiamare:
makeBTree(8,1,1);
Grazie
Oliver Bob Lagumen
Altri suggerimenti
Questo è il codice completo usato per costruire una struttura di dati ad albero binario e le sue operazioni corrispondenti:
<?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
?>
