SitePoint Sponsor

User Tag List

Results 1 to 3 of 3
  1. #1
    SitePoint Member
    Join Date
    Sep 2011
    Posts
    12
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Binary tree using php

    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. #2
    Non-Member bronze trophy
    Join Date
    Nov 2009
    Location
    Keene, NH
    Posts
    3,760
    Mentioned
    23 Post(s)
    Tagged
    0 Thread(s)
    This is a very simple example and relies on method recursion, but at least shows it's possible using objects.

    Code:
    <?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. #3
    Non-Member bronze trophy
    Join Date
    Nov 2009
    Location
    Keene, NH
    Posts
    3,760
    Mentioned
    23 Post(s)
    Tagged
    0 Thread(s)
    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.

    Code:
    <?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();
    
    ?>


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •