fork download
copy 
  1. <?php
  2. /*
  3. Binary Search tree
  4. - Insert
  5. - Search
  6. - Delete
  7. - traversals (inorder, preorder, postorder)
  8. */
  9.  
  10. class Node {
  11.  
  12.       public $data;
  13.       public $left;
  14.       public $right;
  15.  
  16.       function __construct( $key ) {
  17.  
  18.           $this->data = $key;
  19.           $this->left = NULL;
  20.           $this->right = NULL;
  21.       }
  22. }
  23.  
  24. function mostlyRightMin($root) {
  25.  
  26.          if($root->left) {
  27.  
  28.             $root = $root->left;
  29.          }
  30.  
  31.          return $root;
  32. }
  33.  
  34. function delete($root, $key) {
  35.  
  36.          if($root == NULL) {
  37.  
  38.             return $root;
  39.  
  40.          } else if( $root->data > $key ){
  41.  
  42.              $root->left = delete($root->left, $key);
  43.  
  44.          } else if( $root->data < $key ) {
  45.  
  46.              $root->right = delete($root->right, $key);
  47.  
  48.          } else {
  49.  
  50.              if($root->left == NULL && $root->right == NULL) {
  51.  
  52.                 $root = NULL;
  53.  
  54.              } else if($root->left == NULL) {
  55.  
  56.                 $temp = $root->right;
  57.  
  58.                 $root = NULL;
  59.  
  60.                 return $temp;
  61.  
  62.              } else if($root->right == NULL) {
  63.  
  64.                $temp = $root->left;
  65.  
  66.                $root = NULL;
  67.  
  68.                return $temp;
  69.  
  70.              } else if($root->left != NULL && $root->right != NULL ) {
  71.  
  72.                $temp = mostlyRightMin($root->right);
  73.  
  74.                $root->data = $temp->data;
  75.  
  76.                $root->right = delete($root->right, $temp->data);
  77.              }
  78.  
  79.          }
  80.  
  81.          return $root;
  82. }
  83.  
  84. function search($root, $key) {
  85.  
  86.          if($root == NULL) {
  87.            return 0;
  88.          } else if($root->data > $key) {
  89.             return search($root->left, $key);
  90.          } else if($root->data < $key) {
  91.             return search($root->right, $key);
  92.          }
  93.          return 1;
  94. }
  95.  
  96. function insert($root, $key) {
  97.  
  98.          if($root == NULL) {
  99.  
  100.             $root = new Node( $key );
  101.  
  102.             $root->left = NULL;
  103.  
  104.             $root->right = NULL;
  105.  
  106.          } else if($root->data > $key) {
  107.  
  108.             $root->left = insert($root->left, $key);
  109.  
  110.          } else if($root->data < $key) {
  111.  
  112.             $root->right = insert($root->right, $key);
  113.          }
  114.  
  115.          return $root;
  116. }
  117.  
  118. function inorder($root) {
  119.  
  120.     if($root != NULL) {
  121.  
  122.       inorder($root->left);
  123.  
  124.       printf("%d ", $root->data);
  125.  
  126.       inorder($root->right);
  127.     }
  128. }
  129.  
  130. function preorder($root) {
  131.  
  132.     if($root != NULL) {
  133.  
  134.       printf("%d ", $root->data);
  135.  
  136.       inorder($root->left);
  137.  
  138.       inorder($root->right);
  139.     }
  140. }
  141.  
  142. function postorder($root) {
  143.  
  144.     if($root != NULL) {
  145.  
  146.       inorder($root->left);
  147.  
  148.       inorder($root->right);
  149.  
  150.       printf("%d ", $root->data);
  151.     }
  152. }
  153.  
  154. $arrayName = array(9,8,7,11,0,5,4,3,2,1,15,-11);
  155.  
  156. echo"<pre>";
  157.  
  158. print_r( $arrayName );
  159.  
  160. echo"</pre>";
  161.  
  162. $root = new Node(10);
  163.  
  164. foreach ($arrayName as $key => $value) {
  165.  
  166.          insert($root, $value);
  167. }
  168.  
  169. inorder($root);
  170.  
  171. printf("Search for %d: %d\n",11, search($root, 11));
  172.  
  173. $key = 10;
  174.  
  175. printf("Deleted: %d\n",$key);
  176.  
  177. delete($root, $key);
  178.  
  179. inorder($root);
  180. ?>
  181.  
Success #stdin #stdout 0.03s 26320KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
<pre>Array
(
    [0] => 9
    [1] => 8
    [2] => 7
    [3] => 11
    [4] => 0
    [5] => 5
    [6] => 4
    [7] => 3
    [8] => 2
    [9] => 1
    [10] => 15
    [11] => -11
)
</pre>-11 0 1 2 3 4 5 7 8 9 10 11 15 Search for 11: 1
Deleted: 10
-11 0 1 2 3 4 5 7 8 9 11 15
https://ideone.com/FGMLLU
BST recursive
language:
PHP (php 7.3.5)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!