NULL 링크에 중위 후속자 (inorder successor)를 저장시켜 놓은 이진 트리입니다. 중위 후속자란 중위 순회의 순서에서 그 다음에 이어질 차례의 노드입니다. 중위 후속자로 인해 순환 호출 없이도 중위 순회가 간편하다는 장점이 있습니다. 스레드 이진 트리 구조체 typedef struct TreeNode { int data; struct TreeNode *left, *right; int is_thread; //만약 오른쪽 링크가 스레드이면 TRUE } TreeNode; 중위 후속자를 찾는 함수 TreeNode *find_successor(TreeNode *p) { // q는 p의 오른쪽 포인터 TreeNode *q = p->right; // 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른..

시스템 호출1 : open(), close(), read(), write() 연습문제 01-01. 명령줄 인수로 받은 텍스트 파일 내의 문자의 수와 단어의 수와 줄의 수를 출력하는 프로그램을 작성한다. 명령줄 인수가 없는 경우, 표준입력에서 받은 내용을 대상으로 한다. 쉘 명령어 wc와 같은 출력 결과를 내는지 확인하라. read() 가 읽은 바이트 수가 글자 수와 같으므로 그 값을 글자수를 카운트하는 변수 chn에 저장한다. ch에는 read로 읽은 문자들이 들어있는 buffer에서 반복문을 돌려 그 값이 단어를 구분하는 조건들에 부합하고 이전 글자가 역조건에 부합하면 단어 수를 증가시킨다. 줄바꿈을 만나면 줄 수를 증가시킨다. 실행결과 01-02. 파일에 직각삼각형을 출력하는 프로그램을 작성하시오. ..

파일시스템과 파일입출력 : fread(), fseek(), fopen(), fclose(), fwrite() 연습문제 01-01. 파일 내용안의 소문자를 모두 대문자로 변경하는 프로그램을 작성하시오. 입력파일로부터 문자 하나를 받고 대문자로 변환하여 출력파일에 저장하는 방식으로 작성합니다. 입력파일은 기본적으로 열고 입력파일이 없으면 표준 출력합니다. 인자가 3인 경우 출력파일에 출력합니다. 실행결과 01-02. 텍스트 파일을 역순으로 출력하는 프로그램 ch12reverse.c를 작성하라. 파일 스트림의 끝 위치를 먼저 구해주고 1부터 끝위치까지 반복하는 반복문에서 파일 끝 위치의 바로 앞 위치에서 문자 하나를 받아서 출력파일에 저장하는 방식으로 작성한다. 실행결과

이진 트리의 여러가지 연산 이진 트리를 활용하기 위해서는 여러가지 연산이 필요합니다. 예를 들어, 단말 노드의 개수만 구해야 하는 상황이 존재하거나 모든 데이터의 합, 최솟값을 구해야 하는 상황 등이 있습니다. 이진 트리를 활용하기 위해 사용할 수 있는 여러가지 연산에 관한 알고리즘을 작성해보았습니다. 트리에 존재하는 모든 노드의 개수 구하기 각각의 서브트리에 대하여 순환 호출한 다음 반환값에 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를 꺼내서 출력하고 큐에 넣을 서브트리는 없습니다. ..