Created
August 23, 2016 15:16
-
-
Save antoniopicone/8122ac18f096a38277187315342b88cf to your computer and use it in GitHub Desktop.
A Binary Tree implementation with DFS and BFS traversal algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
class Node { | |
public $data; | |
public $next; | |
public function __construct($data) | |
{ | |
$this->data = $data; | |
$this->next = NULL; | |
} | |
public function getData() | |
{ | |
return $this->data; | |
} | |
} | |
class Stack { | |
private $top; | |
public function __construct() | |
{ | |
$this->top = NULL; | |
} | |
public function push($data) { | |
$new = new Node($data); | |
$new->next = $this->top; | |
$this->top = &$new; | |
} | |
public function pop() { | |
if($this->isEmpty()) throw new Exception("Stack is empty"); | |
$top = $this->top; | |
$this->top = $this->top->next; | |
return $top->getData(); | |
} | |
public function peek() { | |
if($this->isEmpty()) throw new Exception("Stack is empty"); | |
return $this->top->getData(); | |
} | |
public function isEmpty() { | |
return $this->top == NULL; | |
} | |
} | |
class Queue { | |
private $head; | |
private $tail; | |
public function __construct() | |
{ | |
$this->head = $this->tail = NULL; | |
} | |
public function isEmpty() { | |
return $this->head == NULL; | |
} | |
public function enqueue($data) { | |
$new = new Node($data); | |
if($this->tail == NULL) { | |
$this->head = &$new; | |
} | |
else { | |
$this->tail->next = &$new; | |
} | |
$this->tail = &$new; | |
} | |
public function dequeue() { | |
if($this->isEmpty()) throw new Exception("Queue is empty"); | |
$head = $this->head; | |
$this->head = $this->head->next; | |
return $head->getData(); | |
} | |
} | |
class BTNode { | |
public $data; | |
public $left; | |
public $right; | |
public function __construct($data) | |
{ | |
$this->data = $data; | |
$this->left = $this->right = NULL; | |
} | |
public function getData() { | |
return $this->data; | |
} | |
} | |
class BinaryTree { | |
private $root; | |
public function __construct($root, $adiacence_list) | |
{ | |
$nodes = array(); | |
foreach ($adiacence_list as $node => $leaves) { | |
if(!isset($nodes[$leaves[0]]) && $leaves[0] != NULL) { | |
$left = new BTNode($leaves[0]); | |
$nodes[$leaves[0]] = $left; | |
} | |
if(!isset($nodes[$leaves[1]]) && $leaves[1] != NULL) { | |
$right = new BTNode($leaves[1]); | |
$nodes[$leaves[1]] = $right; | |
} | |
$this_node = new BTNode($node); | |
if($leaves[0] != NULL) $this_node->left = &$nodes[$leaves[0]]; | |
if($leaves[1] != NULL) $this_node->right = &$nodes[$leaves[1]]; | |
$nodes[$node] = $this_node; | |
} | |
$this->root = &$nodes[$root]; | |
$nodes = NULL; | |
} | |
public function BFS() { | |
$visited = array(); | |
$out = array(); | |
$queue = new Queue(); | |
$queue->enqueue($this->root); | |
$visited[$this->root->getData()] = true; | |
$out[]=$this->root->getData(); | |
while(!$queue->isEmpty()) { | |
$current = $queue->dequeue(); | |
if($current->left != NULL && !isset($visited[$current->left->getData()])) { | |
$queue->enqueue($current->left); | |
$visited[$current->left->getData()] = true; | |
$out[]= $current->left->getData(); | |
} | |
if($current->right != NULL && !isset($visited[$current->right->getData()])) { | |
$queue->enqueue($current->right); | |
$visited[$current->right->getData()] = true; | |
$out[]= $current->right->getData(); | |
} | |
$visited[$current->getData()] = true; | |
} | |
return $out; | |
} | |
public function DFS() { | |
$visited = array(); | |
$stack = new Stack(); | |
$out = array(); | |
$stack->push($this->root); | |
$visited[$this->root->getData()] = true; | |
$out[]= $this->root->getData(); | |
while (!$stack->isEmpty()) { | |
$current = $stack->peek(); | |
if($current->left != NULL && !isset($visited[$current->left->getData()])) { | |
$visited[$current->left->getData()] = true; | |
$stack->push($current->left); | |
$out[] = $current->left->getData(); | |
continue; | |
} | |
if($current->right != NULL && !isset($visited[$current->right->getData()])) { | |
$visited[$current->right->getData()] = true; | |
$stack->push($current->right); | |
$out[] = $current->right->getData(); | |
continue; | |
} | |
$stack->pop(); | |
} | |
return $out; | |
} | |
} | |
$adiacence_list = array( | |
'a' => array('b','c'), | |
'b' => array(NULL,'e'), | |
'c' => array(NULL, 'd') | |
); | |
$bt = new BinaryTree('a',$adiacence_list); | |
var_dump($bt->BFS()); | |
var_dump($bt->DFS()); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
$map = [
"A" => ["B","C","D"],
"B" => ["M","N"],
"C" => ["L"],
"D" => ["O","P"],
"M" => ["X","Y"],
"N" => ["U","V"],
"O" => ["I","J"],
"Y" => ["R","S"],
"X" => [],
"L" => [],
"P" => [],
"U" => [],
"V" => ["G","H"],
"I" => [],
"J" => [],
"R" => [],
"S" => [],
"G" => [],
"H" => []
];
$bt = new BinaryTree('A',$map);
var_dump($bt->BFS()); // it's NOT as I expected