이진 트리의 여러가지 연산 이진 트리를 활용하기 위해서는 여러가지 연산이 필요합니다. 예를 들어, 단말 노드의 개수만 구해야 하는 상황이 존재하거나 모든 데이터의 합, 최솟값을 구해야 하는 상황 등이 있습니다. 이진 트리를 활용하기 위해 사용할 수 있는 여러가지 연산에 관한 알고리즘을 작성해보았습니다. 트리에 존재하는 모든 노드의 개수 구하기 각각의 서브트리에 대하여 순환 호출한 다음 반환값에 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 수식 트리를 계산하는 방법은 여러가지 순회가 있으나 이 글에서는 후위순회를 사용합니다. 서브트리의 값을 순환호출하여 계산하고 연산자(비단말 노드)를 방문할 때 피연산자(양..

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

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