Comment trier un arbre binaire en utilisant PHP

Cette fois, je vais vous montrer comment utiliser PHP pour trier un arbre binaire. Quelles sont les précautions pour utiliser PHP pour trier un arbre binaire. Ce qui suit est un cas pratique, jetons un coup d'œil.

Voici une démonstration des fonctions d'insertion de nœuds d'arbre binaire triés, de parcours dans l'ordre, de recherche de valeurs extrêmes et de recherche de valeurs spécifiques

Fondamentalement, aucun concept ni définition n'est fourni. pour avoir une brève compréhension d'abord. Veuillez lire cet article pour plusieurs concepts fournis dans cet article

En fait, le code est simplement fourni, et il y a très peu de commentaires. votre travail acharné.

Arbre binaire :En informatique, un arbre binaire est une structure arborescente avec au plus deux sous-arbres par nœud.

Arbre binaire trié : La valeur du nœud enfant de gauche est inférieure à la valeur du nœud parent, et la valeur du nœud enfant de droite est supérieure à la valeur du nœud parent .

Quelques concepts :

Nœud racine
Nœud feuille
Sous-arbre gauche
Sous-arbre droit
Parcours dans l'ordre
Précommande parcours
Parcours post-ordre
Recherche d'arbre binaire

Parcours dans l'ordre :

Parcourez d'abord le sous-arbre de gauche, puis parcourir le nœud actuel, puis traverser le nœud de droite. Le résultat après le parcours est le résultat trié de

// 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);

Résultat d'exécution :

Trouvé 7
Cela n'existe pas !

Je crois avoir lu le cas dans cet article Vous maîtrisez la méthode Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Comment ajouter, modifier et supprimer dynamiquement des tableaux JS et des objets JSON

Comment utiliser Vue +Nuxt.js implémente le rendu côté serveur

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!