LCRS Tree [c++]

---

LCRS Tree 개념

왼쪽 자식과 오른쪽 형제에 대한 포인터만을 갖도록 노드를 구성한다.
LCRS Tree에서 어느 한 노드의 모든 자식 노드를 얻으려면 왼쪽 자식 노드에 대한 포인터만 있으면 된다.
해당 포인터를 이용해서 왼쪽 자식 노드의 주소를 얻을 후, 이 자식 노드의 오른쪽 형제 노드의 주소를 얻고 그 다음 오른쪽 형제 노드의 주소를 계속 얻으면 결국 모든 자식 노드를 얻을 수 있다.

트리 노드는 data가 담겨 있는 필드, 왼쪽 자식을 가리키는 포인터, 오른쪽 형제 노드를 가리키는 포인터로 구성되어 있다.

---

c++로 구현한 LCRS Tree

#include <iostream>
#include <string>
using namespace std;
template <typename T>
struct Node {
    T data;
    struct Node* leftChild;
    struct Node* rightSibling;
};

template <typename T>
class LCRSTree {
public:
    LCRSTree();
    ~LCRSTree();

    Node<T>* LCRS_CreateNode(T newData);
    void LCRS_DestroyNode(Node<T>* node);
    void LCRS_DestroyTree(Node<T>* root);

    void LCRS_AddChildNode(Node<T>* parentNode, Node<T>* newNode);
    void LCRS_AddSiblingNode(Node<T>* siblingNode, Node<T>* newNode);

    void LCRS_PrintTree(Node<T>* root, int depth);

};
template <typename T>
LCRSTree<T>::LCRSTree() {}

template <typename T>
LCRSTree<T>::~LCRSTree() {}

template <typename T>
Node<T>* LCRSTree<T>::LCRS_CreateNode(T newData) {
    Node<T>* newNode = new Node<T>;

    newNode->leftChild = nullptr;
    newNode->rightSibling = nullptr;
    newNode->data = newData;

    return newNode;
}

template <typename T>
void LCRSTree<T>::LCRS_DestroyNode(Node<T>* node) {
    node->leftChild = nullptr;
    node->rightSibling = nullptr;

    delete node;
}

template <typename T>
void LCRSTree<T>::LCRS_DestroyTree(Node<T>* root) {
    if (root == nullptr) {
        return;
    }

    LCRS_DestroyTree(root->leftChild);
    LCRS_DestroyTree(root->rightSibling);

    LCRS_DestroyNode(root);
}

template <typename T>
void LCRSTree<T>::LCRS_AddChildNode(Node<T>* parentNode, Node<T>* newNode) {
    Node<T>* current = parentNode;

    while (current->leftChild != nullptr) {
        current = current->leftChild;
    }

    current->leftChild = newNode;
}

template <typename T>
void LCRSTree<T>::LCRS_AddSiblingNode(Node<T>* siblingNode, Node<T>* newNode) {
    Node<T>* current = siblingNode;

    while (current->rightSibling != nullptr) {
        current = current->rightSibling;
    }

    current->rightSibling = newNode;
}

template <typename T>
void LCRSTree<T>::LCRS_PrintTree(Node<T>* root, int depth) {
    if (root == nullptr) {
        return;
    }
    for (int i = 0; i < depth; i++) {
        cout << "   ";
    }
    cout << "+--" << root->data << endl;

    LCRS_PrintTree(root->rightSibling, depth+1);
    LCRS_PrintTree(root->leftChild, 0);
}

int main() {
    LCRSTree<string>* lcrsTree = new LCRSTree<string>;

    Node<string>* A = lcrsTree->LCRS_CreateNode("A");
    Node<string>* B = lcrsTree->LCRS_CreateNode("B");
    Node<string>* C = lcrsTree->LCRS_CreateNode("C");
    Node<string>* D = lcrsTree->LCRS_CreateNode("D");
    Node<string>* E = lcrsTree->LCRS_CreateNode("E");
    Node<string>* F = lcrsTree->LCRS_CreateNode("F");
    Node<string>* G = lcrsTree->LCRS_CreateNode("G");

    lcrsTree->LCRS_AddSiblingNode(A, B);
    lcrsTree->LCRS_AddSiblingNode(A, C);
    lcrsTree->LCRS_AddChildNode(A, D);
    lcrsTree->LCRS_AddSiblingNode(D, E);
    lcrsTree->LCRS_AddChildNode(E, F);
    lcrsTree->LCRS_AddSiblingNode(F, G);

    lcrsTree->LCRS_PrintTree(A, 0);

    return 0;

}

출력 결과

+--A 
   +--B
      +--C
+--D
   +--E
+--F
   +--G