So sortieren Sie einen Binärbaum mit PHP

Dieses Mal zeige ich Ihnen, wie Sie PHP zum Sortieren eines Binärbaums verwenden. Was sind die Vorsichtsmaßnahmen für die Verwendung von PHP zum Sortieren eines Binärbaums?

Hier ist eine Demonstration der Funktionen des Einfügens sortierter Binärbaumknoten, der In-Order-Traversierung, der Suche nach Extremwerten und der Suche nach spezifischen Werten.

Es werden grundsätzlich keine Konzepte und Definitionen bereitgestellt Bitte lesen Sie zunächst diesen Artikel, um einige der in diesem Artikel bereitgestellten Konzepte zu lesen Deine harte Arbeit.

Binärbaum:In der Informatik ist ein Binärbaum eine Baumstruktur mit höchstens zwei Teilbäumen pro Knoten.

Sortierter Binärbaum: Der Wert des linken untergeordneten Knotens ist kleiner als der Wert des übergeordneten Knotens und der Wert des rechten untergeordneten Knotens ist größer als der Wert des übergeordneten Knotens .

Ein paar Konzepte:

Wurzelknoten

Blattknoten

Linker Teilbaum

Rechter Teilbaum

Durchquerung in der Reihenfolge
Vorbestellung Traversal
Post-Order-Traversal
Binärbaumsuche



In-Order-Traversal:

Durchqueren Sie dann zuerst den linken Teilbaum Durchqueren Sie den aktuellen Knoten und dann den rechten Knoten. Das Ergebnis nach der Durchquerung ist das sortierte Ergebnis von

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

Laufergebnis:

Gefunden 7

Dort So etwas gibt es nicht!

Ich glaube, Sie haben den Fall in diesem Artikel gelesen. Nachdem Sie die Methode gemeistert haben, achten Sie bitte auf andere verwandte Artikel auf der chinesischen PHP-Website, um weitere spannende Inhalte zu erhalten!

Empfohlene Lektüre:

So fügen Sie JS-Arrays und JSON-Objekte dynamisch hinzu, ändern und löschen sie

Verwendung Vue +Nuxt.js implementiert serverseitiges Rendering

Das obige ist der detaillierte Inhalt vonSo sortieren Sie einen Binärbaum mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!