[Data Structure] General Tree

1. General Tree란? 

 General Tree란 일반적인 Tree 구조를 말한다. Tree의 기본단위는 기본적으로 부모와 자식으로 구성되어 있다. 이러한 pattern이 여러번 반복되어있는 구조가 Tree를 이루게 된다. 아래 그림을 보고 이해 해보자. 

<General Tree 구조>

여기서 동그라미로 표현 되어 있는 부분을 Node라고 한다. Node에는 parent 와 child의 개념이 중요하다. 실제 단어의 뜻과 똑같게 해석하면 된다. Q라는 노드가 있다. Q의 자식 노드는 무엇인가? 바로 C, N , R 이다. 그렇다면 C의 부모노드는 무엇인가? 바로 Q노드이다. 

 General Tree는 자식이 몇명있던지 상관이 없다. Q처럼 자식이 3명이 있어도 된다. 또한 F처럼 자식이 2명이 있어도 된다. 이러한 점이 Binary Tree와의 차이점이다. 

그렇다면 이러한 General Tree 구조는 어디에 쓰이는가? 

 내 생각에는 데이터를 다룰 때 유용하다고 생각한다. 예를들어, 팀 조직도를 만들어야한다고 가정하자. 이때 , 마켓팅, 소프트웨어 개발팀, 회계팀이 있다. 이 세 부서는 알고리듬이라는 회사에 속한다. 즉 알고리듬이 이 세 부서의 부모다. 또한, 마케팅과 소프트웨어 개발팀, 회계팀에 속하는 사원들이 있다. 그럼 사원들은 세 부서의 자식이다. 

 이와같이 데이터간의 관련성 또는 포함관계를 나타낼 때 유용하게 쓰일 수 있다고 생각하였다. 

 

앞으로 이러한 데이터를 다룰 때 Tree를 떠올리면 되겠다는 생각이 든다. 

class TreeNode:
    def __init__(self,data):
        self.data = data
        self.children = [] 
        self.parent = None 
    
    def add_child(self,child):
        child.parent = self
        self.children.append(child)

    def get_level(self):
        level = 0
        p = self.parent 
        while p:
            level += 1 
            p = p.parent 
        return level 
    
    def print_tree(self,data_type):
        spaces = ' ' * self.get_level() * 3 
        prefix = spaces + "|__" if self.parent else ""
        string = self.data 
        name,designation = string.split(" ",1)
        if data_type == "both":
            print(prefix + self.data)
        elif data_type == "name":
            print(prefix + name)
        elif data_type == "designation":
            print(prefix + designation)
        else:
            raise KeyError("That word is not permitted.")
        if self.children:
            for child in self.children:
                child.print_tree(data_type)