자료구조

Ch 8. 트리(Tree)

• 이진 트리 (binary tree): 공집합도 노드로 간주 → 모두 이진 트리
  • 레벨 0 ~ N, 높이: N → 높이 = 레벨의 최댓값
• 포화 이진 트리: 모든 레벨에 노드가 꽉 차 있는 이진 트리
• 완전 이진 트리: 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리

 

연결 리스트 기반 (BinaryTree)

• 트리의 구조와 일치

typedef struct _bTreeNode {
	BTData data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode * bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

 

이진 트리의 순회 (BinaryTreeTraversalAdded)

• 중위 순회(InorderTraverse): 왼 → 위 → 오
• 후위 순회(PostorderTraverse): 왼 → 오 → 위
• 전위 순회(PreorderTraverse: 위 → 왼 → 오

typedef void VisitFuncPtr(BTData data);
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);

 

수식 트리 (ExpressionTree)

• 중위 표기법(Infix)의 수식 → 후위 표기법(Postfix)의 수식 → 수식트리
• 후위 표기법
  • 피연산자 스택으로, 연산자 만나면 스택에서 피연산자 두 개 꺼내어 트리 구성
  • 형성된 트리는 다시 스택으로 (연산자가 저장된 노드의 주소값을 스택에 push)

BTreeNode * MakeExpTree(char exp[]);
int EvaluateExpTree(BTreeNode * bt);

void ShowPrefixTypeExp(BTreeNode * bt);		// 전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode * bt);		// 중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode * bt);	// 후위 표기법 기반 출력

 

Ch 9. 우선순위 큐와 힙

UsefulHeap

• 우선순위 큐 비교 기준 결정
• 힙(Heap) 이용 - 완전 이진 트리
  • 최대 힙 - 모든 노드의 값은 자식 노드의 값보다 크거나 같아야 함
  • 최소 힙 - 모든 노드의 값은 자식 노드의 값보다 작거나 같아야 함
• 데이터 저장 과정
  • 새 데이터 우선순위가 낮다는 가정하에 끝에 저장한 후 부모 노드와 비교
• 데이터 삭제 과정
  • 마지막 노드를 루트 노드로 이동한 후 자식 노드와 비교
• 배열 기반
  • 인덱스가 0인 요소 비워둠
  • 힙에 저장된 노드의 개수 = 마지막 노드의 고유번호
  • 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2
  • 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 + 1
  • 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2

// d1의 우선순위가 높다면 0보다 큰 값
// d2의 우선순위가 높다면 0보다 작은 값
// d1과 d2의 우선순위가 같다면 0을 반환
typedef int PriorityComp(HData d1, HData d2);

typedef struct _heap
{
	PriorityComp * comp;
	int numOfData;
	HData heapArr[HEAP_LEN];
} Heap;

/*** Heap 관련 연산들 ****/
void HeapInit(Heap * ph, PriorityComp pc);
int HIsEmpty(Heap * ph);

void HInsert(Heap * ph, HData data);
HData HDelete(Heap * ph);

 

Ch 11. 탐색1 - 트리

이진 탐색과 보간 탐색은 정렬이 완료된 데이터를 대상으로 탐색

• 이진 탐색: 중간에 위치한 데이터를 탐색 위치로 결정
• 보간 탐색: 대상에 비례하여 탐색 위치 결정

이진 탐색 트리 (BinarySearchTreeDelAdded)

• 왼쪽 서브 트리 < 루트 노드 < 오른쪽 서브 트리
• BSTInsert: 루트 노드부터 탐색, 비교대상이 없을 때까지 내려감 → 새 데이터 저장될 위치
• BSTSearch: 삽입의 과정을 근거로 탐색 → 탐색 성공시 해당 노드 주소값 반환
• BSTRemove
  • 상황 1: 삭제할 노드가 단말 노드
  • 상황 2: 삭제할 노드가 하나의 자식 노드를 갖는 경우
  • 상황 3: 삭제할 노드가 두 개의 자식 노드를 갖는 경우

typedef BTData	BSTData;

void BSTMakeAndInit(BTreeNode ** pRoot);	// BST의 생성 및 초기화
BSTData BSTGetNodeData(BTreeNode * bst);	// 노드에 저장된 데이터 반환
void BSTInsert(BTreeNode ** pRoot, BSTData data);	// BST를 대상으로 데이터 저장(노드의 생성과정 포함)
BTreeNode * BSTSearch(BTreeNode * bst, BSTData target);	// BST를 대상으로 데이터 탐색

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target);	// 트리에서 노드를 제거하고 제거된 노드의 주소 값을 반환
void BSTShowAll(BTreeNode * bst);	// 중위 순회 작은 것부터 순서대로! 이진 탐색 트리에 저장된 모든 노드의 데이터를 출력한다.

//BinaryTree3.h
BTreeNode * RemoveLeftSubTree(BTreeNode * bt);	// 왼쪽 자식 노드 제거, 제거된 노드의 주소 값이 반환
BTreeNode * RemoveRightSubTree(BTreeNode * bt);	// 오른쪽 자식 노드 제거, 제거된 노드의 주소 값이 반환
void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub);	// 메모리 소멸을 수반하지 않고 main의 왼쪽 자식 노드를 변경
void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub);	// 메모리 소멸을 수반하지 않고 main의 오른쪽 자식 노드를 변경

 

Ch 14. 그래프

• ALGraph (인접 리스트 기반) - 알파벳
• ALGraph_숫자 버전 - 숫자

typedef struct _ual
{
	int numV;   // 정점의 수
	int numE;   // 간선의 수
	List * adjList;   // 간선의 정보
} ALGraph;

void GraphInit(ALGraph * pg, int nv);	// 그래프의 초기화
void GraphDestroy(ALGraph * pg);	// 그래프의 리소스 해제
void AddEdge(ALGraph * pg, int fromV, int toV);	// 간선의 추가
void ShowGraphEdgeInfo(ALGraph * pg);	// 유틸리티 함수: 간선의 정보 출력

 

깊이 우선 탐색 : Depth First Search

• ALGraphDFS - 알파벳
• ALGraphDFS_숫자 - 숫자 
  • Stack 사용
  • 한 사람한테만 연락. 연락할 사람이 없으면 자신에게 연락한 사람한테 이를 알림
  • 처음 연락을 시작한 사람의 위치에서 연락이 끝남

typedef struct _ual
{
	int numV;   // 정점의 수
	int numE;   // 간선의 수
	List * adjList;   // 간선의 정보
	int * visitInfo;	// 탐색이 진행된 정점 정보
} ALGraph;

void GraphInit(ALGraph * pg, int nv);	// 그래프의 초기화
void GraphDestroy(ALGraph * pg);	// 그래프의 리소스 해제
void AddEdge(ALGraph * pg, int fromV, int toV);	// 간선의 추가
void ShowGraphEdgeInfo(ALGraph * pg);	// 유틸리티 함수: 간선의 정보 출력
void DFShowGraphVertex(ALGraph * pg, int startV);	// Depth First Search: 정점의 정보 출력

int VisitVertex(ALGraph * pg, int visitV)	// 방문한 정점 정보 기록 및 출력

 

너비 우선 탐색 : Breadth First Search

• ALGraphBFS - 알파벳
• ALGraphBFS_숫자 - 숫자
  • Queue 사용
  • 연결된 모든 이한테 연락. 연락 받은 대상을 큐에 저장
  • 큐에서 꺼낸 사람을 기준으로 연락을 취하고 연락 받은 사람을 큐로 이동
  • 큐가 빌 때까지 반복

typedef struct _ual
{
	int numV;   // 정점의 수
	int numE;   // 간선의 수
	List * adjList;   // 간선의 정보
	int * visitInfo;
} ALGraph;

void GraphInit(ALGraph * pg, int nv);	// 그래프의 초기화
void GraphDestroy(ALGraph * pg);	// 그래프의 리소스 해제
void AddEdge(ALGraph * pg, int fromV, int toV);	// 간선의 추가
void ShowGraphEdgeInfo(ALGraph * pg);	// 유틸리티 함수: 간선의 정보 출력
void BFShowGraphVertex(ALGraph * pg, int startV);	// Breadth First Search: 정점의 정보 출력

 

최소 비용 신장 트리 (사이클 형성하지 않는 그래프)

• 크루스칼 알고리즘 1
  • 가중치 오름차순 정렬
  • 가중치가 작은 것부터 간선을 선택해나감
  • 사이클이 형성되는 것은 건너뜀
  • 간선의 수 + 1 = 정점의 수
• 크루스칼 알고리즘 2
  • 가중치 내림차순 정렬
  • 높은 가중치의 간선을 하나씩 빼는 방식
  • 간선을 없앤 후에 모든 정점이 연결되지 않으면 복구
  • 간선의 수 + 1 = 정점의 수

typedef struct _edge
{
	int v1;
	int v2;
	int weight;   // 가중치
} Edge;

typedef struct _ual
{
	int numV;
	int numE;
	List * adjList;
	int * visitInfo;
	PQueue pqueue;    // 간선의 가중치 정보 저장
} ALGraph;

void GraphInit(ALGraph * pg, int nv);	// 그래프의 초기화
void GraphDestroy(ALGraph * pg);	// 그래프의 리소스 해제
void AddEdge(ALGraph * pg, int fromV, int toV, int weight);	// 간선의 추가
void ShowGraphEdgeInfo(ALGraph * pg);	// 간선의 정보 출력
void DFShowGraphVertex(ALGraph * pg, int startV);	// Depth First Search: 정점의 정보 출력
void ConKruskalMST(ALGraph * pg);	// 크루스칼 최소 비용 신장 트리의 구성
void ShowGraphEdgeWeightInfo(ALGraph * pg);	// 간선의 가중치 정보 출력

void RemoveWayEdge(ALGraph * pg, int fromV, int toV)	// 한쪽 방향의 간선 소멸: ConKruskalMST Helper function
void RemoveEdge(ALGraph * pg, int fromV, int toV)	// 무방향 그래프로 두 개의 간선 모두 삭제(간선의 소멸): ConKruskalMST Helper function
void RecoverEdge(ALGraph * pg, int fromV, int toV, int weight)	// 간선 복원 ConKruskalMST Helper function
int IsConnVertex(ALGraph * pg, int v1, int v2)	// 두 정점이 연결되어 있다면 TRUE, 그렇지 않다면 FALSE 반환