스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4

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

저는 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: #표현방식: #왜필요해?: #효율적: #간결성: #생략

트리 : Tree

• 트리가 무엇인가요?
• 아래 그림을 보시면!

• 이게 트리입니다. 너무 대충 설명하는 것 같아요? 하지만 이게 맞습니다.
•  거꾸로 된 나무모양이라 이름이 tree 죠! 정확하게는 'level5 로 구성된 트리' 라고 합니다.
• 가장 위에 있는 루트 노드가 트리에서 Level 0 입니다.
• 아랫쪽으로 내려갈 수록 ( 트리의 '깊이' 가 깊어질 수록 ) Level 이 1 씩 증가합니다.
• 용어 ( Terminology )
• Node : 그림에서 직 사각형으로 된 것은 모두 노드입니다. 트리 자료구조는 연결리스트와 마찬가지로 여러 '노드'로 구성되죠.
• Parent, children ( 부모노드, 자식노드 ) : 아래 그림과 같습니다.
• 모든 자식노드는 하나의 부모노드만을 가지는 특성이 있습니다.

                                   

• root : 트리에서 가장 위에 있는 노드를 root( 뿌리 ) 노드라고 합니다. 그림에서 가장 위에 노드 보이시죠?
• leaf : 트리에서 자식노드가 없는 노드를 leaf ( 잎사귀 ) 노드라고 합니다. 그림에서 가장 아래 노드 보이시죠?

• 구성
• TreeNode 
• value : 노드가 가지는 값.
• children : 노드가 가지는 자식노드들. ( 다수가 될 수 있으므로 배열로 구현할 예정 ) (1 / 3)
• add(child: ) : 자식노드에 노드를 추가하는 메소드. 
• forEachDepthFirst(visit: ) : 깊이 우선 탐색하는 메소드 입니다. 
• 깊이 우선 탐색( depth-first traversal ) 이란 트리의 루트 노드를 시작으로 왼쪽, 깊이 를 우선순위에 두어 노드를 검사하는 방식입니다.
• forEachLevelOrder(visit: ) : 레벨 정렬순으로 탐색하는 메소드 입니다. 
• 레벨 정렬 탐색( Level-order traversal ) 이란 트리의 루트 노드인 Level0 를 시작으로 각 Level 별로, 왼쪽부터 우선순위 두어 노드를 검사하는 방식입니다.
• search(value: ) : 매개변수에 입력한 값이 트리에 존재하는지 검색하는 메소드.

---

• TreeNode 구현

public class TreeNode<T> {
    public var value: T // 노드가 가지고 있는 값
    public var children = Array<TreeNode>() // 자식 노드가 없을 수도 많을 수도 있으니 배열로 만들자.
    public init(_ value:T){
        self.value = value // 값으로 초기화 하기.
    }
    
    public func add(_ child: TreeNode) { // 노드에 자식노드 추가하기.
        children.append(child)  // 자식노드 배열로 구현했으므로 append 메소드 사용가능!
    }   
}
 

• TreeNode 실행

    let tree = TreeNode("Beverages") // 루트 노드이며 트리 구조를 가지고 있는 것을 tree 라는 상수에 저장한 것
    
    let hot = TreeNode("Hot")
    let cold = TreeNode("Cold")
    
    let tea = TreeNode("Tea")
    let coffee = TreeNode("Coffee")
    let cocoa = TreeNode("Cocoa")
    
    let blackTea = TreeNode("black")
    let greenTea = TreeNode("green")
    let chaiTea = TreeNode("chai")
    
    let soda = TreeNode("Soda")
    let milk = TreeNode("Milk")
    
    let gingerAle = TreeNode("ginger ale")
    let bittleLemon = TreeNode("bittle lemon")
    
    tree.add(hot)
    tree.add(cold)
    
    hot.add(tea)
    hot.add(coffee)
    hot.add(cocoa)
    
    cold.add(soda)
    cold.add(milk)
    
    tea.add(blackTea)
    tea.add(greenTea)
    tea.add(chaiTea)
    
    soda.add(gingerAle)
    soda.add(bittleLemon)

• TreeNode 출력 : 현재 아래 그림과 같이 트리가 만들어진 상태이고 이 트리가 let tree 에 할당 되어 있음.

---

• forEachDepthFirst(visit: ) 구현 

• 왼쪽, 그리고 깊이 우선 이니까 beverages -> hot -> tea -> black -> green -> chai -> coffee .. 이런 순서로 출력되야해.
• 먼저 어떤 형식의 메소드를 정의할건지 알고 넘어가자. 클로저

public func forEachDepthFirst(visit: (TreeNode) -> Void) { // 깊이 우선 탐색할 메소드
    // 이 메소드의 매개변수는 (TreeNode) -> Void 타입의 함수나 클로저가 들어오겠지? 
    // 보통 함수의 매개변수에 함수타입이 들어오면 클로저를 사용해. 그럴려고 클로저를 만든거거든^^
    // 클로저 모르면 배우고 와야해! 링크걸어둘게!
}

• 호출은 이렇게 할거야.

// 깊이우선탐색 호출을 이렇게 할거거든?
tree.forEachDepthFirst { 
    print($0.value) // 이 부분이 입력 매개변수의 클로저 부분인 거야 헷갈릴 수 있어서.
}

• 이제 진짜 구현.

 public func forEachDepthFirst(visit:(TreeNode) -> Void) {
        visit(self)
        // 입력 매개변수로 클로저가 들어올거야. 위에서 호출할 때 먼저 보여줬지?
        // 들어온 클로저의 매개변수에 self 를 넣은 뒤 실행시키는 거야.
        // 여기서 self 는 현재 이 메소드가 호출될 당시의 TreeNode(self)의 인스턴스야.
        // 호출할 때 클로저에 { print($0.value) } 이렇게 넣었었지?
        // 적용하면 클로저에서 $0 은 첫 매개변수를 뜻하므로 self 인 상수 tree 에 있는 TreeNode 인스턴스 인 것이지.
        // 그러므로 print(tree.value) 가 되겠지? 그래서 첫 번째 출력이 beverage
        
        children.forEach { 
        // 배열의 forEach 메소드 사용
        // forEach 는 배열의 각각 요소에서 클로저에 들어온 실행을 하라는 의미.
            $0.forEachDepthFirst(visit: visit) 
            // 요 부분에서 재귀호출 사용하는거야. 재귀호출 : 자기가 자기 자신을 호출하는 것.
            // beverage 자식노드 hot, cold 잖아 . 
            // hot, cold 에서 다시 forEachDepthFirst 메소드를 실행하는 거야. 계속 반복하게 되는거지.
            // 재귀 호출은 다음에 포스팅 따로 해줄게! 반복문도 재귀호출로 구현하는 거야.
        }
}

• forEachDepthFirst(visit: ) 출력

• 한 번에 이해하기 어려우면 여러가지 다른 방법으로 구현한 것들 번외로 올려둘게. 이해하는데 도움이 되길 바래
• 번외)반복문 으로 구현해볼까?

public func forEachDepthFirst_for(visit: (TreeNode) -> Void) {
        visit(self)
        
        for child in children { // 반복문으로도 구현할 수 있어.
            child.forEachDepthFirst(visit: visit)
        }
    }

• 번외) 호출할 때 클로저 너무 생략해서 이해하기 어려우면 생략 안하고 호출해 볼게

tree.forEachDepthFirst {
    a in print(a.value) // 호출도 $0 쓰지 않으면 이렇게도 할 수 있어
}

• 번외) 클로저를 전달받지 않으면 더 간단해 지네
• 요렇게 메소드 구현해 놓고

public func forEachDepthFirst() { // 매개변수 전달 안받고
        print(self.value) // 출력문을  호출 메소드 안에 넣었어.
        
        for child in children {
            child.forEachDepthFirst()
}

• 호출에 클로저 전달 안해줘도됨^^ ( 이거 번외 포스팅 할려다가 더 간단한 거 찾았네.. )

tree.forEachDepthFirst() // 개간단...

• 레벨별로 정렬, 왼쪽 우선이니까 beverage->hot->cold->tea->coffee->cocoa->soda->milk... 순으로 출력되야해.
• 호출은 똑같아~ 정의한 tree 를 LevelOrder 방식으로 검사해 보는거지~

tree.forEachLevelOrder {
        print($0.value) 
}

• 큐를 사용해서 구현할 예정이야. 혹시 큐 자료구조를 모른다면 큐 : Queue 에서 알 수 있어!
• 큐는 먼저 들어온 객체들을 먼저 나가는 FIFO( 선입 선출 ) 방식을 구현한 자료구조야. ( 영화관 티켓에 줄 설때가 좋은 예, 먼저온 사람이 먼저 들어감 )
• 큐 소스코드는 마지막에 올려줄게. 이 코드 돌려볼 사람도 있을것 같아서!

public func forEachLevelOrder(visit: (TreeNode) -> Void ){
        visit(self) // 루트 노트는 방문했어.
        var queue = Queue<TreeNode>() 
        // TreeNode 객체를 Queue 방식으로 저장할거야.
        // 제네릭으로 정의되 있는 Queue를 TreeNode 타입을 지정해서 인스턴스 생성한 거야.
        children.forEach { // 자식노드 부터 시작이야.
            queue.enqueue($0) // 큐에 자식노드 두 개 먼저 저장.
        }
        while let node = queue.dequeue() { 
            // 큐가 비어있지 않은 이상 계속 반복됨 
            // dequeue() 한 후에는 반환된 값은 큐에서 지워짐을 유의해!
            // 반환된 값이 큐에서 없어지니까 다음 큐의 dequeue() 가 let node 에 할당되서 반복이 진행되는거야.
            visit(node) // 현재 노드 방문해 주고.
            node.children.forEach { 
                // 현재 노드의 자식노드들 큐에 넣어 줘야 레벨 순서대로 나중에 visit 할 수 있어!
                queue.enqueue($0)
            }
        }
}

• forEachLevelOrder(visit: ) : 출력 

• 번외) 깊이우선에서 번외와 마찬가지로 매개변수 지울 수 있어!  이렇게 구현해놓고
  

public func forEachLevelOrder_good(){
        print(self.value) // 루트노트 출력
        var queue = Queue<TreeNode>() 
        children.forEach { 
            queue.enqueue($0) 
        }
        while let node = queue.dequeue() { 
            print(node.value) // dequeue 되는 노드의 값 
            node.children.forEach { 
                queue.enqueue($0)
            }
        }
}

• 요렇게 실행하면 끝

tree.forEachLevelOrder_good()

• search(value: ) 구현

extension TreeNode where T: Equatable { 
    // generic 타입의 범위를 where 키워드를 사용해서 제한할 수 있어.
    // 더 궁금하면 링크 걸어준 곳으로 가봐!
    public func search(_ value: T) -> TreeNode? {
        // 매개변수에는 트리에서 찾고자 하는 노드의 값입력 받고, 찾으면 해당 노드 반환해줌.
        var result: TreeNode? // 반환값으로 사용할 result
        forEachDepthFirst { node in 
            // forEachLevelOrder 을 사용해도 무방합니다. 어떤 방식으로 해도 모든 노드를 검사하기 때문에.
            if node.value == value {
                result = node
            } // 찾고자 하는 노드가 검사하는 노드의 값과 일치하는지 확인함.
        }
        return result // 찾으면 해당 노드 반환하고 못찾으면 nil 반환.
    }
}

( generic 에서 where 키워드 )  ( 내가 쓴 generic )

• search(value: ) 실행

let test = tree.search("Hot") // 트리에 Hot 있는지 검색
    print(test!.value) 

• search(value: ) 출력