|
|
Posted by davidgregan@gmail.com on 01/22/08 19:04
Hi, I'm fairly new to PHP and I have a question regarding pointers.
Below is an example binary tree implementation I found in the
internet. It works great but I'm not sure how it works. Here's what
I'm confused about, in the insert function the variable $pointer is
set to $this->tree. Now, my current understanding is that after this
the variable $pointer will contain the data from $this-> tree.
However, as the function continues $pointer is set to pointer->left
(or right) until the correct index is found. at this point the value
is added to the tree with $pointer->left=new leaf.
In this case the value of pointer seems to be referencing a position
in the $tree variable instead of merely containing the data of $tree
as I would expect. Furthermore, when $pointer->left is set to a new
leaf, it is actually added to $tree and not just to $pointer. So my
question is, why is this variable behaving like a pointer in this case
instead of just containing the value of tree?
Thanks,
Dave
class leaf
{
public $data;
public $left;
public $right;
public function __construct($d){
$this->data = $d;
}
}
class binary_tree{
public $tree=Null;
public function insert($val) {
if (!(isset($this->tree))) {
$this->tree = new leaf($val);
} else {
$pointer = $this->tree;
for(;;) {
if ($val <= $pointer->data) {
if ($pointer->left) {$pointer = $pointer->left;}
else {$pointer->left = new leaf($val); break;}
} else {
if ($pointer->right) {$pointer = $pointer-
>right;}
else {$pointer->right = new leaf($val); break;}
}
}
}
}
}
$root=new binary_tree;
for($i=0; $i<20; $i++){
$randnum = rand(0,1000);
$root->insert($randnum);
}
print "<pre>";
print_r($root)
Navigation:
[Reply to this message]
|