트리 구현하기(C언어 구조체, 파이썬 클래스)

 

왼쪽 자식 오른쪽 형제(LCRS) 트리 구현하기

왼쪽 자식 오른쪽 형제(LCRS) 트리는 각 노드가 자신의 왼쪽 자식과 오른쪽 형제를 가리키는 포인터를 갖는 자료 구조입니다. 이 방식은 트리의 모든 노드를 연결리스트와 유사한 형식으로 저장할 수 있게 해주며, 특히 다중 자식을 가진 트리를 간단하게 표현할 수 있습니다.

노드 구조체 정의

먼저, 각 노드를 정의하는 구조체 LCRSNode를 생성합니다. 이 구조체는 자식 노드와 형제 노드를 가리키는 포인터, 그리고 데이터를 저장하는 필드를 포함합니다.

typedef char ElementType;

typedef struct tagLCRSNode {
    struct tagLCRSNode* LeftChild;
    struct tagLCRSNode* RightSibling;
    ElementType Data;
} LCRSNode;

노드 생성 및 파괴

노드를 생성하는 함수 LCRS_CreateNode는 새 데이터를 받아 새 노드를 할당하고 초기화합니다. 노드를 파괴하는 함수 LCRS_DestroyNode는 단일 노드의 메모리를 해제합니다.

LCRSNode* LCRS_CreateNode(ElementType NewData) {
    LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
    NewNode->LeftChild = NULL;
    NewNode->RightSibling = NULL;
    NewNode->Data = NewData;
    return NewNode;
}

void LCRS_DestroyNode(LCRSNode* Node) {
    free(Node);
}

자식 노드 추가

LCRS_AddChildNode 함수는 부모 노드에 새로운 자식 노드를 추가합니다. 첫 번째 자식이 없는 경우에는 바로 연결하고, 그렇지 않으면 마지막 형제 노드를 찾아 연결합니다.

void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child) {
    if (Parent->LeftChild == NULL) {
        Parent->LeftChild = Child;
    } else {
        LCRSNode* TempNode = Parent->LeftChild;
        while (TempNode->RightSibling != NULL) {
            TempNode = TempNode->RightSibling;
        }
        TempNode->RightSibling = Child;
    }
}

트리 출력

트리를 출력하는 LCRS_PrintTree 함수는 주어진 노드부터 시작하여 트리 구조를 재귀적으로 출력합니다. 각 노드는 해당 깊이만큼 들여쓰기를 하고 데이터를 출력합니다.

void LCRS_PrintTree(LCRSNode* Node, int Depth) {
    for (int i = 0; i < Depth; i++) {
        printf(" ");
    }
    printf("- %c\n", Node->Data);
    if (Node->LeftChild != NULL) {
        LCRS_PrintTree(Node->LeftChild, Depth + 1);
    }
    if (Node->RightSibling != NULL) {
        LCRS_PrintTree(Node->RightSibling, Depth);
    }
}

전체 트리 파괴

트리 전체를 파괴하는 LCRS_DestroyTree 함수는 트리의 모든 노드를 순회하며 메모리를 해제합니다.

void LCRS_DestroyTree(LCRSNode* Root) {
    if (Root->RightSibling != NULL) {
        LCRS_DestroyTree(Root->RightSibling);
    }
    if (Root->LeftChild != NULL) {
        LCRS_DestroyTree(Root->LeftChild);
    }
    LCRS_DestroyNode(Root);
}

 

 

레퍼런스

https://www.yes24.com/Product/Goods/3524901

뇌를 자극하는 알고리즘 - 예스24

파이썬 클래스로 구현하기

노드 클래스 정의

파이썬에서는 class를 사용하여 노드를 정의할 수 있습니다. 각 노드는 자신의 데이터, 왼쪽 자식 노드, 그리고 오른쪽 형제 노드를 참조합니다.

class LCRSNode:
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_sibling = None

노드 추가

특정 부모 노드에 자식 노드를 추가하는 기능을 구현합니다. 첫 번째 자식이 없다면 바로 추가하고, 이미 자식이 있다면 마지막 오른쪽 형제로 이동하여 그 뒤에 새 노드를 연결합니다.

def add_child_node(parent, child):
    if parent.left_child is None:
        parent.left_child = child
    else:
        current = parent.left_child
        while current.right_sibling:
            current = current.right_sibling
        current.right_sibling = child

트리 출력

트리를 출력하는 함수는 재귀적으로 각 노드를 방문하면서 깊이에 따라 들여쓰기를 하고 노드의 데이터를 출력합니다. 이 함수는 루트 노드부터 시작하여 왼쪽 자식을 따라 내려가면서 모든 자식들을 방문하고, 같은 부모의 다른 자식들(오른쪽 형제)로 이동합니다.

def print_tree(node, depth=0):
    print(' ' * depth + f'- {node.data}')
    if node.left_child:
        print_tree(node.left_child, depth + 1)
    if node.right_sibling:
        print_tree(node.right_sibling, depth)

전체 트리 삭제

트리의 모든 노드를 삭제하는 함수는 파이썬에서는 필요하지 않을 수도 있습니다. 파이썬의 가비지 컬렉터가 더 이상 참조되지 않는 객체들을 자동으로 관리하기 때문입니다. 그러나 명시적으로 메모리를 해제하고 싶다면, 모든 노드를 None으로 설정하여 참조를 제거할 수 있습니다.

def destroy_tree(node):
    if node.right_sibling:
        destroy_tree(node.right_sibling)
    if node.left_child:
        destroy_tree(node.left_child)
    node.data = None
    node.left_child = None
    node.right_sibling = None

사용 예

root = LCRSNode('A')
b = LCRSNode('B')
c = LCRSNode('C')
d = LCRSNode('D')

add_child_node(root, b)
add_child_node(b, c)
add_child_node(b, d)

print_tree(root)

이 코드는 루트 노드와 그 자식들을 생성하고, 트리를 출력합니다. 출력 결과는 다음과 같습니다:

- A
  - B
    - C
    - D