How to sort a binary tree using PHP

This time I will show you how to use PHP to sort a binary tree, and what are the precautions for using PHP to sort a binary tree. The following is a practical case, let's take a look.

This demonstrates the functions of inserting sorted binary tree nodes, in-order traversal, extreme value search and specific value search.

Basically no concepts and definitions are provided. It is recommended to have a brief understanding first. Please read this article for several concepts provided in this article.

In fact, the code is simply provided, and there are very few

comments. Thank you for your hard work.

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

Sort binary 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
In-order traversal
Pre-order traversal
Post-order traversal
Binary tree search

In-order traversal:

First traverse the left subtree, then traverse the current node, then traverse the right node. The result after the traversal is the sorted The result

// created by 曲朋维
// 排序二叉树
// 完成以下任务.
// 1. 将节点插入到对应位置
// 2. 使用中序遍历遍历这个二叉树
// 3. 找到这个二叉树的极值
// 4. 搜索一个特定的值
class Node{
  public $key,$left,$right;
  public function construct($key)
  {
    $this->key = $key;
  }
}
class BinaryTree{
  public $root;
  public $sortArr = [];
  // 插入节点
  public function insertNode($node,$newNode){
    if ($node->key < $newNode->key){
      // 如果父节点小于子节点,插到右边
      if (empty($node->right)){
        $node->right = $newNode;
      }else{
        $this->insertNode($node->right,$newNode);
      }
    }elseif ($node->key > $newNode->key){
      // 如果父节点大于子节点,插到左边
      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);
    }
  }
  // 中序遍历
  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);
    }
  }
  // 寻找极值
  public function findMin(){
    //不断的找它的左子树,直到这个左子树的节点为叶子节点.
    if (!empty($this->root)){
      $this->findMinNode($this->root);
    }
  }
  public function findMinNode(Node $node){
    if (!empty($node->left)){
      $this->findMinNode($node->left);
    }else{
      echo '这个二叉树的最小值为:'.$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 '这个二叉树的最大值为:'.$node->key;
    }
  }
  // 查找特定的值
  public function find($val = ''){
    if (!empty($val)){
      $this->findNode($this->root,$val);
    }
  }
  public function findNode(Node $node,$val){
    if ($node->key == $val){
      echo '找到'.$val.'了';
    }else if ($node->key > $val){
      // 如果 父节点的值 大于要查找的值,那么查找它的左子树
      if (!empty($node->left)){
        $this->findNode($node->left,$val);
      }else{
        echo '没有这个东西!';
      }
    }else if ($node->key < $val){
      if (!empty($node->right)){
        $this->findNode($node->right,$val);
      }else{
        echo '没有这个东西!';
      }
    }
  }
}
$tree = new BinaryTree();
// 节点插入
$nodes = array(8,3,10,1,6,14,4,7,13);
foreach ($nodes as $value){
  $tree->insert($value);
}
// 中序遍历
//$tree->midSort();
//print_r($tree->sortArr);
// 寻找极值
//$tree->findMin();
//$tree->findMax();
// 查找特定的值
$tree->find(7);
echo "<br/>";
$tree->find(11);

Copy after login

Run result:

Found 7

There is no such thing!

I believe you have read the case in this article After mastering the method, please pay attention to other related articles on the php Chinese website for more exciting content!

Recommended reading:

How to dynamically add, modify, and delete JS arrays and JSON objects

How to use Vue Nuxt.js implements server-side rendering

The above is the detailed content of How to sort a binary tree using PHP. For more information, please follow other related articles on the PHP Chinese website!