Example of PHP Sorting Binary Tree Basic Function Implementation Method

In this paper, the basic function implementation method of PHP sorting 2-tree is described with examples. Share it for your reference, as follows:

Here, we demonstrate the functions of sorting 2-tree node insertion, middle order traversal, extreme value search and specific value search.

Basic does not provide any concepts and definitions. Suggest a simple understanding of 1 below this article to provide several concepts to see this article.

In fact, it simply provides the code, and there are few comments. You have worked hard.

2-tree: In computer science, a 2-tree is a tree structure with at most two subtrees per node.

Sort 2-tree: The value of the left child node is less than the value of the parent node, and the value of the right child node is greater than the value of the parent node.

Several concepts:

Root node
Leaf node
Left subtree
Right subtree
Middle order traversal
Preorder traversal
Post-order traversal
2-tree lookup

Middle order traversal:

Traverse the left subtree first, traverse this node, and traverse the right node. The result after traversing is the result after sorting

// created by  Qu Pengwei 
//  Sort 2 Fork tree 
//  Complete the following tasks .
// 1.  Insert the node into the corresponding position 
// 2.  Use middle order traversal to traverse this 2 Fork tree 
// 3.  Find this 2 Extreme value of fork tree 
// 4.  Search 1 Specific values 
class Node{
  public $key,$left,$right;
  public function __construct($key)
  {
    $this->key = $key;
  }
}
class BinaryTree{
  public $root;
  public $sortArr = [];
  //  Insert node 
  public function insertNode($node,$newNode){
    if ($node->key < $newNode->key){
      //  If the parent node is smaller than the child node , Insert to the right 
      if (empty($node->right)){
        $node->right = $newNode;
      }else{
        $this->insertNode($node->right,$newNode);
      }
    }elseif ($node->key > $newNode->key){
      //  If the parent node is larger than the child node , Insert to the left 
      if (empty($node->left)){
        $node->left = $newNode;
      }else{
        $this->insertNode($node->left,$newNode);
      }
    }
  }
  public function insert($key){
    $newNode = new Node($key);
    if (empty($this->root)){
      $this->root = $newNode;
    }else{
      $this->insertNode($this->root,$newNode);
    }
  }
  //  Middle order traversal 
  public function midSort(){
    $this->midSortNode($this->root);
  }
  public function midSortNode($node){
    if (!empty($node)){
      $this->midSortNode($node->left);
      array_push($this->sortArr,$node->key);
      $this->midSortNode($node->right);
    }
  }
  //  Searching for Extreme Value 
  public function findMin(){
    // Keep looking for its left subtree , Until the node of this left subtree is a leaf node .
    if (!empty($this->root)){
      $this->findMinNode($this->root);
    }
  }
  public function findMinNode(Node $node){
    if (!empty($node->left)){
      $this->findMinNode($node->left);
    }else{
      echo ' This 2 The minimum value of the fork tree is :'.$node->key;
    }
  }
  public function findMax(){
    if (!empty($this->root)){
      $this->findMaxNode($this->root);
    }
  }
  public function findMaxNode(Node $node){
    if (!empty($node->right)){
      $this->findMaxNode($node->right);
    }else{
      echo ' This 2 The maximum value of the fork tree is :'.$node->key;
    }
  }
  //  Find a specific value 
  public function find($val = ''){
    if (!empty($val)){
      $this->findNode($this->root,$val);
    }
  }
  public function findNode(Node $node,$val){
    if ($node->key == $val){
      echo ' Find '.$val.' It's over ';
    }else if ($node->key > $val){
      //  If   The value of the parent node   Is greater than the value to find , Then look for its left subtree 
      if (!empty($node->left)){
        $this->findNode($node->left,$val);
      }else{
        echo ' There is no such thing !';
      }
    }else if ($node->key < $val){
      if (!empty($node->right)){
        $this->findNode($node->right,$val);
      }else{
        echo ' There is no such thing !';
      }
    }
  }
}
$tree = new BinaryTree();
//  Node insertion 
$nodes = array(8,3,10,1,6,14,4,7,13);
foreach ($nodes as $value){
  $tree->insert($value);
}
//  Middle order traversal 
//$tree->midSort();
//print_r($tree->sortArr);
//  Searching for Extreme Value 
//$tree->findMin();
//$tree->findMax();
//  Find a specific value 
$tree->find(7);
echo "<br/>";
$tree->find(11);

Run results:

Found 7
There is no such thing!

For more readers interested in PHP related contents, please check the special topics of this site: "PHP Data Structure and Algorithm Tutorial", "php Programming Algorithm Summary", "php String (string) Usage Summary", "PHP Array (Array) Operation Skills Complete Book", "PHP Common Traversal Algorithms and Skills Summary" and "PHP Mathematical Operation Skills Summary"

I hope this article is helpful to everyone's PHP programming.