Binary tree using PHP

Question

I want to build a binary tree using PHP. But as there are no pointers in PHP, how can i build a tree. For each node in the tree there must be the following attributes:
1. value at the node
2. level of the node
3. pointer to right child
4. pointer to left child

But as there are no pointers in PHP, i dont know how and where to start. All i know is that if we use $a=&$b, then both will point to the same object and they are not like pointers in C. Please suggest me few ways to build a binary tree using PHP.

I built once a php simple linked list that does printing of nodes and sequenial insertion. The thing is that it is the C++ way with objects and references (since no pointers) without the use of arrays. It is simple and I believe you can easily modify it to a tree, if you want it let me know. — Melsi
– Melsi, Commented Oct 4, 2011 at 12:26

James Anderson · Accepted Answer · 2011-10-04 07:47:40Z

3

The trick is that php arrays can have another array as an element.

Without using classes you can do

$root = array(0,0)

$root[0] = $firstval;   // Value
$root[1] = 0;           // level 0

// first child on left
$lchild = array($lvalue,1);  // left value and level 1
$root[2] = $lchild;          // attach to root item

// first right child 
$rchild = array($rvalue,1);  // right value and level 1
$root[3] = $rchild;          // attach to root item;



//print value of right child:-
   print $root[3][0];
// or more usefull
$anode = $root[3];
print "Value " + $anode[0];
if (isset($anode[2]) ) {
    print "has left child";
}

With classes you just define a class which contains the value , the level, another instance of the class for the left branch and another instance of the class for the right branch. Its effectively the same as the pure array implementation above but easier to read.

edited Oct 4, 2011 at 7:47

answered Oct 4, 2011 at 4:37

James Anderson

27.5k7 gold badges55 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

harsha2624 Over a year ago

as far as level and value are concerned, it is good, but how will i point to the childnodes. Please elp me.

jayunit100 · Accepted Answer · 2011-10-04 03:52:47Z

0

Use a list / array data structure, and simply point to the items in the list. The location of any element tree in the list can be easily calculated, since a binary tree takes up 2,4,8,16 spaces for each new level . so you might pre-declare the list to be a factor of two long.

OR use PHP objects, which can wrap variables and initialize them just as in java objects.

a tree with only one node, whose value was "13" would look like this

13 null null null null null null null null null null ...

a tree with a head node and two children to its left would look like this

13 12 null 11 null null null null null null null null null ...

answered Oct 4, 2011 at 3:52

jayunit100

17.7k23 gold badges99 silver badges175 bronze badges

Collectives™ on Stack Overflow

Binary tree using PHP

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