كيفية موازنة شجرة ثنائية في 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);
شكرًا
أوليفر بوب لاغومين
نصائح أخرى
هذا هو الرمز الكامل الذي استخدمته لإنشاء بنية بيانات شجرة ثنائية وعملياتها المقابلة:
<?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
