[자료구조] Tree - Binary Tree

Archive/CS & App

[자료구조] Tree - Binary Tree

Marco 2021. 5. 3. 23:53

728x90

자료구조 05 - 2 / Tree - BinaryTree

정의

트리 구조에서 2개의 서브트리만 가지는 트리의 형태, 모든 노드의 자식노드는 두개의 서브트리만 가짐

이진트리의 Leaf Node의 상태에 따라서

* (N = level)

Perfect Binary Tree (포화 이진 트리) : 모든 레벨에 노드가 채워진 트리 (총 Node 갯수 : 2ᴺ + 1 개 / Leaf의 갯수: 2ᴺ 개)

Complete Binary Tree (완전 이진 트리) : 자식노드가 왼쪽 -> 오른쪽 형태로 채워진 트리

Full Binary Tree (정 이진 트리) : 자식노드가 없거나 2개인 노드로 채워진 트리

로 구분지어 표현 할수 있다.

구현

class BinaryTreeNode<T: Equatable>: Node<T> {
    var leftChild: Node<T>?
    var rightChild: Node<T>?
    
    override init(value: T) {
        super.init(value: value)
    }
    
    override func add(child: BinaryTreeNode<T>) {
        if leftChild == nil {
            leftChild = child
            child.parent = self
        } else if rightChild == nil {
            rightChild = child
            child.parent = self
        } else {
            print("This Node has Children")
        }
    }
    
    override func search(value: T) -> BinaryTreeNode<T>? {
        if value == self.value {	// Equatable
            return self
        }
        
        if let found = leftChild?.search(value: value) as? BinaryTreeNode<T> {
            return found
        } else if let found = rightChild?.search(value: value)  as? BinaryTreeNode<T> {
            return found
        }
        
        return nil
    }
}

Node<T: Equatable> 트리 기본노드

// Array를 이용한 이진트리 구현

struct BinaryTreeArray {
    static var tree = [Int?]()
    
    static func parent(current: Int) -> Int? {
        return current > 0 ? (current - 1) / 2 : nil
    }
    static func first(current: Int) -> Int? {
        return current*2+1 > tree.count ? nil : current*2+1
    }
    static func second(current: Int) -> Int? {
        return (current+1)*2 > tree.count ? nil : (current+1)*2
    }
}

BinaryTreeArray.tree = [0, 1, 2, 3, 4, 5, 6, 7]

print(" 3's parent \(BinaryTreeArray.parent(current: 3)!)")
print(" root's right child \(BinaryTreeArray.second(current: 0)!)")

추가적으로 생각해볼 내용

노드 추가 및 제거 프로세스