>Liner data structure \
e.g Array, linklist, stack, queue


Select data structure factors

- Cost
- Memory usage
- Esay of implmentaion?

# Tree

Tree is hierarchical data (分層式結構)


## Tree Logic model

Collection of entities \
node link together


Number 為了辨識 非 Order

### link


### Relation


root: 1

sibiling: same hierarchical (必須同paraent)

### leaf node

Node 下面沒有 child


leaf node 4,9,19,6,11,8

### Ancestor / Descendent


因為 link 為單向

4 ancestor : 1 2
9 ancestor : 1 2 5

## Property

tree can be called recursive data structure


N node
N-1 edges

### Depth

root to x node (的路徑長)


5 : Depth = 2
9 : Depth = 3
### Height

Node to any leaf node (longest path)

3 :Hight = 2 (3 -> 7 -> 11)
1 :Hight = 3

## Binary Tree

A paraent only can have two child


C/C++ Binary tree nodes

struct node { 
    int data;
    struct node* left;
    struct node* right;
}

## Application

- Storing naturally hierarchical data
e.g. File Systems

- Organize data
for quickly search, insertion , deletion

- Network Routing algorithm