Detailed explanation of the definition method of complete binary tree in PHP-PHP Tutorial-php.cn

Detailed explanation of the definition method of complete binary tree in PHP

黄舟

Release： 2023-03-16 15:06:01

Original

1744 people have browsed it

This article mainly introduces the definition and implementation method of complete binary tree in PHP. It briefly describes the concept of complete binary tree and gives the definition of complete binary tree, node search, adding, setting, printing and other related operation skills in the form of examples. It is required Friends can refer to

This article describes the definition and implementation method of a complete binary tree in PHP. Share it with everyone for your reference. The details are as follows:

If the depth of the binary tree is h, except for the h-th layer, the number of nodes in each other layer (1~h-1) reaches the maximum number. All the nodes in level h are continuously concentrated on the leftmost side, which is a complete binary tree.

PHP code implementation (temporarily implement adding nodes, traversing nodes hierarchically, and deleting nodes for subsequent updates)

<?php
class Node{
  public $value;
  public $leftNode;
  public $rightNode;
}
/* 找到空节点 */
function findEmpytNode($node, $parent = null){
  if(empty($node->value)){
    return $node;
  }else{
    if(empty($node->leftNode->value)){
      return $node->leftNode;
    }else if(empty($node->rightNode->value)){
      return $node->rightNode;
    }else{
      if(empty($parent) || $node->value == $parent->rightNode->value){
        return findEmpytNode($node->leftNode, $node);
      }else{
        return findEmpytNode($parent->rightNode, $node);
      }
    }
  }
}
/* 添加节点 */
function addNode($node, $value){
  $emptyNode = findEmpytNode($node);
  setNode($emptyNode, $value);
}
/* 设置节点 */
function setNode($node, $value){
  $node->value = $value;
  $node->leftNode = new Node();
  $node->rightNode = new Node();
}
/* 打印 */
function printTree($node, $parent = null){
  if(empty($node->value)) return ;
  echo $node->leftNode->value;
  echo $node->rightNode->value;
  if(empty($parent) || $node->value == $parent->rightNode->value){
    printTree($node->leftNode, $node);
  }else{
    printTree($parent->rightNode, $node);
  }
}
$head = new Node();
setNode($head, 1);
addNode($head, 2);
addNode($head, 3);
addNode($head, 4);
addNode($head, 5);
addNode($head, 6);
printTree($head);

Copy after login

The above is the detailed content of Detailed explanation of the definition method of complete binary tree in PHP. For more information, please follow other related articles on the PHP Chinese website!