이진 트리 - 이진 트리에 n개의 노드가 있을 경우 2n개의 링크 존재 2n개의 링크 중, n+1개의 링크 = NULL 2n개의 링크 중, n-1개의 링크 = 다른 노드를 가리킨다 NULL 링크에 중위 선행자/후속자를 저장해 놓은 트리 = 스레드 이진 트리 스레드 이진 트리 - NULL 링크를 이용해서 순환호출 없이 트리의 노드들을 순회 가능 - 단말 노드 / 비단말 노드를 구분하기 위해 is_thread 필드 필요 - 노드의 right를 후속자를 가리키게 설정, is_thread = 1로 설정 typedef struct treenode { char data; struct treenode* left; struct treenode* right; int is_thread; // 1이면 ->right는 중위 ..

수식 트리 - 산술 연산자(+, -, *, /), 피연산자로 구성 - 피연산자 = 단말노드 - 산술 연산자 = 비단말노드 - 각 루트노드들은 산술 연산자이기 때문에 루트보다 자식 노드(피연산자)들을 먼저 방문해야한다 그러므로 후위 순회를 사용 알고리즘 root에서부터 시작해서 해당 node가 NULL이면 그냥 return (종료) -- (1) 해당 node의 left, right가 모두 NULL이면 해당 node는 단말노드 = 피연산자 ∴ return 해당 node의 data -- (2) - (1), (2)에 해당이 안되면, 각 node의 left, right에서 (1), (2) 반복 Example) root(+) → evaluate(root->left) = '*' / evaluate(root->righ..

반복적 순회 (중위 순회) - 스택을 이용해서 구현 스택에 자식 노드들을 push하고 pop하면서 순회 - 인공지능에서 지능적 탐색을 할 때 사용 알고리즘 root에서부터 root->left로 진행하면서 stack에 push ( root = root->left를 통해서 반복) -- (1) root->left가 NULL이 되면 stack에서 하나씩 pop pop한 노드를 방문해서 해당 노드에서 node->right로 이동 node->right가 NULL이면, 그냥 stack에서 pop node->right가 NULL이 아니면 node->right로 이동해서 (1) 진행 - stack이 공백이 되면 순회 종료 void inorder_iter(treenode* root) { // LVR 순으로 순회 while..

노드의 개수 1. 트리안의 노드들을 전체적으로 순회 (함수 순환 호출) 2. 노드에 대한 각 서브트리들을 계속 순환 호출 (노드 != NULL) 3. 반환되는 값(왼쪽 서브트리, 오른쪽 서브트리 순회하면서 얻은 노드 개수)에 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. 트리안의 노드들을 전체적으로 순회 (함수 순환 호출) 2. 순회하면서 해당 노드의 왼쪽자식 = 오른쪽자식 = NULL ..

이진 트리 순회방법 - 루트 방문 : V - 왼쪽 서브트리 방문 : L - 오른쪽 서브트리 방문 : R 루트를 언제 방문하느냐에 따라 전위(1), 중위(2), 후위(3)로 구분 ① 전위순회 (preorder traversal) : VLR 루트 노드 방문 (V) 왼쪽 서브트리 방문 (L) 오른쪽 서브트리 방문 (R) void preorder(treenode* root) { // VLR 순 if (root!=NULL) { printf("[%d] ", root->data); preorder(root->left); preorder(root->right); } } ② 중위순회 (inorder traversal) : LVR 왼쪽 서브트리 방문 (L) 루트 노드 방문 (V) 오른쪽 서브트리 방문 (R) void in..

배열로 구현한 이진트리 - 노드 i의 부모 노드 인덱스 = i/2 - 노드 i의 왼쪽 자식 노드 인덱스 = 2i - 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1 연결리스트로 구현한 이진트리 - 노드를 구조체로 표현 - 노드(데이터, 왼쪽 링크필드, 오른쪽 링크필드) typedef int element; typedef struct treenode { element data; struct treenode* left; // 왼쪽 노드로 연결하는 포인터 struct treenode* right; // 오른쪽 노드로 연결하는 포인터 }treenode; ※ Example #include #include // 연결리스트로 구현한 이진 트리 typedef int element; typedef struct treen..

트리 - 계층적 구조(hierarchical structure)을 가진 자료구조 - 부모-자식 관계의 노드들로 구성 트리의 용어 - 노드(node) : 트리의 구성요소 → A, B, C, D, E, F, G, H, I, J - 루트(root) : 각 Tree의 최상위 노드 → A - 서브 트리(subtree) : 최상위 노드를 제외한 나머지 노드 / 하나의 노드 + 그 노드들의 자식 → {B, E, F, G}, {C, H}, {D, I, J} - 간선(edge) : 노드들 사이의 선 - 단말 노드(terminal node) : 자식이 없는 노드 → E, F, G, H, I, J - 비단말 노드(nonterminal node) : 자식이 있는 노드 → A, B, C, D - 높이(height) : Tree..