PHP Binary Tree implementation

Question

I need an implementation of a 'perfect binary tree' in PHP.

Currently, I have this:

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

You can view it here. I'm using the Frank Mich jQuery Binary Tree plugin to display the data, but as I said before I believe I need a binary tree in order to display it correctly.

If there's a better way, or I'm just doing it wrong? What would the solution be?

Answer 1

This is the code for implementing binary tree(data structure) in 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;
    }
}

Answer 2

From the Frank Mich Binary Tree page, it appears that your tree entries will display like this:

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

Where each number in the tree represents the index of its entry in the input array. Notice that counting down the first round column, the indexes go up by 2. In the second column, they go up by 4, and in the third column by 8.

I would create an array of strings with the name of each game in them. Then do something like this:

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)