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?

Perhaps I should rephrase, the labels are incorrect even though I'm iterating through them in order. The bracket display itself is great. — Zack
– Zack, Commented Sep 13, 2010 at 4:33
The expected output would be each column is a round in order of 0 1 2 3, and the matches are displayed in order in each column. — Zack
– Zack, Commented Sep 13, 2010 at 5:05
Further research has led me to believe that I need a BST with in-order traversal. How to get my data in the BST properly is beyond me. I've built this array in accordance to en.wikipedia.org/wiki/Binary_tree array(4, 2, 6, 1, 3, 5, 7); This is with the number of matches lowered to 7 (4 participants). — Zack
– Zack, Commented Sep 13, 2010 at 5:32

kix · Accepted Answer · 2017-06-29 08:57:02Z

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

You need to learn how to use the formatting tools in the editor so your code can display properly. See here.

Don Kirkby · Accepted Answer · 2010-11-03 18:23:36Z

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)

Collectives™ on Stack Overflow

PHP Binary Tree implementation

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related