TREE (트리)

1. 부모 자식 관계의 자료구조 - tree(트리)

 

2, 트리의 구성

- node: 구성요소

- root node: 가장 맨 위에 있는 node, 부node가 없다

- link, edge : node와 node사이를 연결

- leaf node: 가장 마지막 끝에 있는 node

- height: root node 부터 leaf node 까지의 높이. 주로 h라고 한다.

- 경로(path): 출발노드 ~ 경유노드~ 도착노드 / 경로 길이

 

3, 트리의 표현법

이러한 트리가 있다고 하해보자 

• 리스트 - level0, level1 ....

A = [ a,   b,c,    None,d,e,f ]

- 각 레벨마다 꽉 차있다고 생각. 빈 노드도 왼쪽부터 비어있음을 표시

- 나는 지금 각 level별로 분류를 해보았다.

- 단점: 메모리 낭비가 심함

 

• 리스트 

[a, [a의 왼쪽 sub tree], [a의 오른쪽 sub tree]]

- 이런 방식으로 재귀

=> [a,  [b, [] , [d, [], [] ] ], [c, [e, [], [] ], [f, [], [] ] ]  ]

• 노드 class

  

  노드 class로 나타

parent, key, left, right