[자료구조,Python] 파이썬으로 만들어보는 트리 Tree

Tree

우리는 왜 Tree 를 사용하는가?
List 혹은 Stack, Queue 형태의 자료구조에서 특정한 값을 찾기 위해서는 Full Scan(값들을 처음부터 하나하나 비교 하는)는 수밖에 없었다. 하지만 Tree구조를 활용하면 굳이 Full scan을 하지 않아도 된다. 즉 list 형태의 자료구조보다 훨씬 효율적으로 데이터값들을 추출할 수 있다.

Tree구조 용어

1. Root
   • 최상위에 있는 데이터 (위 그림의 A)
2. Leaf
   • Child가 없는 노드 (위 그림의 K , L , F , M , N , I , O , P)
3. Terminal / External
   • Leaf노드 이면서 , Max Depth 인 경우 (위 그림의 K , L , M , N , O , P)
4. Non-terminal/Internal
   • Leaf노드이면서 Max Depth 가 아닌 경우 (위 그림의 F , I )
5. Child(ren)
   • 특정 노드와 아래방향으로 직속으로 연결되어있는 노드 (위 그림의 경우 B 의 Child 는 E , F , G)
6. Degree
   • child 노드의 수 (위 그림의 경우 C의 Degree 는 2)
7. Parent (cardinality = 1)
   • 특정 노드와 위 방향으로 직속으로 연결되어있는 노드 (위 그림의 경우 E의 parent는 B)
   • Tree 에서 Parent는 언제나 1개의 노드여야함
8. Sibiling(s)
   • 특정 노드와 같은 Depth / Level 에 있는 노드 (위 그림의 경우 B 의 sibling은 C , D)
9. Ancestor(s)
   • 특정 노드의 Root 노드부터 Parenet노드까지 직속으로 연결된 노드 (위 그림의 경우 K의 Ancestor 노드는 E, B, A)
10. Desencdant(s)
    • 특정 노드와 아래방향으로 연결되어있는 모든 노드 (위 그림의 경우 C의 Desendant(s)는 H, I , N)
11. Subtree
    • parent 노드가 Root 노드인 트리 (위 그림의 경우 Subtree 는 총 3개 B 의 아래방향 으로 뻗어진 트리 , C의 아래방향으로 뻗어진 트리 , D의 아래방향으로 뻗어진 트리)
12. Level/Depth
    • Root를 1로 출발해서 자신에게 도달하는데 걸리는 거리 ( 위 그림에서 Level/Depth2 = B , C , D Level/Depth3 = E, F, G, H , I , J)
13. Height
    • Depth/Level 의 최댓값 ( 위 그림에서 Height = 4)

Node 클래스

Class Node:
    def __init__(self,data):
        self.data = data
        self.children = []
    
    def get_data(self):
        return self.data
        
    def add_child(self,child):
        self.children.append(child)
        
    def get_children(self):
        return self.children

코드 설명

Node의값을 리스트에 담기 위해 init 함수를 통하여 리스트 객체를 만들고 Tree에서 추가할 파라미터를 참조할 data 객체를 만든다.

get_data 메소드에서는 추가된 데이터값을 확인할 수 있게 self.data를 리턴해준다.

get_children 메소드에서는 child 노드를 확인할 수 있게 children 리스트를 리턴해준다.

add_child 메소드에서는 children 값을 추가하기위해 추가에 필요한 child 노드의 데이터를 파라미터로 취하며, child파라미터를 children 리스트에 append 함수를 통하여 추가해준다.

Tree 클래스

Class Tree:

    def __init__(self):
        self.root = None
        
    def get_root(self):
        return self.root
        
    def set_root(self, root):
        self.root = root

코드 설명

init 함수를 통하여 Tree에 Root 노드를 설정하기 위해 Root 객체를 생성한다.

get_root 메소드를 통해서 현재 root 값을 확인할 수 있다.

set_root 메소드는 Root노드를 세팅할 root 를 파라미터로 취하며 Root 노드를 root로 세팅할 수 있게 한다.

노드 생성

우리는 Class Node 와 Clas Tree 를 정의함으로 두 클래스를 활용하여 노드를 만들고 트리를 구현할 수 있게 만들었다. 자 이제 두가지 클래스를 활용해서 노드들을 만들고 그 노드의 Root 노드를 위 그림처럼 설정해보자.

tree = Tree()

node_a = Node("A")
node_b = Node("B")
node_c = Node("C")
node_d = Node("D")
node_e = Node("E")
node_f = Node("F")
node_g = Node("G")
node_h = Node("H")
node_i = Node("I")
node_j = Node("J")
node_k = Node("K")
node_l = Node("L")
node_m = Node("M")
node_n = Node("N")
node_o = Node("O")
node_p = Node("P")

tree.set_root(node_a)

코드 설명

Node class 의 __init__함수에 Data를 전달함으로 A ~ P 까지의 데이터를 취하는 노드를 생성한 후 , Tree클래스의 set_root 메소드를 활용하여 root node를 node_a가 참조하는 “A” 노드로 설정했다.

노드 연결

위의 코드를 통해서 노드를 생성하고 Root 노드를 설정하였다면, 이제 여러 데이터 노드를 트리 형태로 추가해줄 필요가 있다.

node_a.add_child(node_b)
node_a.add_child(node_c)
node_a.add_child(node_d)


node_b.add_child(node_e)
node_b.add_child(node_f)
node_b.add_child(node_g)


node_c.add_child(node_h)
node_c.add_child(node_i)

node_h.add_child(node_n)

node_e.add_child(node_k)
node_e.add_child(node_l)

node_g.add_child(node_m)

node_j.add_child(node_o)
node_j.add_child(node_p)

우리는 node class의 add_child 함수에 생성된 노드데이터를 파라미터값으로 취함으로써 각각의 노드들을 연결시켰다. 우리는 위 노드들이 잘 연결되어있는지 확인해볼 필요가 있다. 이를 확인하기위해서 print method를 구현해보자.

print 메소드

def print_node(self, node, depth):
  msg = ""
  if node is not None:
    for i in range(0, depth):
      msg += "  "
    msg += node.get_data()
    print(msg)
    
    children = node.get_child()
    for i in range(0,len(children)):
        self.print_node(children[i], depth + 1)

우리는 재귀함수를 통하여 print 메소드를 구현해보았다. 그 결과값을 확인해보자.

A
B
  E
    K
    L
  F
  G
    M
C
  H
    N
  I
D
  J
    O
    P

위와같이 띄어쓰기로 Depth를 구분하여 노드들이 출력됬다면 성공이다.