트리(Tree)

---

트리(tree)는 이차원의 자료구조로 노드와 엣지를 이용하여 데이터의 배치형태를 추상화한 자료구조이다.

이진트리(binary Tree)

---

모든 노드의 차수가 2 이하인 트리입니다.
*재귀적으로 정의할 수 있음

이진트리의 연산

• size: 노드의 수
• depth 트리의 깊이
• 순회(traversal)
  -깊이 우선 순회
  1)중위순회
  2)전위순회
  3)후위순회
  //순회의 순서

	1. left subtree, 2. 자기 자신 3.right subtree
#전위순회(Pre-order Traversal)
	1. 자기자신, 2. left subtree 3.right subtree
#후위순회(post-order Traversal)
	1. left subtree, 2. right subtree 3.자기 자신

-넓이 우선 순회

• 수준(level)이 낮은 노드를 우선으로 방문
• 같은 수준의 노드들 사이에는 부모노드의 방문 순서에따라, 왼쪽자식노드를 오른쪽 자식노드보다 먼저
• 한 노드를 방문했을 때 나중에 방문할 노드들을 순서대로 기록해 두어야 한다.

이진트리의 구현

Node - 데이터, LeftChild, RightChild
Tree - root,leaf
size() - 재귀적으로 각각의 서브트리사이즈 +1(자기자신)
depth() - 가장 큰 depth를 가진 서브트리 +1
inorder() - 중위순회
preorder() - 전위순회
postorder() - 후위순회
bft() - 넓이 우선 순회

다음은 파이썬으로 구현한 코드이다.

class Node:
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None

    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l+r+1

    def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return max(l,r) + 1

    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal

    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal

    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal

class BinaryTree:
    def __init__(self,r):
        self.root = r

    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0

    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0

    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []
ㅑ
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []

    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

    def bft(self):
        #리턴할 변수에 빈 리스트를 넣고, 빈큐 생성
        traversal = []
        q = ArrayQueue()
        #빈 트리가 아니면 rootnode를 큐에 추가
        if self.root:
            q.enqueue(self.root.data)
        while q:# 큐가 비어있지 않는동안
            element = q.dequeue() #node<-큐 에서 원소를 추출
            traversal.append(element.data) #node를 방문했다는 표시
             #자식 노드가 있으면 왼쪽 오른쪽자식들 큐에 추가
            if element.left:
                q.enqueue(element.left)
            if element.right:
                q.enqueue(element.right)

        return traversal

---

💡대부분의 순회는 재귀적으로 구현이 가능했지만, 넓이 우선 순회는 한 노드를 방문했을 때 자식노드도 방문해야 하지만 같은 수준의 노드들을 먼저 방문해야 하기 때문에 재귀적인 성질을 가지지 않아 재귀적으로 구현이 불가능했다.