1. 이진 트리의 표현
배열로 표현
- 루트 노드의 인덱스를 0으로 하고 왼쪽 자식은 부모 노드의 인덱스 i에 대해 2*i+1, 오른쪽 노드는 부모 노드 인덱스 i에 대해 2*i+2
- 배열 항목 사이에 빈칸이 발생하지 않는 포화 이진트리나 완전 이진 트리에 가장 적합
- 위의 두 트리가 아닌 경우 메모리 낭비가 발생할 수 있고 배열의 크기에 따라 트리의 높이가 제한 될 수 있음
연결 리스트로 표현
- 각 노드당 두 개의 링크릴 가져 오른쪽 자식 노드와 왼쪽 자식 노드를 가리키도록 함
- 필요한 만큼만 메모리를 사용할 수 있고 트리 구조를 시작적으로 표현 가능, 삭제와 삽입이 빈번한 이진 트리에 적합
- 포인터를 사용해야 하므로 구현이 까다롭고 탐색 속도는 배열로 표현하는 것보다 느릴 수 있음
2. 연결 리스트로 표현
TreeNode | 이진 트리 노드 생성 |
Preorder | 이진 트리를 전위 순회 방식으로 방문한 순서 리턴 |
Inorder | 이진 트리를 중위 순회 방식으로 방문한 순서 리턴 |
Postorder | 이진 트리를 후위 순회 방식으로 방문한 순서 리턴 |
countNodes | 이진 트리에 달려있는 모든 노드 개수를 구해서 리턴 |
calculateHeight | 이진 트리의 높이(깊이)를 구해서 리턴 |
TreeNode
class TreeNode {
public $value; // 노드에 저장될 데이터
public ?TreeNode $left = null; // 왼쪽 자식 노드 참조
public ?TreeNode $right = null; // 오른쪽 자식 노드 참조
// 생성자
public function __construct($value) {
$this->value = $value;
}
}
// 루트 노드 생성
$root = new TreeNode('A');
// 루트의 자식 노드 생성 및 연결
$root->left = new TreeNode('B');
$root->right = new TreeNode('C');
// B의 자식 노드 생성 및 연결
$root->left->left = new TreeNode('D');
$root->left->right = new TreeNode('E');
// C의 자식 노드 생성 및 연결
$root->right->left = new TreeNode('F');
$root->right->right = new TreeNode('G');
이진 트리 순회
class BinaryTree {
public ?TreeNode $root;
public function __construct(?TreeNode $root = null) {
$this->root = $root;
}
// 전위 순회 (V -> L -> R)
public function preorder(?TreeNode $node): void {
if ($node !== null) {
echo $node->value . " "; // 현재 노드 처리
$this->preorder($node->left); // 왼쪽 서브 트리 순회
$this->preorder($node->right); // 오른쪽 서브 트리 순회
}
}
// 중위 순회 (L -> V -> R)
public function inorder(?TreeNode $node): void {
if ($node !== null) {
$this->inorder($node->left); // 왼쪽 서브 트리 순회
echo $node->value . " "; // 현재 노드 처리
$this->inorder($node->right); // 오른쪽 서브 트리 순회
}
}
// 후위 순회 (L -> R -> V)
public function postorder(?TreeNode $node): void {
if ($node !== null) {
$this->postorder($node->left); // 왼쪽 서브 트리 순회
$this->postorder($node->right); // 오른쪽 서브 트리 순회
echo $node->value . " "; // 현재 노드 처리
}
}
}
// 트리 인스턴스 생성 및 순회 실행
$tree = new BinaryTree($root);
$tree->preorder($tree->root); // 출력: A B D E C F G
$tree->inorder($tree->root); // 출력: D B E A F C G
$tree->postorder($tree->root); // 출력: D E B F G C A
countNodes
public function countNodes(): int {
return $this->_countNodes($this->root);
}
private function _countNodes(?TreeNode $node): int {
if ($node === null) {
return 0;
}
// 현재 노드(1) + 왼쪽 서브트리 노드 수 + 오른쪽 서브트리 노드 수
return 1 + $this->_countNodes($node->left) + $this->_countNodes($node->right);
}
calculateHeight
public function calculateHeight(): int {
return $this->_calculateHeight($this->root);
}
private function _calculateHeight(?TreeNode $node): int {
if ($node === null) {
return -1; // 빈 트리의 높이는 -1로 정의(루트가 없는 경우)
}
// 왼쪽 서브트리의 높이
$leftHeight = $this->_calculateHeight($node->left);
// 오른쪽 서브트리의 높이
$rightHeight = $this->_calculateHeight($node->right);
// 현재 높이 = 1 + 자식 트리 중 더 높은 쪽의 높이
return 1 + max($leftHeight, $rightHeight);
}
'CS > 자료구조 & 알고리즘' 카테고리의 다른 글
[자료구조] PHP로 무방향 그래프 구현 (0) | 2025.06.06 |
---|---|
[자료구조] 그래프 Graph (0) | 2025.06.05 |
[자료구조] 트리 Tree(종류, 순회) (0) | 2025.06.04 |
[자료구조] PHP로 단순 연결 리스트 구현 (0) | 2025.04.30 |
[자료구조] 연결 리스트 Linked List (0) | 2025.04.24 |