트리

트리: 계층적인 구조를 갖는 비순차적인 그래프, 부모와 자식간이 간선으로 연결되어 있으며
자식 노드는 서브트리의 부모노드가 될 수 있음

깊이 (depth): 부모 노드에서부터 타겟 노드까지의 간선 수
높이 (height): 부모노드에서부터 최하위 계층의 노드까지의 간선 수 +1

그림을 보면 재귀가 떠오른다 재귀를 통해서 순회가 가능

그러면 해당 그림을 참고해서
Target의 깊이와
해당 트리의 높이를 구하는 메서드를 만들어보자

• 우선 노드 구조 / 데이터는 우선 문자열을 받는걸로

class Node
{
public:
    Node(const char* data)
        : _data(data)
    {}

    void CreateTree()
    {

    }
public:
    const char* _data;
    vector<Node*> _children;
};

• 높이 구하기

int GetHeight(Node* root)
{
    int ret = 1;

    int childSize = root->_children.size();

    for (int i = 0; i < childSize; i++)
    {
        int h;
        h = GetHeight(root->_children[i]) +1;

        if (ret < h)
        {
            ret = h;
        }
    }

    return ret;
}

구조 설명 :
위의 그림을 예시로 들자면 루트 노드의 자식의 수를 구한다 -> 2 (자식A, 자식B)라고 하겠음
자식 수만큼 반복문을 돌려서 A,B의 +1 높이를 구한다
둘 중 더 큰 값을 ret변수에 덮어씌운다

• 어떠한 Target의 깊이 구하기

int GetDepth(Node* root, Node* target)
{
    int childSize = root->_children.size();

    if (target == root)
        return 0;

    for (int i = 0; i < childSize; i++)
    {
        Node* childNode = root->_children[i];

        int depth = GetDepth(childNode, target);

        if (depth != -1)
        {
            return depth + 1;
        }
    }

    return -1;
}

구조 설명:
깊이 역시 자식 수를 우선 구한다음 재귀를 돌려준다
만약 트리를 순회하다 target으로 들어온 노드를 만나면 리턴을 뱉어서 해당 노드까지 간 간선 수를 구하는 방식 밑에 그림 참고 만약 트리른 전체 순회 했는데 찾지 못한다면 -1을 반환