주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 앞서 수식 트리를 구현할 때 수식 트리를 계산하는 함수는 소개하지 않았습니다. 그때 제가 소개했던 것은 제가 직접 구현한 함수였습니다. 이제 책에서는 수식 트리를 어떻게 구현하고 있는지 소개하겠습니다. int EvaluateExpTree(BTreeNode* bt) { int op1, op2; if (GetLeftSubtree(bt) == NULL && GetRightSubTree(bt) == NULL) { return GetData(bt); } op1 = EvaluateExpTree(GetLeftSubTree(bt)); op2 = ..
Chapter 08. 수식 트리(Expression Tree)의 구현
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이진 트리를 이용해서 수식을 표현해 놓은 것을 가리켜 '수식 트리'라고 합니다. 즉 수식 트리는 이전 트리와 구분이 되는 별개의 것이 아닙니다. 먼저 다음의 수식을 보겠습니다. 7 + 4 * 2 - 1 우리는 보통 이러한 수식을 컴퓨터가 스스로 알아서 인식할 수 있다고 생각합니다. 그렇다면 컴파일러는 어떻게 이러한 수식을 처리하는 걸까요? 알다시피 컴파일러는 위의 코드를 실행이 가능한 상태로 만드는 소프트웨어입니다. 그런데 그 방법을 인간이 결정하여 컴파일러에게 인식시킨다는 사실을 놓치는 경우가 종종 있습니다. 컴퓨터의 유연한 판단..
Chapter 08. 이진 트리의 순회
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 앞서 트리의 노드를 삭제할 때, 그 후손 노드까지 전부 삭제해야 한다고 말했습니다. 그러기 위해서는 삭제하고자 하는 노드의 모든 후손 노드들에 접근하는 일을 수행해야 합니다. 이를 '순회'라고 합니다. 이진 트리의 순회가 필요한 이유는 앞서 설명했으니, 이진 트리의 순회 방법을 설명하겠습니다. 이진 트리를 대상으로 하는 대표적인 순회 방법은 다음과 같습니다. 전위 순회(Preorder Traversal) 루트 노드를 먼저 중위 순회(Inorder Traversal) 루트 노드를 중간에 후위 순회(Postorder Traversal)..
Chapter 08. 이진 트리의 구현
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이제 이진 트리를 직접 구현해 볼 차례입니다. 그런데 이진 트리는 재귀적인 특성을 지니고 있습니다. 이런 재귀적인 특성 때문에 이진 트리와 관련된 일부 연산은 재귀 호출의 형태를 띱니다. 따라서 여러분은 재귀적인 사고에, 그리고 재귀 함수의 정의에 어느 정도 익숙한 상태여야 합니다. 이진 트리 역시 배열 기반으로도, 그리고 연결 리스트를 기반으로도 구현이 가능합니다. 하지만 트리를 표현하기에는 연결 리스트가 더 유연하기 때문에 앞으로 대부분의 트리는 연결 리스트를 기반으로 구현하게 됩니다. 하지만 이진 트리라면, 특히 매우 빈번한 ..
Chapter 08. 트리의 개요
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 지금부터 배우게 될 트리는 고급 자료구조로 구분이 됩니다. 그리고 앞서 설명한 선형 자료구조들과 달리 비선형 자료구조이기 때문에 어렵게 느껴질 수 있습니다. 자료구조라고 하면 보통은 데이터를 저장하고 정리하고 꺼내는 것이 전부인 것으로 생각하기 쉽습니다. 물론 지금까지 배운 리스트, 스택, 큐, 덱의 경우는 그래 왔습니다. 하지만 이를 트리에 대해서도 동일하게 생각하면 안 됩니다. 트리는 단순히 데이터를 저장하고 꺼내는 자료구조가 아닙니다. 트리는 계층적 관계를 표현하는 자료구조입니다. 때문에 나중에 보게 될 트리의 ADT를 볼 때..
덱을 이해하고 있다면 덱을 큐처럼 사용할 수 있다는 사실을 알고 있을 것입니다. 따라서 덱을 이용해서 큐를 구현해 보기로 합니다. 다음 두 파일을 만들어서 덱을 기반으로 하여 큐를 구현해 봅니다. DequeBaseQueue.h 큐의 구현을 위한 헤더 파일 DequeBaseQueue.c 큐를 구현하고 있는 소스 파일 큐의 구현에 사용되는 덱의 헤더 파일과 소스 파일은 앞서 양방향 연결 리스트 기반으로 정의했던 것을 사용합니다. 그리고 큐의 헤더 파일에는 다음 함수들이 선언되어야 합니다. void QueueInit(Queue* pq); //큐의 초기화 int QIsEmpty(Queue* pq); //큐가 비어 있는지 확인 void Enqueue(Queue* pq, Data data); //큐에 데이터 저장 ..