차례:
트리란?
용어정리
k-nary tree
이진 트리
이진 트리의 성질
이진 트리의 방문
  -preorder
  -inorder
  -postorder
이진 트리 메모리 표현
  - 배열
  - 링크트 리스트

1. 트리 란?

트리구조란 어떤 구조인가?

(보기) 그림 A 와 그림 B 에서 '라' 의 부모 노드는?

(풀이) 그림 A 에서는 '나' 가 부모 이고 , 그림 B 에서는 '나' 와 '다' 이다. 부모가 두 개 이상 존재하는 그림 B 는 트리구조가 아니다. 즉 모든 노드는 오직 하나의 부모노드를 가져야 한다. (단, 제일 조상 노드는 제외) 그림에서 제일 조상노드는 가 노드이고 이를 루트 노드(root node) 라 한다. #

루트노드가 하나이고 부모 노드가 오직 한 개 존재 하는 구조를 트리구조라 한다.

트리가 아닌 경우의 예 두가지를 들면

• 루트 노드가 하나이고 부모 두 개 이상 존재한다는 것은 사이클이 발생하는 구조이므로 사이클이 존재하지않는 구조이다.
  
• 다른 하나의 조건은 각각은 서로 연결되어 있어야 한다. 아래 그림은 서로 연결되지 않아 트리구조가 될 수 없다. 서로 연결되어 있어야 한다는 것은 제일 조상이 유일해야 한다는 의미에 포함되는 의미이기도 하다.
  

느슨하게 트리를 정의하면

1. 제일 조상은 하나이고
2. 사이클이 존재하지 않고
3. 서로 연결된 상태

정확한 정의는 1 개 이상의 노드로 구성되어 있고

• 노드 중에 제일 조상 노드가 하나 있고
• 나머지는 n 개의 분리집합 T1,T2,..,Tn으로 분리될 수 있고 , 각 Ti 도 트리이다.(재귀적 정의)

2. 용어 정리

트리는 노드 , 브랜치로 이루어진다.

• 노드란 트리를 이루는 데이터를 이루는 구성요소('a','b',...)

  root node 란?

  node 중 아버지가 존재하지 않는 최고 조상 노드

• 브랜치(branch)란 노드와 노드를 연결하는 선

그림의 트리는 루트노드 a 이고 5 개의 노드와 4 개의 브랜치를 가지는 트리 구조이다.

한 번 정도 생각해 볼 것은 트리 구조는 루트 노드를 제외하고는 모든 노드는 부모노드를 가지므로 노드수가 n 이면 브랜치 수는 n-1 개 이다.

용어	설명
부모노드(parents node)
자식노드(child node)
형제노드(sibling node)	같은 아버지를 가진 노드
조상노드(ancestor)
자손노드(descendant)
노드의 차수(degree)	자식 수
트리의 차수	노드의 차수중 가장 높은 차수를 가지는 차수가 트리의 차수(^^)
터미널 노드(terminal node)	자식이 없는 노드
넌 터미널 노드(non-terminal node)	자식이 있는 노드
노드의 레벨(level)
트리의 depth(혹은 height)

(예)

I 노드의 아버지: G I 노드의 자식노드:L , M I 노드의 형제노드:H , J , K I 노드의 조상노드: G , C , A I 노드의 자손노드:L , M , N I 노드의 차수: 2 이 트리의 차수: 4 터미널 노드: D , E , F , H , M , J , K , N 넌터미널노드:A , B , C , G , I , L I 노드의 레벨: 4 트리의 높이(depth): 6