집 >백엔드 개발 >PHP 튜토리얼 >PHP를 사용하여 이진 트리를 정렬하는 방법

PHP를 사용하여 이진 트리를 정렬하는 방법

php中世界最好的语言원래의: 2018-05-28 09:53:522035검색

이번에는 PHP를 사용하여 이진 트리를 정렬하는 방법과 PHP를 사용하여 이진 트리를 정렬할 때 어떤 주의사항이 있는지 보여드리겠습니다. 다음은 실제 사례입니다. 살펴보겠습니다.

정렬된 이진 트리 노드 삽입, 순차 순회, 극값 검색 및 특정 값 검색 기능에 대한 데모입니다.

기본적으로 여기에 제공된 몇 가지 개념과 정의는 간략하게 이해하는 것이 좋습니다.

사실 코드는 간단하게 제공되고 댓글도 거의 없습니다. 수고해 주셔서 감사합니다.

이진 트리:컴퓨터 과학에서 이진 트리는 트리입니다. 각 노드에는 최대 2개의 하위 트리가 있는 구조입니다.

정렬된 이진 트리: 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큽니다.

몇 가지 개념:

루트 노드
리프 노드
왼쪽 자식 트리
오른쪽 자식 트리
순서 순회
선순서 순회
후순 순회
이진 트리 검색

순서 순회:

먼저 왼쪽 순회 하위 트리를 탐색한 후 이 노드를 탐색한 다음 오른쪽 노드를 탐색합니다. 탐색 후 결과는 정렬입니다.

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

실행 결과:

Found 7
그런 건 없습니다!

마스터하신 것 같아요. 이 기사의 사례를 읽은 후 방법을 알아보십시오. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!