Data Structure - Tree (2)

Binary Trees

한 노드당 최대 2개의 자식 노드를 가진 Tree

   - 한 노드 당 2개의 자식 노드를 가진 것을 특정해서 Poper Binary Tree라고 부름

 

각 노드를 Left Child와 Right Child라고 부름

 

활용 : 검색, 의사결정 과정, arithmetic expressions

 

Proper Binary Tree의 특징

Notation:

 

n - 노드의 수

e - external 노드의 수

i - internal 노드의 수

h - 높이

 

특징:

 

e = i + 1

n = i + e = 2i +1 = 2e - 1

h <= i 

e <= 2^h

h >= log(2)e

 

Binary Tree ADT

Binary Tee ADT는 Tree ADT의 확장판 격이기 때문에, 기존 Tree ADT의 메소드를 동일하게 가지고 있음.

따라서 기존 ADT Tree의 메소드는 제외하고 설명함

 

p.left() : p의 left child return (p가 external인 경우 에러)

p.right() : p의 right child return (p가 external인 경우 에러)

 

Binary Tree의 연결 구조

Binary Tree의 각 노드는 요소, 부모노드  지시, Left child node 지시, right child node 지시 부분으로 구성된다.

Binary Tree로 산술 표현하기

Binary Tree는 연산을 표현할 수 있는데, 이때 internal nodes는 연산자, external nodes는 피연산자 element를 갖는다.

 

2(a-1)+3b를 binary Tree로 표현

이제, 컴퓨터가 어떻게 복잡한 산술 표현을 이해하는 지 알아보자, 지난번에 알아본 바에 의하면 컴퓨터는 Tree를 3가지 방식으로 읽을 수 있었다.

 

Inorder traversal,

preorder traversal,

postorder traversal.

 

이 세가지는 tree에서 각각 infix, prefix, postfix 방식으로 읽는다. 그렇다면 이 방법들을 사용해서 어떻게 식을 이해하는지 보자. 먼저, 아래의 Tree를 infix, prefix, postfix 방식으로 읽어보자

우리가 2(x+2) + (x-y)/2로 바로 받아들일 Tree

정답은

 

Infix : x+y*2+x-y/2 

 

prefix : +*+xy2/-xy2

 

postfix : xy+2*xy-2/+

 

Infix같은 경우는 괄호가 없어서 애매하므로 좋은 수식이라고 말할 수가 없다.

 

prefix의 경우, 오른쪽에서부터 왼쪽으로 읽어나가면서 연산자를 만나면 가장최근의 두 숫자에 연산자를 적용하는 식이다. 여기서 보면 먼저 오른쪽에서 가장 가까운 연산자 -를 만나면 최근의 두 숫자 x, y사이에 뺄셈이 적용되고 그 다음 / 에서 (x-y) / 2가 일어나는 식이다. 이렇게 되면 자동으로 괄호가 적용되가면서 수식을 풀어나갈 수 있으므로 연산을 할 수 있다.

 

Postfix의 경우는 왼쪽에서부터 오른쪽으로 가면서 prefix와 같이 연산자를 만나면 가장 최근의 두 숫자에 연산자를 적용하는 식이다.

 

Prefix와 Postfix로 부터 우리는 원하는 식인 {(x+y)*2 + (x-y)/2} 를 구할 수 있다.

 

 

다음은 괄호가 없어서 애매한 Infix에 괄호를 씌우는 방법을 알아보자. 생각보다 간단한데, 왼쪽 subtree에는 개괄호 ' ( ' 를, 오른쪽 subtree에는 폐괄호 ' ) '를 출력한다. 알고리즘은 아래와 같다.