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