알고리즘 분석 | 데이터 구조 Rooted Tree | Tree ADT | 전위, 중위, 후위 순회

이전 포스팅

알고리즘 분석 | ADT 란 | 큐 Queues | List ADT

루트 트리(Rooted Tree)

Tree 자료 구조는 많은 컴퓨터 과학 분야에서 활용되며, 이진 검색 트리나 허프만 코딩 등의 알고리즘에서 매우 중요한 역할을 합니다. 이러한 Tree 자료 구조를 다루기 위해서는, Tree ADT(Tree Abstract Data Type)를 이해하고 활용하는 것이 필수적입니다. 이번 글에서는 Tree ADT에 대해 소개하고, 일반적인 Tree 자료 구조에서 제공되는 기본적인 기능들을 정리해보겠습니다

Rooted Tree에서 각 노드는 특정한 용어로 부르는 것이 일반적입니다. 이 용어들은 다음과 같습니다 :

1. 루트 (root): 트리의 최상위 노드를 의미합니다.
2. 부모 (parent): 어떤 노드에서 그 노드의 바로 위에 있는 노드를 의미합니다.
3. 자식 (child): 어떤 노드에서 그 노드의 바로 아래에 있는 노드를 의미합니다.
4. 형제 (sibling): 같은 부모를 가지는 노드들을 의미합니다.
5. 잎 노드 (leaf node): 자식 노드가 없는 노드를 의미합니다. 즉, 서브 트리를 형성하지 않는 노드입니다.
6. 내부 노드 (internal node): 잎 노드를 제외한 모든 노드를 의미합니다. 자식 노드를 가지며, 서브 트리를 형성합니다.

이러한 용어들은 Rooted Tree를 이해하고 다루는 데 매우 중요합니다.

---

 

Tree ADT Method

 

Tree ADT query 메소드

• root(): Tree의 루트 노드를 반환합니다.
• parent(v): 주어진 노드 v의 부모 노드를 반환합니다.
• children(v): 주어진 노드 v의 자식 노드들을 반환합니다.

이외에도, Tree ADT에서 제공하는 query 메소드는 Tree의 종류에 따라 다를 수 있습니다. 일반적으로, 다음과 같은 메소드가 추가적으로 제공됩니다  :

• isInternal(v): 주어진 노드 v가 내부 노드인지 여부를 반환합니다.
• isExternal(v): 주어진 노드 v가 외부 노드(잎 노드)인지 여부를 반환합니다.
• isLeaf(node): 주어진 노드가 잎 노드인지 여부를 반환합니다.
• isRoot(node): 주어진 노드가 루트 노드인지 여부를 반환합니다.

이러한 Tree ADT의 query 메소드는 Tree 자료 구조를 분석하고, 효과적으로 활용하는 데 필수적입니다

 

Tree ADT update 메소드 

• size(): Tree 내 노드의 개수를 반환합니다.
• elements(): Tree 내 모든 노드의 값을 리스트로 반환합니다.
• positions(): Tree 내 모든 노드의 주소를 리스트로 반환합니다.
• swapElements(u,v): 두 주소 u와 v에 저장된 값을 서로 교환합니다.
• replaceElements(v, e): 특정 주소 v에 저장된 값을 e로 대체합니다.

이러한 update 메소드는 Tree 자료 구조의 내부 구조를 수정하거나, 정보를 추출하는 데에 필요합니다

---

 

트리 순회(Tree Traversal)

Tree traversal(트리 순회)는 Tree 자료구조에서 모든 노드를 한 번씩 방문하는 것을 말합니다. 즉, Tree의 모든 노드를 순회하여 데이터를 처리하는 과정입니다. Tree traversal은 대개 재귀적인 방법을 사용하며, 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 등 여러 가지 방법이 있습니다

트리 순회 코드 구현

전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)는 모두 재귀적인 방법을 사용하여 구현할 수 있습니다. 아래는 Java 코드로 각각의 순회 방법을 구현한 예시입니다.

 

preorderTraversal 전위 순회

Fig.

public void preorderTraversal(TreeNode node) {
    if (node != null) {
        System.out.print(node.val + " "); // 노드를 처리합니다.
        preorderTraversal(node.left); // 왼쪽 서브트리를 순회합니다.
        preorderTraversal(node.right); // 오른쪽 서브트리를 순회합니다.
    }
}

 

inorderTraversal 중위 순회

Fig.

public void inorderTraversal(TreeNode node) {
    if (node != null) {
        inorderTraversal(node.left); // 왼쪽 서브트리를 순회합니다.
        System.out.print(node.val + " "); // 노드를 처리합니다.
        inorderTraversal(node.right); // 오른쪽 서브트리를 순회합니다.
    }
}

 

postorderTraversal 후위 순회

Fig.

public void postorderTraversal(TreeNode node) {
    if (node != null) {
        postorderTraversal(node.left); // 왼쪽 서브트리를 순회합니다.
        postorderTraversal(node.right); // 오른쪽 서브트리를 순회합니다.
        System.out.print(node.val + " "); // 노드를 처리합니다.
    }
}

---