이번에는 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 중국어 웹사이트의 다른 관련 기사를 주목하세요!
추천 자료:
JS 배열 및 JSON 객체를 동적으로 추가, 수정 및 삭제하는 방법
Vue+Nuxt.js를 사용하여 서버 측 렌더링을 구현하는 방법
위 내용은 PHP를 사용하여 이진 트리를 정렬하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!