C 자료구조
-
1. Binary Search Tree 만들기 - 삽입과 탐색C 자료구조/6. Binary Search Tree Basic 2020. 6. 16. 11:47
시작 하기 전에, Tree에서 구현한 BinaryTree 헤더 파일과 소스파일이 필요하다. 그리고 BinarySearchTree에서의 삽입과 탐색 그리고 삭제 함수들은 모두 BinarySearchTree 헤더 파일과 소스 파일에 구현하도록 함. 1. 이진 탐색 트리의 정의 이진 탐색 트리란 이진 탐색 트리의 성질을 만족하는 이진 트리를 말한다. 이진 탐색 트리의 정의는 아래와 같다. (1). 모든 노드의 키는 유일하다. (2). 왼쪽 서브 트리의 키들은 루트의 키보다 작다. (3). 오른쪽 서브 트리의 키들은 루트의 키보다 크다. (4). 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 위의 정의와 같이, 찾고자 하는 키값이 이진 트리의 루트 노드의 키값과 비교하여 작으면 우리가 찾고자 하는 키값은 왼쪽..
-
4 - (2). 수식 트리 만들기( 수식 트리의 순회 )C 자료구조/5. 트리( Tree ) 2020. 6. 15. 11:05
아래의 내용에 이어서 진행하도록 하자. designatedroom87.tistory.com/12?category=869064 4 - (1). 수식 트리 만들기 ( 수식 트리 구성 & 수식 트리 계산 ) 이진 트리 순회는 수식 트리를 처리하는데 사용될 수 있다. 수식 트리는 산술식이나, 논리식의 연산자와 피연산자들로부터 만들어진다. 피연산자들은 단말 노드가 되며, 연산자는 비단말 노드 designatedroom87.tistory.com 수식 트리의 순회는 앞에서 이진 트리의 순회와 그 형태가 같다. designatedroom87.tistory.com/10?category=869064 2. 이진 트리의 순회 순회 알고리즘은 다음과 같다. 전위 순회는 루트를 먼저 방문하고, 그 다음에 왼쪽 서브 트리를 방문하..
-
4 - (1). 수식 트리 만들기 ( 수식 트리 구성 & 수식 트리 계산 )C 자료구조/5. 트리( Tree ) 2020. 6. 15. 00:24
이진 트리 순회는 수식 트리를 처리하는데 사용될 수 있다. 수식 트리는 산술식이나, 논리식의 연산자와 피연산자들로부터 만들어진다. 피연산자들은 단말 노드가 되며, 연산자는 비단말 노드가 된다. 각 이진 연산자에 대하여 왼쪽 서브 트리는 왼쪽 피연산자가 되며, 오른쪽 서브 트리는 오른쪽 피연산자를 나타낸다. [ 그림1 ] [ 그림2 ] [ 그림3 ] 구성에 앞서, 수식 트리 구성하는 함수와 수식 트리 계산하는 함수는 ExpressionTree 헤더 파일과 ExpressionTree 소스 파일에 정의. 1. 수식 트리 구성하기 수식 트리를 구성하기에 앞서 수식은 후위 표기법의 수식이며, 만약 중위 표기법의 식이면 이를 후위 표기법으로 변경이 필요하다. 아래의 글을 읽어보자. designatedroom87.t..
-
3. 이진 트리의 연산 ( 노드의 개수, 단말 노드의 개수, 트리의 높이 구하기 )C 자료구조/5. 트리( Tree ) 2020. 6. 13. 01:21
1. 이진 트리의 노드의 갯수 구하기 이진 트리 안의 노드의 갯수를 세어서 표시한다. 노드의 갯수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다. 각 각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환하면 된다. 이진 트리에서 노드의 갯수 구하는 알고리즘 의사코드 2. 단말 노드 갯수 구하기 단말 노드의 갯수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다. 순회하면서 만약 왼쪽 자식과 오른쪽 자식이 동시에 NULL이 되면, 단말 노드이므로 1을 반환한다. 만약 그렇지 않다면 비단말 노드이므로 각 각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값을 서로 더하면 된다. 이진 트리에서 단말 노드의 갯수 구하는 알고리즘 의사코드 3. 트리의 높이 구하..
-
2. 이진 트리의 순회C 자료구조/5. 트리( Tree ) 2020. 6. 11. 15:43
순회 알고리즘은 다음과 같다. 전위 순회는 루트를 먼저 방문하고, 그 다음에 왼쪽 서브 트리를 방문하고 오른쪽 서브 트리를 마지막으로 방문하는 것이다. 중위 순회는 먼저 왼쪽 서브 트리, 루트, 오른쪽 서브 트리 순으로 방문한다. 후위 순회는 왼쪽 서브 트리, 오른쪽 서브 트리, 루트 순으로 방문한다. 그림으로 보자. ㉠. 전위 순회 : VLR ㉡. 중위 순회 : LVR ㉢. 전위 순회 : LRV 이진 트리에서 각 각의 서브 트리도 이진 트리이다. 따라서, 서브 트리에서도 전체 이진 트리와 똑같은 방법을 적용할 수 있다. 즉, 전위 순회라면 서브 트리에 들어 있는 노드들도 VLR의 순서대로 순회된다. 트리 순회 알고리즘은 앞에서 한 순환 기법을 이용한다. 아래의 그림의 이진 트리에서 보면 전체 트리나 서..
-
1. 이진 트리를 구성하기C 자료구조/5. 트리( Tree ) 2020. 6. 11. 15:04
트리의 링크 표현법 링크표현법에서는 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법이다. 이진 트리를 링크 표현법으로 표현하여 보면 아래와 같다. 아래와 같은 이진 트리가 있다고 가정하자. 위의 이진 트리를 링크 표현법을 이용해서 그리면 아래와 같다. 위 내용을 바탕으로 프로그래밍을 해보자. 프로그램 결과창 위 프로그램 소스에 문제가 생겼다. 그 이유는 메인함수에서 트리를 생성(동적할당)하는데, 프로그램이 종료가 될 때, 해제를 해줘야 한다. 그 부분이 없다. 이는 뒤에 할 이진 트리의 순회를 하고나서 해결하도록 한다. 물론, 메인 함수 내에서 free함수를 호출해서 이를 해결할 수 있다. 아래는 소스파일
-
1. Stack 직접 만들기C 자료구조/3. 스택( Stack ) 2020. 6. 10. 12:01
우리는 아래의 포스트에서 라이브러리로 구현되어 있는 스택을 사용해봤다. designatedroom87.tistory.com/7?category=868809 0. stack library 맛 보기 제공하는 스택을 쓰기 위해서는 C++의 template에 대한 이해가 필요. main.cpp 프로그램 결과 designatedroom87.tistory.com 스택은 라이브러리로 구현이 되있기는하나, 속도가 느리며, 입맛대로 바꿀수 없다. 그렇기 때문에, 직접 만들어 봐야 한다. 스택의 기본적 모양은 아래와 같다. 아래의 Top은 연결 리스트에서의 Head와 역할이 같다. 스택은 나중에 들어간 데이터가 가장 맨 위에 위치한다. 여러개의 함수 및 구조체를 정의함에 따라 프로그램이 길어져 파일분할 합니다. 프로그램 ..