---
# System prepended metadata

title: Introduction
tags: [tree, data structure]

---


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

![](https://hackmd.io/_uploads/SJDy6uMK2.png)

Select data structure factors


- Cost 
- Memory usage
- Esay of implmentaion? 
 
 
 # Tree 
 
 Tree is hierarchical data (分層式結構)

![](https://hackmd.io/_uploads/Bkbv-KGF3.png)

## Tree Logic model 



Collection of entities \
node link together 


![](https://hackmd.io/_uploads/HJuizYzt3.png)

Number 為了辨識 非 Order 

### link

![](https://hackmd.io/_uploads/HkNWXYfth.png)

### Relation 


![](https://hackmd.io/_uploads/BJl8XYfYh.png)

root: 1

sibiling: same hierarchical (必須同paraent)

### leaf node 

Node 下面沒有  child 

![](https://hackmd.io/_uploads/ry5VEYfFn.png)

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

### Ancestor / Descendent 

![](https://hackmd.io/_uploads/B1FPrFzth.png)

因為 link 為單向

4 ancestor : 1 2
9 ancestor : 1 2 5 



## Property 

tree can be called recursive data structure

![](https://hackmd.io/_uploads/rynJDFMtn.png)


N node
N-1 edges 


### Depth 

root to x node (的路徑長)

![](https://hackmd.io/_uploads/BkZQFKzY2.png)

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 

![](https://hackmd.io/_uploads/S1nfsKfF3.png)

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 
