스위프트: 이진 트리: #BinaryTree: #자료구조: #탐색: #in-order: #pre-order: #post-order:

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github

( 제 깃허브에 iOS, Swift 관련 정보들 정리되어 있습니다!!    )

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• Swift4: 스택: #Stack: #자료구조: #DataStructure: #쌓기
• Swift4: 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• Swift4: 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• Swift4: 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• Swift4: 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4

• Swift 주제별 분류
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략

이진 트리 : Binary Tree

• 이진 트리가 뭐야? 
• 각각의 노드가 최대 2개 까지만 자식 노드를 가질 수 있는 트리가 이진 트리야.
• 여기서 말하는 자식 노드 2개는 왼쪽 노드, 오른쪽 노드로 구별하고 LeftNode, RightNode 라고 쓰여. 

                                             

• 이진 트리가 뭔진 알겠어. 근데 이거 왜 해?
• 나도 지금 공부중이라 나중에 어떤 쓸모가 있는지는 잘 모르지만 개인적으로는..
• 근데 모든 자료구조가 인간의 삶에서 익숙한 패턴들을 컴퓨터화 시킨다는 관점에서 트리는 어떤 것을 정리하고 카테고리를 나누는, 그러니까 계층화 시킨다는 점에서 이런 현상을 컴퓨터로 더 잘 구현하려고 이걸 공부한다고 생각해.
• 이 글을 보고 있는 화면 오른쪽에 메뉴가 카테고리 별로 나눠저 있는게 트리로 구현한 거니까.

• 구성
• BinaryNode

public class BinaryNode<Element> {
    public var value: Element // 노드의 값
    public var leftChild: BinaryNode? // 왼쪽 노드 (옵셔널)
    public var rightChild: BinaryNode? // 오른쪽 노드 (옵셔널)
    public init(value: Element) {} // 초기화 함수
    public func traverseInOrder(visit: (Element) -> Void) // In-order 탐색
    public func traversePreOrder(visit: (Element) -> Void) // Pre-order 탐색
    public func traversePostOrder(visit: (Element) -> Void) // Post-order 탐색 
}

• BinaryNode  앞부분 구현

public class BinaryNode<Element> {
    
    //MARK: - 전처리 부분
    public var value: Element
    public var leftChild: BinaryNode?
    public var rightChild: BinaryNode?
    public init(value: Element) {
        self.value = value
}

• 사용자 출력도 정의해서 트리 쉽게 볼 수 있게 해보자. 이건 내가 작성한게 아니라 누군가가 여기 서 가져와서 공유한 소스를 가져온 거라는 걸 밝힐게!

extension BinaryNode: CustomStringConvertible {
    public var description: String {
        return diagram(for: self)
    }
    
    private func diagram(for node: BinaryNode?,
                         _ top: String = "",
                         _ root: String = "",
                         _ bottom: String = "") -> String {
        guard let node = node else {
            return root + "nil\n"
        }
        if node.leftChild == nil && node.rightChild == nil {
            return root + "\(node.value)\n"
        }
        return diagram(for: node.rightChild, top + " ", top + "┌──", top + "│ ")
            + root + "\(node.value)\n"
            + diagram(for: node.leftChild, bottom + "│ ", bottom + "└──", bottom + " ")
    }
}

• 트리 만들어서 실행해 보자

var tree: BinaryNode<Int> {
    
    let zero = BinaryNode(value: 0)
    let one = BinaryNode(value: 1)
    let five = BinaryNode(value: 5)
    let seven = BinaryNode(value: 7)
    let eight = BinaryNode(value: 8)
    let nine = BinaryNode(value: 9)
    
    seven.leftChild = one
    one.leftChild = zero
    one.rightChild = five
    seven.rightChild = nine
    nine.leftChild = eight
    
    return seven // 루트노드 반환
}
print(tree)

• 출력하면 이래!

---

• traverseInOrder(visit: ) 구현 : in-order 탐색
• 왼쪽 자식 노드부터 재귀호출을 시작하고 오른쪽 노드의 재귀 호출을 마지막에 하는 방식입니다. 아래 그림 참조.
• 왼쪽 자식 노드 부터 재귀를 시작하므로 왼쪽 가장 아래까지 가서 출력하고 이전에 호출됬던 1을 출력하고 5를 출력하죠? 
• 그 이전에 호출됬던 7을 출력하고 오른쪽 노드로 넘어갑니다.

public func traverseInOrder(visit: (Element) -> Void) {
        leftChild?.traverseInOrder(visit: visit) 
        // 왼쪽 노드 먼저 재귀 호출 시작.
        // 매개변수에 상위 visit 쓴 것은 같은 클로저를 쓰겠다. 즉 print($0) 하겠다는 말.
        // 그림에서 보세용.
        visit(value) 
        // 클로저로 들어온 visit 에 value 를 매개변수로 넣어서 실행.
        // 그러니까 print($0) 의 $0 는 현재 인스턴스의 value 가 되겠쥬? 이건 7 이겠네.
        // 가운대에 노드 출력하는 연산 있으므로 in-order
        rightChild?.traverseInOrder(visit: visit)
        // 마지막 순서로 오른쪽
    }

• traverseInOrder(visit: ) 실행과 출력

tree.traverseInOrder {
    print($0)
}

---

• traversePreOrder(visit: ) , traversePostOrder(visit: ) 구현 : Pre-order, Post-order 탐색

• inorder 를 잘 이해하셨다면 pre-order 와 post-order 는 출력하는 실행의 순서만 바꾼 것입니다. ( 여기선 visit(value)네요. ) 
• pre-order 는 먼저 출력하고 왼쪽 자식 노드로 넘어갑니다. 아래 그림과 같습니다. p 는 출력의 순서를 표시한 것입니다.
• post-oder 는 출력을 가장 늦게 하고 왼쪽 재귀가 가장 먼저 호출되므로 가장 아랫쪽의 왼쪽 노드부터 출력하기 시작합니다. 그림과 같습니다.

pre-order	post-order
tree.traversePreOrder { print($0) }	tree.traversePostOrder{ print($0) }