트리 이론 기본편3 -이진 트리를 표현하는 방법 + 순회 구현 -

1. 배열을 이용한 이진 트리 표현

 

루트의 번호를 1로 하고

 

레벨 n에 대하여 왼쪽부터 오른쪽으로 $2^{n}$부터 시작하여 번호를 부여

 

노드 번호를 index로 해서 배열에 노드 정보를 저장

 

완전 이진트리일때만 가능할듯

 

아니라면 빈 부분은 0으로 채우고 데이터를 넣으면 될것 같은데 조금 복잡해질것 같고

 

 

높이 h가 주어진다면.. h의 노드 최대개수는 $2^{h+1}-1$개니까 [0]*$2^{h+1}-1$으로 초기화

 

노드 개수 n개가 주어진다면 뭐 [0]*(n+1)로 초기화하면 될듯

 

라고 생각했는데.. 이게 아니야 왜 그런지는 뒤에 쓴다

 

 

1-1) 노드 번호의 특징

 

완전이진트리처럼 번호를 붙이는 방식인 1번부터 n번까지를 왼쪽부터 오른쪽으로 차례대로 붙일때만 성립함

 

 

 

1)레벨 n의 시작 노드 번호는 $2^{n}$이다

 

실제로 레벨 0는 1, 레벨1은 2 레벨2는 4 레벨 3은 8임을 알 수 있고

 

 

2)노드 번호 i의 부모 노드 번호는? \[\left \lfloor \frac{i}{2} \right \rfloor\]

 

이건 floor(i/2)라는 뜻으로 i/2보다 작거나 같은 최대의 정수를 뜻함

 

파이썬으로 표현하면 int(i/2) 혹은 i//2

 

//은 floor divide라고도 부름

 

실제로 위 그림을 보면 5번 노드의 부모 노드는 int(5/2) = 2번 노드

 

11번 노드의 부모노드는 int(11/2) = 5번 노드

 

 

3) 노드번호 i의 왼쪽 자식은 2i이고 오른쪽 자식은 2i+1

 

실제로 위 그림에서 4번 노드의 왼쪽 자식은 8번노드이고 오른쪽 자식은 9번노드

 

 

1-2) 비효율적인 공간 낭비

 

높이가 h인 이진트리라면 노드 수가 몇개인지는 모르니까 최대 노드의 수만큼 [0]*$2^{h+1}-1$로 초기화하는데

 

예를 들어 편향이진트리라면 비효율적으로 메모리공간을 낭비하게됨

 

 

 

1-3) 단점

 

위와 같이 편향이진트리의 경우 사용하지 않는 배열 원소에 대해 메모리 공간 낭비가 심할 수 있다

 

트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 때 배열의 크기를 변경하기가 쉽지 않아 비효율적이다

 

 

2. 연결리스트를 이용한 이진트리 표현

 

배열을 이용한 이진트리 표현의 단점을 극복

 

이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조를 가지는 단순 연결리스트 노드를 이용하여 구현할 수 있다

 

 

이진 트리 하나를 표현하면 이런 느낌?

 

 

3. 기타 다른 표현 방법

 

당연하지만 완전이진트리나 포화이진트리가 아니더라도 같은 방식인,

 

그러니까 1번부터 n번까지를 왼쪽부터 오른쪽으로 차례대로 번호를 붙이면 똑같이 위와 같이 배열로 저장할 수 있다

 

 

완전이진트리나 포화이진트리가 아닐때 고려해볼만한 방법들

 

물론 완전이진트리에도 당연히 가능한 방법들

 

3-1) 부모 번호를 인덱스로 하고 자식 번호를 저장함

 

자식은 왼쪽 자식과 오른쪽 자식이 있으니까 2개의 리스트 c1, c2를 이용

 

순회에 유용하다

 

 

pseudo code

 

부모,왼쪽자식, 부모,오른쪽자식, ... 순으로 입력이 주어진다면

 

예를 들어 1 2 1 3 3 4 3 5 이러면

 

2는 1의 왼쪽자식이고 3은 1의 오른쪽 자식, 이렇게 순서대로 주어진다는 것이 보장된다면..

 

(당연히 오른쪽 자식만 있을수 있지만 그런 경우가 없다고 한다면 아래 코드가 통하는거고)

 

p,c를 읽어와서

 

왼쪽 자식 c1[p] = 0이라면, 왼쪽 자식이 안채워졌으니까 왼쪽 자식 c1[p] = c를 먼저 채우고

 

왼쪽 자식 c1[p] != 0이면 왼쪽 자식은 채워졌으니까 이번에 나오는 자식은 오른쪽 자식이라서

 

c2[p] = c로 채운다

 

for i : 1 -> N   

read p,c   

if (c1[p] == 0):       

c1[p] = c   

else       

c2[p] = c

 

 

3-2) 자식 번호를 인덱스로 하고 부모 번호를 저장하는 방법

 

부모는 하나니까 부모 리스트 par 하나만 사용해도 된다

 

루트를 찾거나 조상을 찾는데 유용하다

 

루트가 항상 1이 아니거든

 

 

 

pseudo code

 

부모, 자식, 부모,자식, .. 이런식으로 입력이 주어진다면

 

순서대로 부모,자식을 읽어서

 

par[자식] = 부모 라고 넣으면 되겠지

 

for i: 1 -> N:   

read p,c   

par[c] = p

 

 

algorithm - 루트와 조상을 찾는 방법?

 

par = [0,0,1,1,3,3]일때, 5번 노드의 조상을 찾는 방법은?

 

루트 노드의 부모는 존재하지 않으니까 최초로 0이 나올때까지 거슬러 올라가면 된다

 

c = 5

 

anc = [] #조상 목록

 

while par[c] != 0:   

c = par[c]        #c=5의 부모 par[c]를 새로운 c로 저장   

anc.append(c)        #c=5의 조상이므로 리스트에 저장

root =c          #par[c] = 0이 된 순간 반복문을 탈출하고 그 c는 root가 된다

 

 

4. 구현 연습

 

4-1) 연결리스트를 이용한 이진트리 표현

 

파이썬에는 따로 연결리스트 자료구조는 없어서 class를 이용해서 이진트리를 표현할 수 있다

 

class Node:
    
    def __init__(self,data):
        
        self.data = data #노드 정보
        self.left = None #왼쪽 자식
        self.right = None #오른쪽 자식

 

self.data에는 현재 node의 노드 정보가 들어갈거고

 

self.left에는 왼쪽 자식 노드가 들어갈건데 노드를 class로 표현하니까 self.left에는 class가 들어갈거임

 

마찬가지로 self.right에는 오른쪽 자식 노드를 표현한 class가 들어갈거임

 

# node class로 tree를 생성

root = Node(1)

#root의 left, right node를 만드는 방법

root.left = Node(2) #1의 왼쪽 자식은 2
root.right = Node(3) #1의 오른쪽 자식은 3

##root.left = 2라고만 한다면 그냥 데이터 2를 넣고 
##root.left = Node(2)라고 한다면 Node(2)라는 instance를 넣는다
#그래서 Node(2)의 왼쪽, 오른쪽이 다시 Node(4), Node(5),... instance가 들어가면서 재귀적으로 생성

##4와 5를 2번 노드에 붙이기

root.left.left = Node(4)
root.left.right = Node(5)

 

root.left = 2가 아니고 root.left = Node(2)를 넣으면서,, instance가 재귀적으로 들어갈 수 있도록

 

root.left = 2하면, 더 붙일수 있는게 없는걸

 

 

4-2) 순회하기

 

위에서 만든 트리를 이용해서 전위순회, 중위순회, 후위순회를 해본다면..?

 

 

1) 전위순회

 

node가 존재한다면, 

 

1. 현재 node의 데이터를 출력하고(방문처리)

2. 현재 node의 왼쪽 자식으로 이동하고

3. 현재 node의 오른쪽 자식으로 이동하고

 

생각보다 어렵지 않고, pseudo code 그대로 쓰면 된다

 

#preorder traverse

def preorder(node):

#if node는 왜 써야하냐?

# 1 >> 2 간 다음에 4와 5를 갈건데 4와 5는 node.left = None, node.right = None
#그래서 None.data 이거 하면 에러나거든
#그래서 None이면 아무것도 실행이 안되니까
#재귀함수를 종료시키는 역할을 함
    
    if node:
        
        print(node.data, end = ' ') #방문 순서를 한줄로 출력하고 싶다면 end 옵션 사용
        
        preorder(node.left)
        
        preorder(node.right)
    
preorder(root) 
1 2 4 5 3

 

2) 중위순회(inorder)

 

node가 존재한다면,

 

현재 node의 왼쪽 자식으로 이동하고

 

현재 node를 방문 처리하고(출력하고)

 

현재 node의 오른쪽 자식으로 이동하고

 

마찬가지로 pseudo code를 그대로 쓰면 된다

 

#중위순회
def inorder(node):
    
    if node:
        
        inorder(node.left)
        print(node.data, end = ' ')
        inorder(node.right)
 
inorder(root)
4 2 5 1 3

 

3) 후위순회(postorder)

 

node가 존재한다면,

 

현재 node의 왼쪽 자식으로 이동하고

 

현재 node의 오른쪽 자식으로 이동하고

 

현재 node를 방문처리하고(출력하고)

 

역시 pseudo code 그대로 쓰면 된다

 

#후위순회

def postorder(node):
    
    if node:
        
        postorder(node.left)
        postorder(node.right)
        print(node.data, end = ' ')

postorder(root)
4 5 2 3 1

5. 연습문제

 

첫 줄에 트리의 정점의 총 수 v가 주어지고 다음 줄에 v-1개의 간선이 나열된다.

 

간선은 항상 "부모 자식" 순서로 나열된다.

 

간선은 부모 정점 번호가 작은 것부터 나열되고, 부모 정점이 동일하다면 왼쪽자식부터 번호가 작은 순서대로 나열된다.

 

다음을 전위 순회하여 순회한 순서대로 정점의 번호를 출력한다면?

 

131 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13

 

5-1) 인접리스트처럼 노드 번호마다 연결된 자식을 [왼쪽 자식, 오른쪽 자식]으로 가지는 이진 트리 표현

 

v = int(input())

tree = [[] for _ in range(v+1)]

link = list(map(int,input().split()))

#간선의 수가 v-1개이므로
#나열된 번호는 총 2(v-1)개

#0,2,4,6,...,2(v-1)-1까지 순회하고 싶음

for i in range(0,2*(v-1),2):
    
    p,s = link[i], link[i+1]
    
    tree[p].append(s)

 

이럴 경우 전위순회는 어떻게 할까

 

tree와 root node를 인자로 받고 현재 node를 출력한 다음에

 

현재 node의 자식 node가 존재한다면?

 

왼쪽 자식 node tree[node][0]를 root로 하고 재귀함수 호출

 

오른쪽 자식 node tree[node][1]를 root로 하고 재귀함수 호출

 

그런데 생각을 잘 해야돼

 

tree[node]가 [] 일수도 있고, [4]로 하나만 존재할 수도 있거든

 

이런 분기처리를 해줘야함

 

def preorder(tree,node):
    
    print(node, end=' ')
    
    if tree[node]:
        
        try:
            
            preorder(tree,tree[node][0])
        
        except:
            
            pass
        
        try:
            
            preorder(tree,tree[node][1])
        
        except:
            
            pass
            
preorder(tree,1)
1 2 4 7 12 3 5 8 9 6 10 11 13

 

try: except:를 이용해서

 

왼쪽 자식노드로 이동하는 재귀함수 preorder(tree,tree[node][0])를 호출해서

 

잘 동작하면 그대로 가지만 아니면 except: 로 pass하면 된다

 

다음 오른쪽 자식 노드로 이동하는 재귀함수 preorder(tree,tree[node][1])를 호출해서

 

잘 동작하면 계속 가지만 아니면 except:로 pass

 

try: except:가 별로라면?

 

tree[node]의 길이를 이용해서 1이라면 preorder 하나만 호출하고

 

2라면 preorder 2개를 호출하면 될것

 

def preorder(tree,node):
    
    print(node,end=' ')
    
    if tree[node]:
        
        if len(tree[node]) == 1:
            
            preorder(tree,tree[node][0])
        
        else:
            
            preorder(tree,tree[node][0])
            preorder(tree,tree[node][1])

preorder(tree,1)
1 2 4 7 12 3 5 8 9 6 10 11 13

 

 

5-2) 부모 번호를 인덱스로 저장하는 방법

 

v = int(input())

tree_left = [0]*(v+1)
tree_right = [0]*(v+1)

link = list(map(int,input().split()))

for i in range(0,2*(v-1),2):
    
    p,s = link[i],link[i+1]
    
    if tree_left[p] == 0: ###왼쪽 자식이 채워지지 않았다면
         
        tree_left[p] = s #현재 s는 왼쪽 자식
        
    else: #왼쪽 자식이 채워졌다면
        
        tree_right[p] = s #현재 s는 오른쪽 자식이다

 

이에 따라서 전위순회 알고리즘도 조금 바뀌어야 할건데

 

tree_left, tree_right, node를 모두 인자로 받고

 

현재 node를 출력한 다음에

 

만약에 왼쪽자식, 오른쪽자식이 모두 존재한다면, preorder를 왼쪽, 오른쪽 2번 호출하고

 

왼쪽자식만 존재한다면(문제에서 오른쪽자식만 존재하는 경우는 없다고 가정함)

 

preorder를 왼쪽 자식으로 한번만 호출하고

 

둘다 존재하지 않는다면 pass하면 그만

 

tree_left[node]가 0이면 왼쪽 자식이 존재하지 않는다는 뜻이지?

 

def preorder(tree_left,tree_right,node):
    
    print(node,end=' ')
    
    if tree_left[node] != 0 and tree_right[node] != 0:
        
        preorder(tree_left, tree_right, tree_left[node])
        
        preorder(tree_left, tree_right, tree_right[node])
    
    elif tree_left[node] != 0 and tree_right[node] == 0:
        
        preorder(tree_left, tree_right, tree_left[node])
    
    else:
        
        pass

preorder(tree_left,tree_right,1)
1 2 4 7 12 3 5 8 9 6 10 11 13

 

5-3) 배열을 사용하여 단순히 tree를 표현?

 

이게 노드 수가 있으니까 tree = [0] * (v+1)로 하면 되겠지 생각했는데 그게 아니야

 

 

저기 5번이 비어야하는데 tree = [0]*(v+1)하면 5번이 비질 않네??

 

그래서 tree = [0]*(2**(h+1) - 1)로 초기화하구나

 

근데 높이를 모르는데?

 

노드 수 v가 주어지면... 이게 이진 트리의 각 레벨의 시작 노드는 1,2,4,8,16,...으로 주어지기 때문에 

 

$log_{2}v$의 int()값을 구하면 그게 높이일듯

 

math.log(v,2)로 구할 수 있다

 

아니 근데 저장하기가 너무 어려운데? 이건 힘들다

 

굳이 해야되는지 모르겠어

 

부모 - 자식 순서로 주어져가지고

 

 

5-4) 자식 번호를 인덱스로 하여 부모 번호를 저장

 

그러면 이건 가능한가?

 

v = int(input())

tree = [0] * (v+1)

link = list(map(int,input().split()))

for i in range(0,2*(v-1),2):
    
    p,s = link[i],link[i+1]

    tree[s] = p

print(tree)

 

자식, 부모가 주어지니까 간단하게 tree[자식] = 부모로 하면 되니까 아주 쉬운데

 

전위순회는 어떻게 가능할까

 

def preorder(tree,node,v):
    
    print(node,end=' ')

    ##자식 node의 번호를 찾는다

    c_list = []

    for i in range(v):
        
        if tree[i] == node:
            
            c_list.append(i)
    
    #자식 수에 따른 전위순회

    if len(c_list) == 1: #자식이 하나 존재하면
        
        preorder(tree,c_list[0],v)
    
    elif len(c_list) == 2: #자식이 2개 존재하면
        
        preorder(tree,c_list[0],v)
        preorder(tree,c_list[1],v)
    
    else:  #자식이 존재하지 않으면
        
        pass

preorder(tree,1,v+1)
1 2 4 7 12 3 5 8 9 6 10 11 13

 

먼저 현재 노드를 출력하고,

 

이제 자식 노드를 찾는다

 

자식 노드는 tree를 index로 순회하여, 현재 node와 동일한 index를 모두 찾아 c_list에 집어넣는다

 

c_list의 길이가 1개이면 자식이 1개니까 왼쪽만 재귀호출하고

 

2개이면 자식이 2개니까 왼쪽, 오른쪽 재귀호출하고

 

0개이면 자식이 없어서 pass한다

 

 

5-5) class로 이진트리를 만드는 방법

 

class로 입력을 받아서 이진트리를 만들 수 있을까

 

root.left.left.left.... 입력이 몇개 들어올지 알고 이걸 다 써야할까??

 

#class 정의
class Node:
    
    def __init__(self,data):
        
        self.data = data
        self.left = None
        self.right = 

v = int(input())

#가능한 node 번호 instance를 모두 리스트에 담아둔 다음에

#0번부터 v까지 모두 넣어
#0은 필요없는것 같기는 한디
tree = [Node(i) for i in range(v+1)]

link = list(map(int,input().split()))

for i in range(0,2*(v-1),2):
    
    p,s = link[i],link[i+1]
    
    ##### 반복문을 활용해서 instance에 붙여준다
    
    if tree[p].left:      ##tree[p] === Node(p)이고 이것의 left 속성이 존재한다면..
        
        tree[p].right = tree[s] ## 오른쪽 자식이 s이므로, tree[s] == Node(s)를 불러와 붙여준다
    
    else:  ##왼쪽 자식이 존재하지 않는다면..
        
        tree[p].left = tree[s] ### 왼쪽 자식이 s이므로, tree[s] == Node(s)를 불러와 왼쪽에 붙여줌

 

클래스를 먼저 정의하고.. 핵심은 tree = [Node(i) for i in range(v+1)]로 가능한 0~v번 Node instance를 모두 리스트에 담아둔다

 

이렇게 인스턴스를 미리 만들어두는것임

 

그런 다음에.. 반복문을 호출해서 부모, 자식을 불러와

 

여기서 if tree[p].left:라고 한다면, tree[p]는 p번 Node인 Node(p)를 불러오는거고

 

Node(p)의 left 속성이 존재한다면... s는 p의 오른쪽 자식이므로

 

tree[p].right = tree[s]하면 tree에 만들어진 Node(p)의 right에는 Node(s)가 들어가있다

 

만약 else:로 tree[p].left가 존재하지 않는다면...

 

s는 p의 왼쪽자식이고 tree[p].left = tree[s] 하면 Node(p)의 left에 Node(s)가 들어가있다

 

이게 반복문을 끝내면

 

Node(1)을 root로 class를 이용한 이진트리가 만들어져있을 것임

 

tree = [Node(i) for i in range(v+1)] 이렇게 Node(i)를 만들어두지 않는다면...

 

if Node(p).left:

    Node(p).right = Node(s) 이럴건가?? 근데 이러면 Node(p)는 어디 변수에 저장이 안되어있어서

 

날라가버리는데??

 

이게 가능하다면 전위순회는 매우 간단하다

 

def preorder(node):
    
    if node:
        
        print(node.data,end=' ')
        
        preorder(node.left)
        
        preorder(node.right)

#Node(1)이 root 
preorder(tree[1])
1 2 4 7 12 3 5 8 9 6 10 11 13