트리(Tree) 자료구조와 순회

컴퓨터 과학에서 트리란, 계층 구조의 추상적 모델이다.

부모 / 자식의 노드로 구성되어 있으며 조직도, 파일시스템, 프로그래밍 환경 등에서 응용된다.

 

트리 용어

Root : 부모가 존재하지 않는 최상위노드

Internal node(내부 노드) : 최소 한개의 자식을 갖는 노드

External node(외부 노드) : 자식이 없는 노드

Ancestors of a node(조상 노드) : parent,grandparent,great-grandparent etc..

Depth(깊이) : 조상의 개수의 수. 즉 , 노드에 도착하기 위해 거쳐야 하는 간선의 수.

Height(높이) : 가장 깊이 있는 노드의 깊이

Subtree(서브 트리) : 트리 내에서 노드와 자손들로 구성된 다른 트리

 

Tree ADT

Generic methods : int size() , boolean empty()

Accessor methods : position root() , list<position> positions()

Position-based methods : position parent() , list<position> children()

Query methods : boolean isRoot() , boolean isExternal()

 

전위 순회(Preorder Traversal)

- 트리 자료구조에서 노드가 자손을 방문하기 전에 먼저 방문하는 순회이다.

Algorithm preOrder(v){
	visit(v)
    for each child w of v
    	preOrder(w)
}

 

후위 순회(Postorder Traversal)

- 트리 자료구조에서 노드의 자손을 먼저 방문하는 순회이다.

Algorithm postOrder(v){
	for each child w of v
    	postOrder(w)
    visit(v)
}

 

중위 순회(Inorder Traversal)

- 중위 순회는 우측 서브트리를 방문하기 전에, 왼쪽 서브트리를 먼저 방문하는 순회이다.

Algorithm inOrder(v){
	ifㄱv.isExternal()
    	inOrder(v.left())
    visit(v)
    ifㄱv.isExternal()
    	inOrder(v.right())
}

 

이진 트리(Binary Tree)

- 이진 트리는 각 내부노드가 최대 2개의 자손을 가지고(적절한 이진트리는 정확히 2개만 가짐) 노드의 자식들이 정렬된 쌍으로 존재하는 트리 구조이다.

- 내부 노드의 자식들을 left child와 right child로 구분하여 부른다.

- 이진 트리는 수학적 표현과 관련이 있다. 내부 노드는 operators(연산자) , 외부 노드는 operands(숫자)를 표현한다.

 

Binary Tree ADT

- 이진 트리의 ADT는 트리 ADT를 상속받지만 추가적으로 position p.left() 와 position p.right()를 가진다.