Реализация двоичного дерева PHP

Question

Мне нужна реализация «идеального бинарного дерева» в PHP.

В настоящее время у меня есть это:

<?php 
    $teams = 8; 
    $num_rounds = round(log($teams, 2)) + 1; 

    for ($i = 0; $i < $num_rounds; ++$i) 
    { 
    $matches = $teams * pow(.5, $i - 1)/2; 
    for ($j = 0; $j < $matches; ++$j) 
    { 
    echo "<div style=\"border-style: inset;\"><span>Round $i Match $j</span></div>\n"; 
    } 
    } 
?> 

Вы можете его here просмотра. Я использую плагин Frank Mich jQuery Binary Tree для отображения данных, но, как я уже сказал, я считаю, что мне нужно бинарное дерево, чтобы отображать его правильно.

Если есть лучший способ, или я просто делаю это неправильно? Каким будет решение?

Answer 1

Из Frank Mich Binary Tree page, кажется, что ваши записи дерева будет отображаться как это:

0 
    \ 
    1 
/ \ 
2  \ 
     \ 
      3 
     / \ 
4 / \ 
    \ /  \ 
    5   \ 
/   \ 
6    \ 
        \ 
        7 
       /
8    /
    \   /
    9  /
/ \  /
10  \ /
     \ /
      11 
     /
12 /
    \ /
    13 
/
14 

Где каждый номер в дереве представляет индекс его записи во входном массиве. Обратите внимание, что подсчет столбца первого раунда, индексы увеличиваются на 2. Во втором столбце они увеличиваются на 4, а в третьем столбце на 8.

Я бы создал массив строк с именем каждая игра в них. Затем сделать что-то вроде этого:

num_rounds = x 
num_games = (2^num_rounds) - 1 
game_names = array(num_games) 
for round = 0 to num_rounds - 1 
    index = (2^round) - 1 
    increment = 2^(round + 1) 
    game_number = 0 
    while index < num_games 
     game_names[index] = sprintf("round %s, game %s", round, game_number) 
     game_number++ 
     index += increment 
display_tree(game_names) 

Answer 2

Это код для реализации двоичного дерева (структуры данных) в PHP:

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

class BinaryTree 
{ 
    public $root; 

    public function __construct() 
    { 
     $this->root = null; 
    } 

    /** 
    * 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; 
       if ($key == ($this->find_order($key, $current->data))) { 
        $current = $current->leftChild; 
        if ($current == null) { 
         $parent->leftChild = $newnode; 

         return; 
        }//end if2 
       } else { 
        $current = $current->rightChild; 
        if ($current == null) { 
         $parent->rightChild = $newnode; 

         return; 
        } 
       } 
      } 
     } 
    } 

    /** 
    * 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); 
    } 

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

     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); 
     } else { //to delete a node having a leftChild 
      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); 
      } else { //to delete a node having a rightChild 
       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); 
       } else { //to delete a node having both childs 
        $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); 
       } 
      } 
     } 
    } 

    /** 
    * 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); 
      } 
     } 
    } 

    public function is_empty() 
    { 
     return $this->root === null; 
    } 
}