이진 트리의 여러가지 연산 이진 트리를 활용하기 위해서는 여러가지 연산이 필요합니다. 예를 들어, 단말 노드의 개수만 구해야 하는 상황이 존재하거나 모든 데이터의 합, 최솟값을 구해야 하는 상황 등이 있습니다. 이진 트리를 활용하기 위해 사용할 수 있는 여러가지 연산에 관한 알고리즘을 작성해보았습니다. 트리에 존재하는 모든 노드의 개수 구하기 각각의 서브트리에 대하여 순환 호출한 다음 반환값에 1을 더하여 반환합니다. int get_node_count(TreeNode *node) { int count=0; if( node != NULL ) count = 1 + get_node_count(node->left)+ get_node_count(node->right); return count; } 트리의 높이 구..

이진 수식 트리 생성과 계산 수식 트리란 산술 식을 트리 형태로 표현한 트리입니다. 수식 트리에서 연산자들은 비단말 노드에 해당되며 피연산자들은 단말 노드에 해당됩니다. 전위, 중위, 후위 수식 표기법은 아래 포스팅에 설명되어있으니 참고하시기 바랍니다. [자료구조] 스택을 응용, 활용한 프로그램 스택을 응용한 예시로는 괄호 검사, 스택의 응용1 : 괄호 검사 프로그램 괄호의 종류에는 대괄호 [ , ] 중괄호 { , } 소괄호 ( , ) 가 있습니다. 프로그램을 구현하기 위해 다음 조건을 만족해야 합니 yjg-lab.tistory.com 수식 트리를 계산하는 방법은 여러가지 순회가 있으나 이 글에서는 후위순회를 사용합니다. 서브트리의 값을 순환호출하여 계산하고 연산자(비단말 노드)를 방문할 때 피연산자(양..

이진트리의 레벨 순회 레벨 순회는 각 노드를 레벨 순으로 검사하는 순회 방법입니다. 중위, 후위, 전위 순회가 스택을 사용했던 것에 비해 레벨 순회는 선입선출 기반의 큐를 사용하는 순회 법입니다. 위의 이진트리를 레벨 순회해보겠습니다. "만나는 노드를 꺼내서 출력하고 서브트리를 왼쪽부터 큐에 넣는다" 만 기억하면 됩니다. 먼저 루트를 방문하여 +를 큐에 넣습니다. 큐 : | + | +를 꺼내서 출력하고 서브트리인 *와 /를 큐에 넣습니다. 큐 : | * | / | *를 꺼내서 출력하고 서브트리인 A와 B를 큐에 넣습니다. 큐 : | / | A | B | /를 꺼내서 출력하고 서브트리인 C와 D를 큐에 넣습니다. 큐 : | A | B | C | D | A를 꺼내서 출력하고 큐에 넣을 서브트리는 없습니다. ..

이진 트리의 순회 순회(Traversal)란 어떠한 목적을 위해 트리의 노드들을 체계적으로 방문하는 것입니다. 순회의 방법에는 여러가지가 있으며 목적에 따라 어떤 순회를 선택할 것인지를 결정하게 됩니다. 전위 순회 (preorder traversal) : VLR 전위 순회는 루트 이진 트리->왼쪽 이진 트리->오른쪽 이진 트리 순으로 방문하는 방식입니다. 중위 순회 (inorder traversal) : LVR 중위 순회는 왼쪽 이진 트리->루트 이진 트리->오른쪽 이진 트리 순으로 방문하는 방식입니다. 후위 순회 (postorder traversal) : LRV 후위 순회는 왼쪽 이진 트리->오른쪽 이진 트리->루트 이진 트리 순으로 방문하는 방식입니다. 알고리즘 (inorder, preorder, p..

이진 트리의 구현, 표현 방법에는 배열을 이용한 방법과 연결리스트를 이용한 방법이 있습니다. 배열을 이용한 이진 트리의 구현 배열을 이용한 방법은 모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법입니다. 어떤 노드를 n이라고 할 때, n의 부모 노드의 인덱스(index)는 n/2 n의 왼쪽 자식 노드의 인덱스는 2n n의 오른쪽 자식 노드의 인덱스는 2n + 1 입니다. 위 그림에서 c노드의 배열 인덱스를 찾기 위해서는 i의 인덱스를 1이라고 할 때, 순차적으로 계산하면 됩니다. f의 인덱스 == (1 * 2), a의 인덱스 == (2 * 2), b의 인덱스 == (4 * 2 + 1), e의 인덱스 == (9 * ..

파일시스템과 파일 입출력 : fread(), fwrite(), fseek() 연습문제 01-01. 파일 내용에 쓰인 영문 소문자를 모두 대문자로 변경하는 프로그램을 작성하시오. 조건1 | 입력파일과 출력파일을 인자로 받아서 결과를 출력파일에 저장한다. 조건2 | 출력파일을 받지 않는 경우 터미널 창에 표준 출력한다. 실행결과 01-02. 파일 내용에 쓰인 내용을 역순으로 출력하는 프로그램을 작성하라. 조건1 | 입력파일과 출력파일을 인자로 받아서 결과를 출력파일에 저장한다. 조건2 | 출력파일을 받지 않는 경우 터미널 창에 오류를 출력한다. 실행결과

트리(tree) 트리는 계층적인 구조를 나타내는 비선형 자료구조입니다. 트리는 부모-자식 관계의 노드들로 이루어지며 트리를 응용한 분야로는 계층적 조직을 표현하거나 컴퓨터 파일들의 디렉토리 구조 조직, 인공지능에서의 결정 트리 등이 있습니다. 트리의 용어 노드(node) : 트리의 구성 요소입니다. 루트(root) : 부모가 없는 최상위 노드입니다. 서브 트리(subtree) : 하나의 노드와 그 노드들의 자손들의 이루어진 트리입니다. 단말노드(terminal node) : 자식이 없는 노드입니다. 비단말노드 : 적어도 하나의 자식을 가지는 노드입니다. 자식, 부모, 형제, 조상, 자손 노드: 용어 그대로의 의미입니다. 레벨(level) : 트리의 각층의 번호입니다. 높이(height) : 트리의 최대 ..

연결리스트로 구현한 스택 스택을 구현하는 데 있어서 연결리스트를 활용할 수 있습니다. 연결리스트로 스택을 구성하면 배열로 구성된 스택에 비해 크기의 제한이 없다는 장점이 있지만 반대로 메모리를 동적으로 할당하므로 할당과 해제에 따른 시간이 소모된다는 단점이 있습니다. 삽입 연산 연결리스트로 구현된 스택에 노드를 삽입하는 연산의 경우 다음 두 순서의 변경 사항이 필요합니다. 1. temp(삽입할 노드)의 link를 top으로 할당. 2. top을 temp로 할당. 이때 순서가 변경되어서는 안됩니다. 만약 top을 temp로 할당하는 과정을 먼저 수행하면 temp의 link가 가리킬 위치를 알 수 없게됩니다. 삭제 연산 연결리스트로 구현된 스택에 노드를 삭제하는 연산의 경우 다음 두 순서의 변경 사항이 필요..

파일시스템과 파일 입출력 : fopen(), fclose(), fgetc(), fputc() 연습문제 01-01. 명령줄 인수로 받은 텍스트 파일내의 문자의 수와 줄의 수를 출력하는 프로그램 ch12wc.c를 작성한다. 실행결과 01-02. 파일1에 파일2의 내용을 추가하는 프로그램 ch12append.c를 작성하라. 실행결과 01-03. 입력 파일의 홀수 줄 만을 출력 파일에 저장하는 프로그램 ch12cp.c를 작성하라. 실행결과 01-04. ch12cp의 입력파일과 출력파일을 diff로 비교해 보고 설명한다. 2d1 : origin.txt의 line2를 삭제하면 copied.txt의 line1과 같다. 4d2 : origin.txt의 line4를 삭제하면 copied.txt의 line2와 같다. 6d..

이중 연결리스트 이중 연결리스트는 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트입니다. 아래 그림처럼 노드의 왼쪽 링크(left link)와 오른쪽 링크(right link)가 각각 다른 노드의 오른쪽 링크와 왼쪽 링크를 연결짓고 있으며 특별하게 헤드도 노드로 이루어져 있습니다. 헤드노드 헤드노드는 데이터를 가지지 않고 오로지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드입니다. 따라서 헤드 포인터와의 구별이 필요하며 리스트가 공백상태라면 헤드 노드만 존재하는 상태입니다. 이때 헤드노드의 left link는 right link를 가리키며 right link는 left link를 가리키는 상태입니다. 삽입 연산 new_node를 before의 앞쪽에 삽입하는 연산입니다. (1)은 ..

gcc compile 연습문제 01-01. 다음 순서에 따라 수행하고 설명한다. test.c 파일을 컴파일하여 test0 실행 파일을 만든다. test.c 파일을 최적화 컴파일하여 test1 실행 파일을 만든다. (옵션 -O1 사용) test.c 파일을 최적화 컴파일하여 test2 실행 파일을 만든다. (옵션 -O2 사용) test.c 파일을 최적화 컴파일하여 test3 실행 파일을 만든다. (옵션 -O3 사용) diff 명령어를 사용하여 test0, test1, test2, test3가 같은지 다른지 확인한다. 01-02. 위 실행파일들의 수행 시간을 time 명령어로 측정 및 비교한다. 최적화 컴파일을 하지 않은 test0에서는 가장 느린 속도를 보였고 최적화 컴파일 -O1옵션으로 컴파일하니 속도가 ..

원형 연결리스트 원형 연결리스트에서 head 포인터는 마지막 노드를 가리키게 됩니다. 이러한 방식의 원형 리스트는 head는 마지막 노드를, head의 link는 첫 노드를 가리키므로 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리해집니다. 앞부분 삽입 연산 노드를 리스트의 첫 부분에 삽입하는 연산의 경우 두 가지의 변경 사항이 필요합니다. 1. node의 link를 head의 link로 할당 2. head의 link를 node로 할당 [중요] 이때 순서가 변경되어서는 안됩니다. 만약 2를 먼저 실행, 즉 head의 link를 먼저 변경해버리면 node의 link를 지정해 줄 주소를 알 수 없게됩니다. // 앞 삽입 ListNode* insert_first(ListNode* head, elemen..