当前位置： 文江博客话题详情

如何在不旋转父级的情况下平衡 PHP 中的二叉树？

发布于 2024-09-19 21:11:45 字数 1860 浏览 13 评论 0原文

我会尽力让自己尽可能清楚。基于邻接列表模型： 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     |
------------------------------------------------------

但我需要一种方法将所有这些重新组织成平衡树，而无需移动或旋转父级。虽然我可以考虑在数据库中创建一个重复的表并执行第二个查询来显示或创建另一个二进制树，但我认为可以将这样的平面树重新组织为：

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

从左到右。 0 代表父级或 super_parent 0000。

我想这样做的原因是这样我可以从原始树创建一个虚拟树，这将成为我的项目中另一个算法的基础。

提前致谢。

鲍勃

原文

I will try to make myself as clear as possible. Based from Adjacency List Model: http://articles.sitepoint.com/article/hierarchical-data-database

I need a way to balance this tree

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

to something like:

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

Based from the sample 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); 
   } 
} 
?>

I modified the code so it can output a flat html table like this:

$super_parent = '0000'
left Node entries into flat list:

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

But I need a way to reorganize all this into a balanced tree without moving or rotating the parent. Although I can think of creating a duplicate table in the db and do a second query to display or create another Binaray tree, I thought it may be possible to reorganize a flat tree like this into:

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

From left to right. 0 represents the parent or super_parent 0000.

The reason I would like to do this is so I can create a virtual tree from the original tree that will be the basis of another algorithm in my project.

Thanks in advance.

Bob

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

因为看清所以看轻 2024-09-26 21:11:51

我决定用这个发现来回答我自己的问题。一般来说，这可以称为从左到右递归地自动化平衡二叉树的“分布方法”。该算法确保每个级别处理 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

I have decided to answer my own question with this discovery. In General, this can be called, the "Distribution Method" of recursively automating a Balanced Binary Tree from left to right. This algorithm makes sure to take care of 64 pairs per level and the rest would be flushed out : )

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

The left frontline node of super parent should be counted as 1. For 8 entries left, just call:

makeBTree(8,1,1);

Thanks

Oliver Bob Lagumen

回复 原文
梦毁影碎の 2024-09-26 21:11:50

这是我用来构建二叉树数据结构及其相应操作的完整代码：

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

This is the complete code i used to build a binary tree datastructure and its corresponding operations:

<?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
?>
回复 原文
~没有更多了~

关于作者

鹿童谣

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

胡图图

文章 0 评论 0

zt006

文章 0 评论 0

z祗昰~

文章 0 评论 0

冰葑

文章 0 评论 0

野の

文章 0 评论 0

天空

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文