트리 문제

1. 이진트리 순회 구현하기

• 입력:
  첫 번째 줄에 노드의 개수를 나타내는 정수 n이 입력됩니다. (1≤n≤1000)
  두 번째 줄부터 n줄에 걸쳐 정수 a b c가 공백으로 구분되어 입력됩니다.
  정점 a가 왼쪽 자식으로 b, 오른쪽 자식으로 c를 갖는다는 의미입니다. 만약 노드의 자식 노드가 없다면 -1이 주어집니다.
  단, 첫 번째 줄에는 무조건 루트 노드가 입력되며 루트 노드가 갖는 값은 1입니다.
  이외의 각 정점들은 이미 입력된 정점들 중 하나를 부모 노드로 갖는 경우만 입력됩니다. 즉, 정점이 뒤죽박죽 입력되는 경우는 없습니다.
• preorder : 전위순회한 결과를 리스트로 반환
  inorder : 중위순회한 결과를 리스트로 반환
  postorder : 후위순회한 결과를 리스트로 반환
• 코드 :

def preorder(tree) :
    # 순회를 한 결과 방한 노드들을 순서대로 담고있는 리스트.
    # result에 값을 추가한다 = 현재 노드를 방문한다.
    result = []
    result.append(tree.index)
    # 루트노드 + 왼쪽 전위순회 + 오른쪽 전위순회
    if tree.left != None:
        result = result + preorder(tree.left)

    if tree.right != None:
        result = result + preorder(tree.right)
    return result

def inorder(tree) :
    result=[]
    if tree.left != None:
        result = result + inorder(tree.left)
    result.append(tree.index)
    if tree.right != None:
        result = result + inorder(tree.right)
    return result

def postorder(tree) :
    result=[]
    if tree.left != None:
        result = result + postorder(tree.left)
    if tree.right != None:
        result = result + postorder(tree.right)
    result.append(tree.index)
    return result

# 실행문
def main():
    myTree = Tree(None, None, None)

    n = int(input())

    for i in range(n) :
        myList = [int(v) for v in input().split()]

        if myList[1] == -1 :
            myList[1] = None

        if myList[2] == -1 :
            myList[2] = None

        myTree.addNode(myList[0], myList[1], myList[2])

    print(*preorder(myTree))
    print(*inorder(myTree))
    print(*postorder(myTree))

1-1. 이진트리 순회 구현하기

• self.index : 자기 자신의 번호(int 자료형)
  self.left : 왼쪽 서브트리의 루트 노드(Tree 자료형) 왼쪽 서브트리가 없다면 None
  self.right : 오른쪽 서브트리의 루트 노드(Tree 자료형) 오른쪽 서브트리가 없다면 None

from queue import Queue

def BFS(tree) :
    q = Queue()
    q.put(tree)
    result = []
    # q에 뭔가 들어있다면 계속 반복을 한다.
    # 즉, 더이상 방문할 노드가 없을 때 종료한다.
    while len(q.queue) > 0 : 
        cur = q.get()
        if cur == None :
            continue
        result.append(cur.index) # 방문
        q.put(cur.left)
        q.put(cur.right)
    return result

2. 이진트리 만들기

• 코드 :

# 어떤 트리의 루트 노드를 갖고있다.

class Tree:
    def __init__(self, i, l, r) :
        self.index = i
        self.left = l
        self.right = r

    # 재귀적으로 동작한다.
    # 새로운 노드가 현재 노드의 자식으로 추가되어야 하는 경우
    # -> 바로 추가
    # 그렇지 않다면 자기 자식중에 새로운 노드를 받을 수 있는 노드를 탐색한다. 
    # -> 재귀함수
    
    # 우선 바로추가부터 
    def addNode(self, i, l, r) :
        if self.index == None or self.index == i:
            self.index = i
            self.left = Tree(l, None, None) if l != None else None
            self.right = Tree(r, None, None) if r != None else None
            return True
            
        # 이부분이 재귀함수
        else: 
            flag = False

            if self.left != None :
                flag = self.left.addNode(i, l, r)
            if flag == False and self.right != None:
                flag = self.right.addNode(i,l,r)

            return flag

3. 트리높이

• 루트 노드로부터 리프노드 거리 +1이다.
• 코드 :

def getHeight(myTree) :
    # 루트노드를 포함햇, 왼쪽 서브트리와 오른쪽 서브트리를 모두 포함.
    # 왼쪽 서브트리의 높이를 구해보고,
    # 오른쪽 서브트리의 높이를 구해보고,
    # 두 높이를 비교하여 더 높은 쪽 +1(루트노드)값을 return 하면된다.
    
    if myTree == None :
        return 0
    else:
        return 1+max(getHeight(myTree.left),getHeight(myTree.right))

4. 트리의 너비

• 트리의 모든 정점들을 격자 무늬의 칸에 넣어서 정리해야 합니다.
  이 때 일정한 규칙에 따라 정리해야 하는데, 같은 레벨(깊이)의 정점은 같은 행에 위치해야 하며 한 열에는 하나의 정점만 위치해야 합니다.
  또, 한 정점의 왼쪽 서브 트리의 모든 정점들은 자신보다 왼쪽 열에, 오른쪽 서브 트리의 모든 정점들은 자신보다 오른쪽 열에 위치해야 합니다.

• 트리의 너비는 같은 레벨의 정점들 중에서 가장 오른쪽에 있는 정점의 열에서 가장 왼쪽에 있는 정점의 열을 뺀 값에 1을 더한 결과입니다.
  트리가 입력되는 형식과 규칙은 이전의 실습들과 동일하고, Tree 클래스 또한 이전 실습들과 동일합니다.
  단, 본 실습에서는 Tree.py 파일에서 클래스를 직접 수정할 수 있습니다.

• 출력 :
  myTree의 너비가 가장 넓은 레벨과 그 레벨의 너비를 반환하는 함수를 작성하세요.
  가장 넓은 레벨 l과 그 레벨의 너비 w를 튜플로 반환해야 합니다.
  반환값 형식 : (l, w)

• 코드 :

def inorder(tree, depth):
    result = []

    if tree.left != None:
        result += inorder(tree.left, depth + 1)

    tree.setDepth(depth)
    result.append(tree)

    if tree.right != None:
        result += inorder(tree.right, depth + 1)

    return result

def getWidth(myTree) :

    result = inorder(myTree,1)
    n = len(result)

    # 정점의 개수는 1000개 이하이다. (입력조건)
    # 깊이의 최댓값은 1000

    # left[i] = 깊이가 i인 모든 노드들 중에서, 가장 왼쪽에 있는 노드의 행.
    left = [1001 for i in range(1001)]
    # right[i] = 깊이가 i인 모든 노드들 중에서, 가장 오른쪽에 있는 노드의 행.
    right = [-1 for i in range(1001)]
    # 어떤 깊이의 너비는 right[i] - left[i]
    maxDepth = 0

    # result에 들어있는 중위순회의 값들을 하나씩 보겠다.
    for i in range(n):
        d = result[i].depth

        left[d] = min(left[d], i)
        right[d] = max(right[d], i)

        maxDepth = max(maxDepth, d)

    ansDepth = 0
    ans = 0

    for i in range(1, maxDepth+1):
        temp = right[i] - left[i]+1

        if ans < temp:
            ansDepth = i
            ans = temp

    return (ansDepth, ans)

class Tree:
    def __init__(self, i, l, r) :
        self.index = i
        self.left = l
        self.right = r
        self.depth = -1

    def setDepth(self, d):
        self.depth = d

    def addNode(self, i, l, r) :
        if self.index == None or self.index == i :
            self.index = i
            self.left = Tree(l, None, None) if l != None else None
            self.right = Tree(r, None, None) if r != None else None
            return True

        else :
            flag = False

            if self.left != None :
                flag = self.left.addNode(i, l, r)

            if flag == False and self.right != None :
                flag = self.right.addNode(i, l, r)

            return flag