如何在不旋转父母的情况下平衡PHP中的二进制树？
https://stackoverflow.com/questions/3743519
-
04-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我将尽力使自己尽可能清楚。基于邻接列表模型： 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 |
------------------------------------------------------
但是我需要一种方法将所有这些重组为平衡的树，而无需移动或旋转父母。尽管我可以想到在DB中创建一个重复的表，并进行第二个查询以显示或创建另一个Binaray树，但我认为可以将像这样的平坦树重组为：
0
/ \
1 2
/ \ / \
3 4 5 6
/
7
从左到右。 0代表父级或super_parent 0000。
我想这样做的原因是，我可以从原始树上创建一个虚拟树，这将成为我项目中另一种算法的基础。
提前致谢。
鲍勃
解决方案 2
我决定通过这一发现回答自己的问题。通常，这可以称为“分布方法”，即从左到右递归自动化平衡的二进制树。该算法确保每个级别的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);
谢谢
奥利弗·鲍勃·拉古曼（Oliver Bob Lagumen）
其他提示
这是我用来构建二进制树数据结构及其相应操作的完整代码：
<?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
?>
不隶属于 StackOverflow
