Types of trees
기본적으로 tree는 binary tree를 의미한다.
A full tree is a tree in which every node has either 0 or 2 children.
13
/ \
7 8
/ \
2 4
/ \
1 9
A complete tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
13
/ \
7 8
/ \ /
2 4 9
A perfect tree is a binary tree in which all interior nodes have two children and all leaves have the same level.
13
/ \
7 8
/ \ / \
2 4 3 5
traversal
Pre order traversal (DFS)
- visit root node
- visit left child
- visit right child
In order traversal (DFS)
- visit left child
- visit root
- visit right child
Post order traversal (DFS)
- visit left child
- visit root
- visit right child
BFS
- level 순서대로 방문한다
- tree를 다룰 때는 잘 사용하지 않는다
DFS는 재귀로 구현하기 때문에 실제로는 그렇게 복잡하지 않다.
Methods for storing binary trees
Arrays
Breadth-first order로 저장한다.
특히 complete tree를 구현할 때 배열을 사용하면 공간의 낭비가 없다.
Nodes and references
Tree 클래스와 Node 클래스를 만들어서 구현한다.
'CS > 자료구조' 카테고리의 다른 글
| Binary Search Tree (BST) (0) | 2022.04.18 |
|---|---|
| Max Heap (0) | 2022.04.18 |
| Hash (2) (0) | 2022.04.14 |
| Hash (1) (0) | 2022.04.13 |
| Linked List (0) | 2022.04.13 |