자료 구조 - 트리 구조 정리

Tree

Tree = Node + Edge

Tree의 특성

1. 사이클이 없다. 
   • 사이클이 있으면, 그래프
2. 모든 노드는 자료형으로 표현이 가능
3. 루트에서 한 노드로 가는 경로는 유일한 경로 
   • 유일한 경로 : 간선이 중복해서 존재하지 않는 경로. 즉, 가는 길이 하나만 존재.
4. 간선의 개수 = 노드의 개수 - 1

그래프 VS 트리
사이클이 있으면 그래프, 없으면 트리 !

트리의 순회 방식 4가지

트리의 순회 방식은 우선순위로 따라가면 쉽다.

전위 순회 pre-order

루트부터 항상 왼쪽을 먼저 순회!

🔥우선 순위 : Root ➡️ 왼쪽 자식 ➡️ 오른쪽 자식

1➡️2➡️4➡️8➡️5➡️9➡️3➡️6➡️10➡️11➡️7

중위 순회 in-order

🔥우선 순위 : 왼쪽 서브트리 ➡️ 현재 서브트리의 Root ➡️ 오른쪽 서브트리

8➡️4➡️2➡️5➡️9➡️1➡️10➡️6➡️11➡️3➡️7

후위 순회 post-order

🔥우선 순위 : 왼쪽 서브트리 ➡️ 오른쪽 서브트리 ➡️ 현재 서브트리의 Root

8➡️4➡️9➡️5➡️2➡️10➡️11➡️6➡️7➡️3➡️1

레벨 순회 level-order

🔥우선 순위 : 루트 ➡️ 계층 별 노드

1➡️2➡️3➡️4➡️5➡️6➡️7➡️8➡️9➡️10➡️11

코드

from collections import deque

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.childen = []
    
class Tree:
    def __init__(self, data) -> None:
        self.root = Node(data)
    
    def add_node(self, target_data, new_data, ) -> None:
        q = deque()
        q.append(self.root)
        while q:
            current_node = q.popleft()
            if current_node.data == target_data:
                current_node.childen.append(Node(new_data))        
                break
            
            for i in current_node.childen:
                q.append(i)
    
tree = Tree("A")
tree.add_node("A", "B")
tree.add_node("A", "C")
tree.add_node("B", "D")
tree.add_node("C", "F")

print("A의 자식 :", end=" ")
for i in tree.root.childen:
    print(i.data, end=" ")
print("\nB의 자식 :", end=" ")
for i in tree.root.childen[0].childen:
    print(i.data, end=" ")    
print("\nC의 자식 :", end=" ")
for i in tree.root.childen[1].childen:
    print(i.data, end=" ")

--- 출력 ---
A의 자식 : B C 
B의 자식 : D
C의 자식 : F

자바

package 자료구조;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Tree{
    public static void main(String[] args) {
        Tree_ t = new Tree_("A");
        t.add_node("A", "B");
        t.add_node("A", "C");
        t.add_node("B", "D");
        t.add_node("C", "F");

        System.out.print(t.root.data + " -> ");
        for(Node i : t.root.children){
            System.out.print(i.data+ " ");
        }
        System.out.println();

        Node b = t.root.children.get(0);
        Node c = t.root.children.get(1);
        
        System.out.print(b.data+ " -> ");
        for(Node i : b.children){
            System.out.print(i.data + " ");
        }
        System.out.println();

        System.out.print(c.data+ " -> ");

        for(Node i : c.children){
            System.out.print(i.data + " ");
        }
    }
}
class Tree_ {
    Node root;
    
    Tree_(String data) {
        this.root = new Node(data);
    }

    public void add_node(String targetNode, String data){
        Deque<Node> q = new LinkedList<>();
        q.addLast(this.root);
        while(!q.isEmpty()){
            Node currentNode = q.pollFirst();
            if (currentNode.data == targetNode) {
                currentNode.children.add(new Node(data));
                break;
            }
            
            for(Node i : currentNode.children){
                q.addLast(i);
            }

        }
    }
}

class Node{
    public String data;
    public ArrayList<Node> children;

    Node(String data){
        this.data = data;
        this.children = new ArrayList<>();
    }
}

--- 출력 ---
A -> B C 
B -> D
C -> F

 

참고 출처

https://gyoogle.dev/blog/computer-science/data-structure/Tree.html