트리(Tree)

1. 트리

1. 트리

= 계층적 관계를 표현하는 자료구조 ex) 조직도

 

2. 이진트리

= 자식 가지가 최대 2개로 나누어진다.

2. 구현 방법

1) 배열 기반 이진트리

2) 연결 리스트 기반 이진트리

 

3. 이진트리의 순회

1. 전위 순회(Preorder Traversal)

- 루트 노드 먼저 방문 = node -> Left subtree -> Right subtree

 

2. 중위 순회(Inorder Traversal)

- 루트 노드를 중간에 방문 = Left subtree -> node -> Right subtree

void inorder(TreeNode* bt){
    inorder(bt->left);
    printf("%d \n", bt->data);
    inorder(bt->right);
}

 

3. 후위 순회(Postorder Traversal) 

- 루트 노드를 마지막에 방문 = Left subtree -> Right subtree -> node