[자료구조] 트리 1 (트리 종류, 이진 트리 순회, 복사, 동일성 검사)

트리

하나 이상의 노드로 이루어진 유한 집합

- 하나의 루트 노드

- 나머지 노드들은 n(≥0) 개의 분리 집합 \(T_{1}, T_{2},..., T_{n}\)으로 분할

- \(T_{i}\): 루트의 서브트리

 

노드	한 정보 아이템 + 다른 노드로 뻗어진 가지
노드의 차수(degree)	노드의 서브트리 수
단말(리프) 노드	차수 = 0
비단말 노드	차수 ≠ 0
자식	노드 X의 서브트리의 루트
형제	부모가 같은 자식들
트리의 차수	노드의 차수의 최댓값
조상	루트까지의 경로상에 있는 모든 노드
레벨	루트 == 레벨1, 자식 레벨 == 부모 레벨 + 1
높이(깊이)	노드 레벨의 최댓값

트리의 리스트 표현

(A(B(E(K,L),F),C(G),D(H(M),I,J)))

- 차수가 k인 트리에 대한 노드 구조

 

트리 예시

노드 구조

 

이진트리

공백이거나 루스와 두 개의 분리된 이진트리로 구성된 노드의 유한 집합

• 한 노드는 최대 두 개의 가지
• 왼쪽 서브트리와 오른쪽 서브트리 구별
• 0개의 노드를 가질 수 있음

template <class T>
class BinaryTree
{ // 빈 이진트리이거나 루트 노드, 왼쪽 이진트리, 오른쪽 이진트리로 구성된 유한한 노드 집합
public:
    BinaryTree();
    // 빈 이진트리를 생성

    bool IsEmpty();
    // 이진트리가 비어있는지 여부를 반환

    BinaryTree(BinaryTree<T> &bt1, T &item, BinaryTree<T> &bt2);
    // bt1을 왼쪽 서브트리, bt2를 오른쪽 서브트리, item을 루트 노드의 데이터로 하는 이진트리를 생성

    BinaryTree<T> LeftSubtree();
    // *this의 왼쪽 서브트리를 반환

    BinaryTree<T> RightSubtree();
    // *this의 오른쪽 서브트리를 반환

    T RootData();
    // *this의 루트 노드 데이터를 반환
};

 

이진트리와 일반 트리의 차이점

- 이진트리는 공백 이진 트리 가능

- 이진 트리는 자식의 순서 구별

서로 다른 두 이진 트리

 

이진트리의 성질

최대 노드 수

• 레벨 i에서 최대 노드 수: \(2^{i-1}(i ≥ 1)\)
• 깊이가 k인 이진트리가 가질 수 있는 최대 노드 수: \(2^{k}-1(k ≥ 1)\)

리프 노드 수와 차수가 2인 노드 수와의 관계

• \(n_{0} = n_{2} + 1\)(\(n_{0}\): 리프 노드 수, \(n_{2}\): 차수가 2인 노드 수)
  • \(n_{1}\): 차수가 1인 노드 수, n: 총 노드 수, B: 총 가지 수
  • \(n = n_{0} + n_{1} + n_{2}\)
  • 루트를 제외한 모든 노드들은 들어오는 가지가 하나씩 있으므로
    \(n = B + 1\)
  • 모든 가지들은 차수가 2 또는 1인 노드에서 뻗어 나오므로
    \(B = n_{1} + 2n_{2}\)

총 정리
\(n = B + 1 = n_{1} + 2n_{2} +1\)
\(n_{0} = n_{2} + 1\)

 

포화 이진트리

포화 이진 트리

• 깊이 - k
• 노드 수 - \(2^{k}-1\)
• 노드 번호 1 ~ \(2^{k}-1\) 까지 순차적 부여 가능

 

완전 이진트리

완전 이진 트리

• 깊이 - k
• 노드 수 - n
• 1~n까지 포화 이진트리와 노드 번호가 같은
• \([log_{2}(n+1)]+1\)

 

편향 이진트리

 

이진트리의 표현

배열 표현

• 1차원 배열에 노드를 저장
• n개의 노드를 가진 완전 이진트리가 순차적으로 표현되고 인덱스가 1 ≤ i ≤ n일 때
  • parent(i): [i/2]
  • leftChild(i): 2i
  • rightChild(i): 2i+1

- 완전 이진트리: 낭비되는 공간 없음

- 편향 이진트리: 공간 낭비 - 최악의 경우 깊이 k 편향 트리는 \(2^{k}-1\) 중 k개만 사용

 

연결 표현

노드 - [left child | data | right clild]

template <class T>
class Tree; // 전방 선언

template <class T>
class TreeNode
{
    friend class Tree<T>;

private:
    T data;
    TreeNode<T> *leftChild;
    TreeNode<T> *rightChild;
};

template <class T>
class Tree
{
public:
    // 트리 연산 함수들
    //
    //
private:
    TreeNode<T> *root;
};

 

예시

편향 이진 트리

포화 이진 트리

 

이진 트리 순회와 트리 반복자

트리 순회

• 트리에 있는 모든 노드를 한 번씩만 방문
• 순회 방법: LVR, LRV, VLR, VRL, RVL, RLV
  • L - 왼쪽 이동, V - 노드 방문, R - 오른쪽 이동

 

• V의 위치에 따라 
  • 전위(preorder) 순회
  • 중위(inorder) 순회
  • 후위(postorder) 순회

 

전위 순회

template <class T>
void Tree<T>::Preorder()
{ // 인자 미입력시 루트부터 순회
    Preorder(root);
}

template <class T>
void Tree<T>::Preorder(TreeNode<T> *currentNode)
{ // 현재 노드와 서브트리의 노드들을 순회
    if (currentNode)
    {
        Visit(currentNode);
        Preorder(currentNode->leftChild);
        Preorder(currentNode->rightChild);
    }
}

 

중위 순회

template <class T>
void Tree<T>::Inorder()
{
    Inorder(root);
}

template <class T>
void Tree<T>::Inorder(TreeNode<T> *currentNode)
{
    if (currentNode)
    {
        Inorder(currentNode->leftChild);
        Visit(currentNode);
        Inorder(currentNode->rightChild);
    }
}

 

후위 순회

template <class T>
void Tree<T>::Postorder()
{
    Postorder(root);
}

template <class T>
void Tree<T>::Postorder(TreeNode<T> *currentNode)
{
    if (currentNode)
    {
        Postorder(currentNode->leftChild);
        Postorder(currentNode->rightChild);
        Visit(currentNode);
    }
}

 

레벨 순서 순회

큐 사용

루트 방문 -> 왼쪽 자식 방문 -> 오른쪽 자식 방문

template <class T>
void Tree<T>::LevelOrder()
{ // 이진 트리의 레벨 순서 순회
    Queue<TreeNode<T> *> q;
    TreeNode<T> *currentNode = root;
    while (currentNode)
    {
        Visit(currentNode);
        if (currentNode->leftChild)
            q.Push(currentNode->leftChild);
        if (currentNode->rightChild)
            q.Push(currentNode->rightChild);
        if (q.IsEmpty())
            return;
        currentNode = q.Front();
        q.Pop();
    }
}

 

 

이진 트리의 복사

template <class T>
Tree<T>::Tree(const Tree<T> &s)
{ // Copy constructor
    root = Copy(s.root);
}

template <class T>
TreeNode<T> *Tree<T>::Copy(TreeNode<T> *origNode) 
{ // 해당 노드에서의 트리를 복사해서 포인터를 리턴
    if (!origNode)
        return 0;
    return new TreeNode<T>(origNode->data,
                           Copy(origNode->leftChild),
                           Copy(origNode->rightChild));
}

 

 

이진 트리 동일성 검사

template <class T>
bool Tree<T>::operator==(const Tree &t) const
{
    return Equal(root, t.root);
}

template <class T>
bool Tree<T>::Equal(TreeNode<T> ~*a, TreeNode<T> ~*b)
{
    if ((!a) && (!b))
        return true;                                 // a, b 모두 0일때
    return (a && b                                   // a, b 모두 0이 아닐 때
            && (a->data == b->data)                  // 데이터가 같은 경우
            && Equal(a->leftChild, b->leftChild)     // 왼쪽 서브 트리가 같은 경우
            && Equal(a->rightChild, b->rightChild)); // 오른쪽 서브 트리가 같은 경우
}