data structure for traversal tree in PHP?
https://stackoverflow.com/questions/3418684
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I don't have a background in CS or data structures. I want to make a PHP class that stores a modified preorder transversal tree, for manipulation and syncing with a database.
Basically I need to store data like:
+-------------+----------------------+-----+-----+
| category_id | name | lft | rgt |
+-------------+----------------------+-----+-----+
| 1 | ELECTRONICS | 1 | 20 |
| 2 | TELEVISIONS | 2 | 9 |
| 3 | TUBE | 3 | 4 |
| 4 | LCD | 5 | 6 |
| 5 | PLASMA | 7 | 8 |
| 6 | PORTABLE ELECTRONICS | 10 | 19 |
| 7 | MP3 PLAYERS | 11 | 14 |
| 8 | FLASH | 12 | 13 |
| 9 | CD PLAYERS | 15 | 16 |
| 10 | 2 WAY RADIOS | 17 | 18 |
+-------------+----------------------+-----+-----+
I was thinking of using an array, but it seems cumbersome. If it were an array of arrays like this: array( 'name'=> "PORTABLE ELECTRONICS", 'lft' => 10, 'rgt' = 19 ), then it would get cumbersome to loop through that array repeatedly to make sure all numbers are present, etc.
Since PHP has a few new data structures available, I wonder if any of these would get me any benefit over using an array?
- SplDoubly
- LinkedList
- SplStack
- SplQueue
- SplHeap
- SplMaxHeap
- SplMinHeap
- SplPriorityQueue
- SplFixedArray
- SplObjectStorage
Edit: This class isn't going to be a gateway to a tree stored in a database table. (If it were, I would just have a query of classes.) It's just a stand-alone mmpt in some kind of PHP data structure.
Solution
Edit: Ok, I looked into this a little more. I think there was a mix up in the nomenclature. You're not looking for a data structure for a transveral tree in PHP. You want to use a tree as a data structure in PHP, and you want to recover data from that tree using a method called the modified preorder tree traversal algorithm.
When working with a tree, we work from left to right, one layer at a time, descending to each node's children before assigning a right-hand number and moving on to the right. This approach is called the modified preorder tree traversal algorithm.
This is about storing hierarchical data in PHP vs MySQL. In PHP we can use a simple tree. The problem is that it is not easy to store a tree in the flat database that is MySQL. One option is to take the PHP and retrieve and adjacency list from it. This is essentially a list of each item and its parents. This way of doing things has some draw backs.
Another method is to extract information from the PHP tree that describes the nested sets that can be made out of the hierarchical data. To get this information from the PHP tree we need to use a modified preorder tree traversal algorithm. This is a method of running up and down the tree in order to extract certain information from it.
Whether we use the adjacency list model or the modified preorder tree traversal to retrieve the information, we use the exact same PHP Tree. The difference becomes how we retrieve the information from the tree and how we store the information in MySQL. The code for how to extract the information from MySQL is already on the page you quoted. To synch the data between PHP and MySQL you just have to use the MySQL techniques described on that page and a PHP tree class.
For this, I created a class in PHP that stores a tree. It uses a nodes. Each node can be thought of as the root of a complete tree, since from each node a complete subtree can be accessed. It was just easier to separate out the node from the tree, and it causes less overhead.
The important part of the class is the showAdjacency method. This runs the tree using a modified preorder tree traversal, and it displays the lft and rgt quantity for each name that enables you to store the data in MySQL as a Nested Set.
You can also display the tree, so you can visualize it. The deletion method is missing from this class. When you implement it, you have to pass the children of the deleted node to the parent of the node. Maybe I'll do that later.
I'll include the entire class at the bottom of the post, but here is how the data is retrieved for the modified preorder tree traversal:
// The modified preorder tree traversal.
private function showAdjacency($root, $spaces)
{
// Print the data first
if ($root)
{
// On the way down the tree, we get lft.
$left = ++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$spaces = $this->showAdjacency($child, $spaces);
}
}
}
// On the way back up, we get rgt.
$right = ++$spaces;
echo "$left - $right - $root->data <br/>";
return $spaces;
}
You can obviously store $root->data, $rgt, and $lft in an array that you use to synch with your database.
Here is the entire class. After the class I create a tree using the sample data from the page you linked to, and I output the lft and rgt values as well as the tree visualization.
You can run the code on Codepad
<?php
// Class defintions and methods:
// It's easier to use separate nodes. Each node still points to an entire and complete subtree.
class Node
{
public $data;
public $next = array();
}
// A first try at creating a tree with any number of branches from its nodes
// by Peter Ajtai - feel free to use and modify
class Tree
{
// The root
private $root;
public function __construct()
{
$this->root = NULL;
}
// The public wrapper.
// This is needed because we must start the recursive functions
// at the root, and we do not want to give public access to root.
// I am not familiar w overloading in PHP, maybe __set should be used for this
public function insertPub($data, $parent)
{
$root =& $this->root;
$this->insert($root, $data, $parent);
}
private function insert(&$root, $data, $parent)
{
// Create the root of the entire tree if no parent is passed in
if (!$root && !$parent)
{
$root = new Node;
$temp =& $root;
$temp->data = $data;
// Create space for next insertion
$temp->next[] = NULL;
} else if ($root->data == $parent)
{
// Add data as a child if we're at the parent, and we're done.
// Find the empty node to insert at
foreach($root->next as &$child)
{
// Insert at the first (and only) NULL
if (!$child)
{
$child = new Node;
$temp =& $child;
$temp->data = $data;
// Create space for next insertion
$temp->next[] = NULL;
}
}
// Create space for the next insertion
$root->next[] = NULL;
} else
{
// Keep searching for the parent as default behavior.
foreach($root->next as $child)
{
if ($child)
{
$this->insert($child, $data, $parent);
}
}
}
}
// Public wrapper for the display function.
public function showAdjPub()
{
echo "The neighbors:<br/><br/>";
$root =& $this->root;
$this->showAdjacency($root, 0);
echo "<br/>";
}
// The display function.
private function showAdjacency($root, $spaces)
{
// Print the data first
if ($root)
{
$left = ++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$spaces = $this->showAdjacency($child, $spaces);
}
}
}
$right = ++$spaces;
echo "$left - $right - $root->data <br/>";
return $spaces;
}
// Public wrapper for the display function.
public function showAllPub()
{
echo "The tree:<br/><br/>";
$root =& $this->root;
$this->showAll($root, 0);
echo "<br/>";
}
// The display function.
private function showAll($root, $spaces)
{
// Print the data first
if ($root)
{
for ($i=0; $i < $spaces; ++$i)
echo "---> ";
echo "$root->data <br/>";
++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$this->showAll($child, $spaces);
}
}
}
}
}
// Create a new instance of the tree
$myTree = new Tree;
// Insert the data into the tree.
// The following data would be retrieved using MySQL
$name = 'Electronics'; $parent = NULL;
$myTree->insertPub($name, $parent);
$name = 'Televisions'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);
$name = 'Tube'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Lcd'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Plasma'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Portable Electronics'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);
$name = 'MP3 Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
$name = 'Flash'; $parent = 'MP3 Players';
$myTree->insertPub($name, $parent);
$name = 'CD Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
$name = '2 Way Radios'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
// Display adjacency
$myTree->showAdjPub();
// Show hierarchy
$myTree->showAllPub();
?>
PS: Storing the data in PHP in nested arrays like you suggested would be very difficult. In the class above, if a data member is deleted the tree is modified (including additions of entire subtrees, etc) the lft and rgt values will still be retrieved correctly.
If you use arrays to store the information you will have an extremely hard time deleting items that have both parents and children, and updating the lft and rgt valuse would be very hard. Finally adding large sets (subtrees) to the array would also be extremely difficult.
A tree is really the ideal way to store this sort of hierarchical data. It mimics our notions of sets. The problem is that while PHP stores trees easily MySQL doesn't, so we need to go through all the difficult work of the modified preorder tree traversal in order to extract information from the PHP tree so that we can store it in the MySQL db.
OTHER TIPS
A simple running program with Node and Tree objects. Without any further ado, ladies and gentlemen, here is the code:
<?php
#Create a node class
#-----------------------------------------------------------------------------
class Node
{
#The node properties
public $value;
public $leftChild;
public $rightChild;
#Set the properties for the node
public function set_value($passedValue)
{
$this->value = $passedValue;
}
public function set_left_child($passedChild)
{
$this->leftChild = $passedChild;
}
public function set_right_child($passedChild)
{
$this->rightChild = $passedChild;
}
#Get the properties for the node
public function get_value()
{
return $this->value;
}
public function get_left_child()
{
return $this->leftChild;
}
public function get_right_child()
{
return $this->rightChild;
}
}
#Create a tree class with a function to transverse the node
#-----------------------------------------------------------------------------
class Tree
{
#The node properties
public $treeNodes = array();
public $preorderedNodes = array();
public $nodeArray = array();
#Set the tree nodes from the passed array
public function set_tree_nodes($nodeArray)
{
$this->nodeArray = $nodeArray;
#Set each node with its children based on the passed array
foreach($this->nodeArray AS $node) array_push($this->treeNodes, $this->set_node_object($node));
}
public function set_node_object($node)
{
$nodeObject = new Node();
$nodeObject->set_value($node['value']);
if(!empty($node['left_child'])) $nodeObject->set_left_child($this->nodeArray[$node['left_child']]);
if(!empty($node['right_child'])) $nodeObject->set_right_child($this->nodeArray[$node['right_child']]);
return $nodeObject;
}
#perfom a preorder transversal on the tree and return the tree nodes in the expected order
public function do_preorder_transversal($node)
{
#If the node is empty, end the recursion
if(empty($node)) return $this->preorderedNodes;
#Start the transversal
if($node == 'head' && !empty($this->treeNodes[0])) $node=$this->treeNodes[0];
#Add the node to the pre-ordered node list
array_push($this->preorderedNodes, $node);
$leftChild = $node->get_left_child();
$rightChild = $node->get_right_child();
if(!empty($leftChild)) $this->do_preorder_transversal($this->set_node_object($leftChild));
if(!empty($rightChild)) $this->do_preorder_transversal($this->set_node_object($rightChild));
}
#Get the preordered nodes
public function get_preordered_nodes()
{
return $this->preorderedNodes;
}
}
#-----------------------------------------------------------------------------
# Test the objects
#-----------------------------------------------------------------------------
#Call the class in an example
$sampleTree = new Tree();
$seedData = array();
#Seed data array is in the format [value, [key to left child], [key to right child]]
$seedData[0] = array('value'=>2, 'left_child'=>1, 'right_child'=>2);
$seedData[1] = array('value'=>7, 'left_child'=>3, 'right_child'=>4);
$seedData[2] = array('value'=>5, 'left_child'=>'', 'right_child'=>7);
$seedData[3] = array('value'=>2, 'left_child'=>'', 'right_child'=>'');
$seedData[4] = array('value'=>6, 'left_child'=>5, 'right_child'=>6);
$seedData[5] = array('value'=>5, 'left_child'=>'', 'right_child'=>'');
$seedData[6] = array('value'=>11, 'left_child'=>'', 'right_child'=>'');
$seedData[7] = array('value'=>9, 'left_child'=>8, 'right_child'=>'');
$seedData[8] = array('value'=>4, 'left_child'=>'', 'right_child'=>'');
$sampleTree->set_tree_nodes($seedData);
#Create the root node to start the tree transversal
$sampleTree->do_preorder_transversal('head');
#Now get the preordered nodes and print out their values
$preordered = $sampleTree->get_preordered_nodes();
foreach($preordered AS $count=>$node) echo "<BR>[".$count."] ".$node->get_value();
?>
The results are as follows:
[0] 2
[1] 7
[2] 2
[3] 6
[4] 5
[5] 11
[6] 5
[7] 9
[8] 4
This is the code I used to build a binary tree and its operations 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;
}
}//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
?>
