TJRoger · December 21, 2015 23:24 · Dec 9, 2011 · Dec 8, 2011 · Dec 8, 2011
diff --git a/gistfile1.aw b/gistfile1.aw
@@ -1,5 +1,13 @@
 <?php
 
+/**
+ * by Adrian Statescu <[email protected]>
+ * Twitter: @thinkphp
+ * G+     : http://gplus.to/thinkphp
+ * MIT Style License
+ */
+
+
     class Node {
 
           public $info;

diff --git a/gistfile1.aw b/gistfile1.aw
@@ -67,7 +67,7 @@
                  }
           }
 
-          public function travers($method) {
+          public function traverse($method) {
 
                  switch($method) {
 
@@ -89,7 +89,7 @@
 
           } 
 
-          public function _inorder($node) {
+          private function _inorder($node) {
 
                           if($node->left) {
                              $this->_inorder($node->left); 
@@ -103,7 +103,7 @@
           }
 
 
-          public function _preorder($node) {
+          private function _preorder($node) {
 
                           echo $node. " ";
 
@@ -118,7 +118,7 @@
           }
 
 
-          public function _postorder($node) {
+          private function _postorder($node) {
 
 
                           if($node->left) {
@@ -174,28 +174,39 @@
                 return join($out,""); 
           }
     } 
+               $arr = array(8,3,1,6,4,7,10,14,13);
 
                $tree = new SearchBinaryTree();
-               $tree->create(8);
-               $tree->create(3);
-               $tree->create(1);
-               $tree->create(6);
-               $tree->create(4);
-               $tree->create(7);
-               $tree->create(10);
-               $tree->create(14);
-               $tree->create(13);
+               for($i=0,$n=count($arr);$i<$n;$i++) {
+                   $tree->create($arr[$i]);
+               }
+$str = <<<INTRO
+     In computer science, a binary search tree (BST) is a node-based binary tree structure which has the following
+properties:
+<ul>
+<li>the left subtree of a node contains only nodes with keys less than the node's key</li>
+<li>the right subtree of a node contains only nodes with keys greater than the node's key</li>
+<li>both the left and right subtrees must also be binary search trees</li>
+</ul> 
+INTRO;
+
+    echo"<h1>Binary Search Tree</h1>"; 
+
+    echo"<p>$str</p>"; 
 
+    echo "<h2>Input vector: ", join($arr," "), "</h2>";
 
     echo"<h1>Breadh-First Traversal Tree</h1>"; 
     echo $tree->BFT();
 
     echo"<h1>Inorder</h1>"; 
-    $tree->travers('inorder');
+    $tree->traverse('inorder');
 
 
     echo"<h1>Postorder</h1>"; 
-    $tree->travers('postorder');
+    $tree->traverse('postorder');
 
     echo"<h1>Preorder</h1>"; 
-    $tree->travers('preorder');
+    $tree->traverse('preorder');
+
+?>
diff --git a/gistfile1.aw b/gistfile1.aw
@@ -0,0 +1,201 @@
+<?php
+
+    class Node {
+
+          public $info;
+          public $left;
+          public $right;
+          public $level;
+
+          public function __construct($info) {
+                 $this->info = $info;
+                 $this->left = NULL;
+                 $this->right = NULL;
+                 $this->level = NULL;
+          }
+
+          public function __toString() {
+
+                 return "$this->info";
+          }
+    }  
+
+
+    class SearchBinaryTree {
+
+          public $root;
+
+          public function  __construct() {
+                 $this->root = NULL;
+          }
+
+          public function create($info) {
+
+                 if($this->root == NULL) {
+
+                    $this->root = new Node($info);
+
+                 } else {
+
+                    $current = $this->root;
+
+                    while(true) {
+
+                          if($info < $current->info) {
+
+                                if($current->left) {
+                                   $current = $current->left;
+                                } else {
+                                   $current->left = new Node($info);
+                                   break; 
+                                }
+
+                          } else if($info > $current->info){
+
+                                if($current->right) {
+                                   $current = $current->right;
+                                } else {
+                                   $current->right = new Node($info);
+                                   break; 
+                                }
+
+                          } else {
+
+                            break;
+                          }
+                    } 
+                 }
+          }
+
+          public function travers($method) {
+
+                 switch($method) {
+
+                     case 'inorder':
+                     $this->_inorder($this->root);
+                     break;
+
+                     case 'postorder':
+                     $this->_postorder($this->root);
+                     break;
+
+                     case 'preorder':
+                     $this->_preorder($this->root);
+                     break;
+
+                     default:
+                     break;
+                 } 
+
+          } 
+
+          public function _inorder($node) {
+
+                          if($node->left) {
+                             $this->_inorder($node->left); 
+                          } 
+
+                          echo $node. " ";
+
+                          if($node->right) {
+                             $this->_inorder($node->right); 
+                          } 
+          }
+
+
+          public function _preorder($node) {
+
+                          echo $node. " ";
+
+                          if($node->left) {
+                             $this->_preorder($node->left); 
+                          } 
+
+
+                          if($node->right) {
+                             $this->_preorder($node->right); 
+                          } 
+          }
+
+
+          public function _postorder($node) {
+
+
+                          if($node->left) {
+                             $this->_postorder($node->left); 
+                          } 
+
+
+                          if($node->right) {
+                             $this->_postorder($node->right); 
+                          } 
+
+                          echo $node. " ";
+          }
+
+
+          public function BFT() {
+
+                 $node = $this->root;
+
+                 $node->level = 1; 
+
+                 $queue = array($node);
+
+                 $out = array("<br/>");
+
+
+                 $current_level = $node->level;
+
+
+                 while(count($queue) > 0) {
+
+                       $current_node = array_shift($queue);
+
+                       if($current_node->level > $current_level) {
+                            $current_level++;
+                            array_push($out,"<br/>");  
+                       } 
+
+                       array_push($out,$current_node->info. " ");
+
+                       if($current_node->left) {
+                          $current_node->left->level = $current_level + 1;
+                          array_push($queue,$current_node->left); 
+                       }    
+
+                       if($current_node->right) {
+                          $current_node->right->level = $current_level + 1;
+                          array_push($queue,$current_node->right); 
+                       }    
+                 }
+
+
+                return join($out,""); 
+          }
+    } 
+
+               $tree = new SearchBinaryTree();
+               $tree->create(8);
+               $tree->create(3);
+               $tree->create(1);
+               $tree->create(6);
+               $tree->create(4);
+               $tree->create(7);
+               $tree->create(10);
+               $tree->create(14);
+               $tree->create(13);
+
+
+    echo"<h1>Breadh-First Traversal Tree</h1>"; 
+    echo $tree->BFT();
+
+    echo"<h1>Inorder</h1>"; 
+    $tree->travers('inorder');
+
+
+    echo"<h1>Postorder</h1>"; 
+    $tree->travers('postorder');
+
+    echo"<h1>Preorder</h1>"; 
+    $tree->travers('preorder');