C 자료구조/5. 트리( Tree )
-
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함수를 호출해서 이를 해결할 수 있다. 아래는 소스파일