[알고리즘] 트리 알고리즘

트리

• 계층적 구조를 표현하는 자료 구조

이진 트리

• 각 노드가 최 두 개의 자식을 갖는 트리

완전 이진 트리

• 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리
• 마지막 레벨은, 노드가 왼쪽에서 오른쪽으로 채워져야 함
  • 오른쪽으로부터 비어 있을 수 있음
• 배열을 이용하여 표현 가능

이진 트리 표현

배열 표현
- 모든 노드의 상위, 왼쪽 하위 및 오른쪽 하위의 위치를 쉽게 결정 가능
- 모든 노드 i 에 대해 완전한 이진 트리에서
1) parent(i) = [i/2]
2) leftchild(i) = 2i
3) rightchild(i) = 2i + 1
- skewed(비뚤어진) tree인 경우, 공간 낭비
연결 리스트 표현
- 순차적 표현의 일반적인 부적절성
- skewed tree위한 낭비
- 트리 중앙에서 노드 삽입 및 삭제

이진 트리 수도코드

class TNode:
    def __init__ (self,data, left, right):
        self.data = data
        self.left = left
        self.right = right

이진 검색 트리에서의 삽입

treeInsert(t,x)
{
    if(t=NIL) then{
        key[r] <-- x;
        left[r] <-- NIL;
        right[r] <-- NIL;
        return r   (r : 새노드)
        }
    if(x<key[t])
        then{left[t] <-- treeInsert(left[t],x);
        return t; }
        else{right[t] <-- treeInsert(right[t],x);
        return t; }
}

이진 검색 트리에서 삭제

treeDelete(t,r,p)
{
    if(r=t) then root <-- deleteNode(t);
    else if(r = left[p])
        then left[p] <-- deleteNode(r);
        else right[p] <-- deleteNode(r);
}

deleteNode(r)
{
    if(left[r] = right[r] = NIL) then return NIL;
    else if (left[r] = NIL and right[r] != NIL) then return right[r];
    else if (left[r] != NIL and right[r] != NIL) then return left[r];
    else{
        s <-- right[r];
        while(left[s] != NIL)
            {parent <-- s;
            s <-- left[s];}
        key[r] <-- key[s];
        if (s = right[r]) then right[r] <-- right[s];
                          else left[parent] <-- rihgt[s];
        return r;
        }
}

이진 트리 순회

• 이진 트리의 모든 노드를 방문하는 일
• 선순위(전위)
  • root --> left --> right

    def preorder(n):
    if n is not None:
      print(n.data, end=' ')
      preorder(n.left)
      preorder(n.right)

• 중순위(중위)
  • left --> root --> right

    def inorder(n):
    if n is not None:
      inorder(n.left)
      print(n.data, end=' ')
      inorder(n.right)

• 후순위(후위)
  • left --> right --> root

    def postorder(n):
    if n is not None:
      postorder(n.left)
      postorder(n.right)
      print(n.data, end=' ')

• 레벨오더
  • node in level 1 --> nodes in level 2 --> nodes in level 3
    Queue(Q is a queue0)

    LEVEL-ORDER-TREE-TRAVERSAL()
    visit the root;
    Q <-- root;
    while Q is not empty do
      V <-- dequeue(Q)
      visit children of v;
      enqueue children of v into Q;
    end.
    end.

ppt (p.17,18)

Q1.

Is a binary tree satisfying a certain inorder traversal unique?
(이진 트리가 특정 순서로 순회를 만족하는 것이 고유한가요?)

• 트리 순회 결과 값이 같은가?

Q2.

Recover the binary tree satisfying the following conditions
(다음 조건을 충족하는 이진 트리를 복구할 것인가?)

• Preorder: 1--> 2 --> 4 --> 5 --> 3 --> 6 --> 7
• Inorder: 4 --> 2 --> 5 --> 1 --> 6 --> 3 --> 7