Chapter 08. 트리(Tree)

#08-1. 트리의 개요1

자료구조는 데이터를 저장하고 표현하는 학문이다. 저장 그리고 표현

비선형 자료구조 접근 하는 자체가 다르다. 

선형자료구조는 저장이 목적이었다. 

비선형자료구조는 진짜 표현이다.

구조체 삽입 함수 노드 추가 노드 삭제 A B 영... 구 성..

트리 구조체 + 함수 

                     삽

                     삭

                     조

트리를 구성하는데 만드는 도구를 만들 것이다. 함수를 만들것이다. 그 도구를 가지고 무언인가를 표현할 것이다. 

트리를 만드는 도구부터 만들 것이다.

#08-1. 트리의 개요2

< 저장, 삭제, 탐색 >

ㅁ > ㅁ > ㅁ 

도구.

목적없음.

이유?

언제?

하나의 중심점을 기준으로 뻗어나간다. 조직도 표현 가능. 

트리 표현을 위한 자료구조이다. 사고를 전환하자. 데이터의 저장이 아니다. 표현이라는 측면에서 접근하자!!.. 

#08-1. 트리의 개요3

깊이사고 시야 넓게 100% 넓게 이해 하려고 노력해야 한다. 

#08-1. 트리의 개요4

트리 트러버셜하려면 재귀적으로 해야 한다. 이것이 중요하다.

이진 트리의 조건

어떠한 때어나도 이진트리여야 한다. 

이진 트리라면 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.

#08-1. 트리의 개요5 

하나의 노드도 이진 트리이다?? 왜??..

이진트리에서 공집합 노드를 정의해 놓고 있다. 

빈 노드를 공집합 노드라고도 한다. 

기대치.. 노드를 최대 2개 까지 둘 수 있어서.. 

#08-1. 트리의 개요6

레벨과 높이, 그리고 포화, 완전 이진 트리

높이는 최대 레벨이 높이다. 

모든 레벨에 노드가 꽉 찬! 포화 이진 트리 FULL BINARY TREE..

완전 이진 트리 COMPLETE BINARY TREE.. 

위에서 아래로 왼쪽에서 오른쪽으로 빈틈없이 차례로 채워지는 것.. 

#08-2. 이진 트리의 구현 1

이진 트리의 구현 할 수 있는 도구를 만들 것이다..!!

배열을 기반으로 구현을 하겠다. 노드의 값을 매긴다. 노드 번호 노드 값

일반적으로 인덱스 0은 비워둔다. 왜 구현하게 되면 불편함이 생긴다. 

PROGRAMMER들이 프로그램의 안정도를 높이기 위해서 필요 없는 것은 떨쳐낸다.

양방향 연결 리스트라는 것을 알게 된다. 

#08-2. 이진 트리의 구현 2

이진 트리를 표현한 구조체이다.

이 구조체가 노드이자 구조체이다. 

#08-2. 이진 트리의 구현 3

#08-2. 이진 트리의 구현 4

#08-3. 이진 트리의 순회(Traversal) 1

재귀가 약하다면 이 분야 약할 수도 있다. 

중위 순회로 계속 내려가면 순회가 이루어진다. 중위 순회를 재귀적으로 구현을 하면 어떠한 트리건 간에 매우 간단하게 만들 수 있다. 

생각 할 시간 필요하다.

#08-3. 이진 트리의 순회(Traversal) 2

이진 트리 순회 그 안에 코드를 다시 한 번 더 불러서 수행한다.

자신의 생각, 논리를 설명해야 한다.

중위 순회

#08-3. 이진 트리의 순회(Traversal) 3

전위 순회..

후위 순회..

가능하다. 금방이다. 

#08-3. 이진 트리의 순회(Traversal) 4

노드의 방문 이유! 자류옵게 구성하기!!

함수 포인터 선언. 

typedef void VisitFucnPtr(BTdata data);

         반환형                데이터 전달 받음.            이게 더 이해하기 좋음..

void (*visitFuncPtr) _________

void  (BTD)

{

}

함수 포인터.. 

#08-4. 수식 트리(Expression Tree)의 구현 1

수식 트리는 중위 표현을 표현한 것이 아니다. 그냥 대등한 조건에서 표현한 수식 조건이다. 

수식트리 구축해 놓으면 표현하는거 어렵지 않다. 

#08-4. 수식 트리(Expression Tree)의 구현 2

수식 트리는 만드는 절차를 설명해 준다. 

그림(이론) -> code로 옮기는 과정이 필요하다.

중위 표기법의 수식 -> 후위 표기법의 수식 -> 수식 트리

스택이 어떻게 활용되는지 확인. 

구조체 정의. 공학적 마인드. 교과서적 마인드이다. 구조체 무시하지 않는다. 우선시 할 필요는 없다. 

전위, 중위, 후위 순회하여 출력 시

각각 전위, 중위, 후위 표기법의 수식이 출력된다.

#08-4. 수식 트리(Expression Tree)의 구현 3

12+7*     >>       

         수식 트리

컴퓨터는 단순학습, 반복학습을 잘한다.

피연산자를 가지고 계산해서 스택에 집어 넣는다. 서브트리를 스택에 어떻게 넣느냐?? 

피연산자 스택에 넣고 연산 보이면 트리만들어 연산해서 스택에 넣어준다. 

최종 결과는 스택에서 확인 할 수 있다.

#08-4. 수식 트리(Expression Tree)의 구현 4

이진 트리를 구성하는 도구의 활용.

#08-4. 수식 트리(Expression Tree)의 구현 5