[자료구조] PHP로 이진 트리 구현

2025. 6. 5. 13:48·CS/자료구조 & 알고리즘

 


 

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
'CS/자료구조 & 알고리즘' 카테고리의 다른 글
  • [자료구조] PHP로 무방향 그래프 구현
  • [자료구조] 그래프 Graph
  • [자료구조] 트리 Tree(종류, 순회)
  • [자료구조] PHP로 단순 연결 리스트 구현
초오오이
초오오이
  • 초오오이
    초이
    초오오이
  • 전체
    오늘
    어제
    • 분류 전체보기 (101)
      • PHP (4)
      • Laravel (7)
      • Vue.js (5)
      • CS (73)
        • WEB (1)
        • 컴퓨터 구조 (12)
        • 운영체제 (24)
        • 네트워크 (24)
        • 자료구조 & 알고리즘 (12)
      • etc (6)
        • 자격증 (3)
  • 인기 글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
초오오이
[자료구조] PHP로 이진 트리 구현
상단으로

티스토리툴바