Binary tree using php

PHP
1

Hi all,

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.

2

This is a very simple example and relies on method recursion, but at least shows it’s possible using objects.


<?php
class nodeElement {
	public
		$data,
		$prev=false,
		$next=false;

	public function __construct($data) {
		$this->data=$data;
	}

	public function add($data) {
		if ($this->data<$data) {
			if ($this->next) {
				$this->next->add($data);
			} else {
				$this->next=new nodeElement($data);
			}
		} else {
			if ($this->prev) {
				$this->prev->add($data);
			} else {
				$this->prev=new nodeElement($data);
			}
		}
	}

	public function show() {
		if ($this->prev) $this->prev->show();
		echo $this->data,'<br />';
		if ($this->next) $this->next->show();
	}
}

class nodeTree {
	public
		$first=false;

	public function add($data) {
		if ($this->first) {
			$this->first->add($data);
		} else {
			$this->first=new nodeElement($data);
		}
	}

	public function show() {
		if ($this->first) {
			$this->first->show();
		}
	}

}

$test=new nodeTree();
$test->add(12);
$test->add(10);
$test->add(3);
$test->add(15);
$test->show();

?>

Should output:
3
10
12
15

showing the btree sorting in action. you can print_r $test to see the actual structure working. The big trick is using the boolean false for unassigned nodes. Doing things like deleting nodes would be much more complex, and a good version wouldn’t use recursion for the add function.

3

Here’s a version without the recursive add – so it would use way less memory when adding large data sets as it’s not making endless copies of the data being added to the tree.


<?php
class nodeElement {
	public
		$data,
		$prev=false,
		$next=false;

	public function __construct($data) {
		$this->data=$data;
	}

	public function show() {
		if ($this->prev) $this->prev->show();
		echo $this->data,'<br />';
		if ($this->next) $this->next->show();
	}
}

class nodeTree {
	public
		$first=false;

	public function add($data) {
		if ($this->first) {
			$current=$this->first;
			while (true) {
				if (strnatcasecmp($current->data,$data)<0) {
					if ($current->next) {
						$current=$current->next;
					} else {
						$current->next=new nodeElement($data);
						break;
					}
				} else {
					if ($current->prev) {
						$current=$current->prev;
					} else {
						$current->prev=new nodeElement($data);
						break;
					}
				}
			}
		} else {
			$this->first=new nodeElement($data);
		}
	}

	public function show() {
		if ($this->first) {
			$this->first->show();
		}
	}

}

$test=new nodeTree();
$test->add('bravo');
$test->add('charlie');
$test->add('echo');
$test->add('alpha');
$test->add('delta');
$test->show();

?>