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

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