이진 트리는 컴퓨터 과학의 기본 데이터 구조로, 컴퓨터 과학에서 검색 및 정렬을 위해 사용되는 등 가장 일반적인 트리 구조이며, 컴퓨터 과학의 다른 많은 분야에서도 사용됩니다. PHP는 동적 웹 개발을 지원하는 널리 사용되는 서버측 스크립팅 언어입니다. 이번 글에서는 PHP를 이용하여 바이너리 트리를 구현하는 방법을 소개하겠습니다.
이진 트리란 무엇인가요?
이진 트리는 여러 노드로 구성되며 각 노드에는 최대 2개의 하위 노드가 있습니다. 세 가지 속성이 있습니다:
이진 트리는 다음 범주로 나뉩니다.
이진 트리를 구현하려면
클래스를 사용하여 이진 트리 구조를 정의할 수 있습니다. 각 노드는 다음 속성을 가진 개체입니다.
노드를 나타내는 클래스를 만듭니다.
class Node {
public $value;
public $left;
public $right;
function __construct($value){
$this -> value = $value;
$this -> left = null;
$this -> right = null;
}
}다음으로 이진 트리를 나타내는 클래스를 만들어야 합니다.
class BinarySearchTree {
public $root;
function __construct() {
$this -> root = null;
}
}다음으로 이진 트리에 대해 다음 메서드를 정의합니다.
Insert Node
Insert Node 방법은 새 노드를 올바른 위치에 삽입합니다. 트리가 비어 있으면 새 노드는 루트 노드입니다. 그렇지 않으면 루트 노드에서 현재 노드의 값을 비교하기 시작합니다.
삽입 방법에 대한 코드는 다음과 같습니다.
function insert($value) {
$newNode = new Node($value);
if ($this -> root == null) {
$this -> root = $newNode;
} else {
$current = $this -> root;
while (true) {
if ($value < $current -> value) {
if ($current -> left == null) {
$current -> left = $newNode;
return;
} else {
$current = $current -> left;
}
} else if ($value > $current -> value) {
if ($current -> right == null) {
$current -> right = $newNode;
return;
} else {
$current = $current -> right;
}
} else {
return;
}
}
}
}Find Node
Find Node 방법은 간단한 재귀 방법입니다. 루트 노드부터 시작하여 노드 값을 비교합니다. 값이 같으면 현재 노드를 반환합니다. 그렇지 않고 노드의 값이 찾고 있는 값보다 작으면 왼쪽 하위 트리를 계속 검색합니다. 값이 찾고 있는 값보다 크면 오른쪽 하위 트리를 계속 검색하세요.
find 메소드의 코드는 다음과 같습니다.
function search($value) {
$current = $this -> root;
while ($current != null) {
if ($value == $current -> value) {
return $current;
} else if ($value < $current -> value) {
$current = $current -> left;
} else {
$current = $current -> right;
}
}
return null;
}Delete Node
노드 삭제 메소드는 전체 구현에서 가장 복잡한 메소드 중 하나입니다. 노드 삭제 방법은 노드의 하위 항목 수에 따라 다릅니다. 다음과 같은 상황이 있을 수 있습니다.
삭제 메소드의 코드는 다음과 같습니다.
function delete($value) {
$current = $this -> root;
$parent = null;
while ($current != null) {
if ($value == $current -> value) {
if ($current -> left == null && $current -> right == null) {
if ($parent == null) {
$this -> root = null;
} else {
if ($parent -> left == $current) {
$parent -> left = null;
} else {
$parent -> right = null;
}
}
} else if ($current -> left == null) {
if ($parent == null) {
$this -> root = $current -> right;
} else {
if ($parent -> left == $current) {
$parent -> left = $current -> right;
} else {
$parent -> right = $current -> right;
}
}
} else if ($current -> right == null) {
if ($parent == null) {
$this -> root = $current -> left;
} else {
if ($parent -> left == $current) {
$parent -> left = $current -> left;
} else {
$parent -> right = $current -> left;
}
}
} else {
$replacementNode = $current -> right;
while ($replacementNode -> left != null) {
$replacementNode = $replacementNode -> left;
}
$removeValue = $replacementNode -> value;
$this -> delete($replacementNode -> value);
$current -> value = $removeValue;
}
return;
} else if ($value < $current -> value) {
$parent = $current;
$current = $current -> left;
} else {
$parent = $current;
$current = $current -> right;
}
}
}결론
이제 PHP에서 이진 트리를 구현하는 방법을 배웠습니다. 이진 트리는 컴퓨터 과학의 기본 데이터 구조이며 많은 알고리즘과 응용 프로그램이 이를 포함합니다. 노드를 삽입하는 방법, 노드를 찾는 방법, 노드를 삭제하는 방법을 배웠습니다. 또한 이 클래스를 확장하여 다른 실용적인 메서드를 구현할 수도 있습니다.
위 내용은 PHP에서 이진 트리를 구현하는 방법(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
