Tree1

Tree and Binary Tree

Tree ?

• Example : 조직도 → 디렉토리와 서브 디렉토리 구조 or 가계도
• Tree는 Node Node를 연결하는 Link들로 구성
  • Node의 개수가 n개라면 Link의 개수는 n-1개이다.
  • x Node에서 y Node까지의 경로는 유일하다.

Binary Tree ?

• 모든 Node가 최대 2개의 자식만을 갖는다.
• 각각의 Node는 자신이 왼쪽 자식인지 오른쪽 자식인지 구분(지정) 한다.
• Example : (x + y) * ((a + b)/c) 이 수식을 Binary Tree로 표현하면?
• Full binary tree and Complete binary tree
  • 높이가 h이면 노드의 개수는 2^h-1
  • Common feature: 노드가 N개인 full 혹은 complete binary tree의 높이는 O(logN)
    –> Full or Complete binary tree는 배열로 표현이 가능
    • Tree의 코드 표현(연결리스트 사용시)

Inorder Traversal

• x + y * a + b / c (연산자 우선 순위 고려 안됨)
• 순회 시 시작에서 ‘(‘ 끝에서 ‘)’를 넣으면 된다
• ( x + y ) * ( ( a + b ) / c )
  
• Sub-tree와 관계 T_L을 inorder로 순회 -> R 순회 -> T_R을 inorder로 순회
• pseudo code)

inorderTreeWalk (x) // root 노드가 x인 sub-tree를 inorder로 순회
    if x ne null then
        inorderTreeWalk(left[x])
        print key[x]
        inorderTreeWalk(right[x])

Preorder Traversal

• x y + a b + c / * (후위표기식이 된다)
• pseudo code)

preorderTreeWalk (x) // root 노드가 x인 sub-tree를 inorder로 순회
    if x ne null then
        print key[x]
        preorderTreeWalk[left[x]]
        preorderTreeWalk[right[x]]

Post Traversal

• pseudo code)

  
postorderTreeWalk (x) // root 노드가 x인 sub-tree를 inorder로 순회
    if x ne null then
        postorderTreeWalk[left[x]]
        postorderTreeWalk[right[x]]
        print key[x]

Level Traversal

Problem

• ACMICPC:
• LEETCODE: Tree