쌓고 쌓다

노드 typedef struct TreeNode { int key; TreeNode* left, * right; }TreeNode; 노드의 삭제 삭제에 필요한 함수 TreeNode* min_value_node(TreeNode* node) { TreeNode* current = node; while (current->left != NULL) { current = current->left; } return current; } node의 가장 왼쪽에 있는 노드를 찾아 반환해줌 삭제 함수 TreeNode* delete_node(TreeNode* root, int key) { if (root == NULL) return root; if (key key) // 왼쪽 서브트리로 이동 root->left..

전체 코드 #include #include typedef struct TreeNode { int key; TreeNode* left, * right; }TreeNode; void delete_node(TreeNode** root, int key) { TreeNode* p, * child, * succ, * succ_p, * t; // key를 갖는 노드 t(arget)를 탐색, p는 t의 부모 p = NULL; t = *root; while (t != NULL && t->key != key) { p = t; t = (key key) ? t->left : t->right; } if (t == NULL) { printf("트리에 키가 존재하지 않음."); return; } if (t->left ==..

이진트리의 노드 개수 구하기 탐색 트리 안의 노드의 개수를 계산해준다. 각각의 서브 트리에 대하여 순환 호출, 반환 되는 값에 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; } 처음에 루트를 전달하면 총 6이 반한되어 나온다. 이진트리의 높이 구하기 서브 트리에 대하여 순환 호출하고 반환 값 중에서 최댓값을 반환해준다. int get_height(TreeNode* node) { int height = 0; if (node != NULL) { height =..

순회 방법 전위 순회(preorder traversal) : 루트노드->Left->Right 방문, VLR 중위 순회(inorder traversal) : Left->루트노드->Right, LVR 후위 순회(postorder traversal) : Left->Right->루트노드, LRV _L_R_ : L R은 고정적이고 V의 위치에 따라 순회 방식이 정해진다. _를 선택하여 V 삽입 전위 순회 (preorder traversal) : 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 // 전위 순회 void preorder(TreeNode* root) { if (root) { printf("%d", root->data); // 루트 노드 방문 preorder(root->left); // 왼쪽 서브..

이진 트리의 표현 - 배열 표현법 : 모든 이진 트리를 포화 이진 트리라고 가정하여 각 노드에 번호를 붙인다. 인덱스 관계 노드 i의 왼쪽 자식 노드 인덱스 : i*2 노드 i의 오른쪽 자식 노드 인덱스 : i*2+1 노드 i의 부모 노드 인덱스 : i/2 이진 트리의 표현 - 링크 표현법 : 포인터를 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법 노드는 구조체로 링크는 포인터로 구현한다. 아래의 그림같은 트리를 구현해보자. 전체 코드 #include #include typedef struct TreeNode { int data; TreeNode* left, * right; }TreeNode; int main(void) { TreeNode* n1, * n2, * n3; n1 = (TreeNode*..

트리(Tree)는 나무를 뒤집어 놓은 모습과 같은 비선형이며 계층적인 구조이다. 부모-자식 관계의 노드들로 구성 컴퓨터 디스크의 디렉토리 구조 또한 트리이다. 트리의 용어 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드 ( 젤 위의 노드를 뜻함, A ) 서브 트리(sub tree) : 하나의 노드와 그 노드의 자손들로 이루어진 트리 단말 노드(terminal node) : 자식이 없는 노드 (E,F,G,H,I,J) 비 단말 노드 : 적어도 하나의 자식을 가지는 노드 (A,B,C,D) 자식, 부모, 형제, 조상, 자손 노드 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 레벨(level) : 트리의 각층의 번호 높이(height) : 트리의 최대 레벨(3) 아래의 그래..

단순 연결 리스트 리스트의 항목들을 노드(node)라고 함 노드는 데이터 필드와 링크 필드로 구성 데이터 필드 : 리스트의 원소, 값을 저장하는 곳 링크 필드 : 다른 노드의 주소 값을 저장하는 곳 ( 포인터 ) 마지막 노드의 링크 값은 NULL 헤드 포인터 : 리스트의 첫 번째 노드를 가리키는 변수 연결 리스트의 장점 삽입, 삭제가 용이 연속된 공간 필요 X 크기 제한 X ( 배열의 경우 크기 제한이 있음 ) 연결 리스트의 단점 구현이 어려움 오류 발생률이 높음 노드 ( 구조체로 정의 ) #include #include typedef int element; typedef struct ListNode { element data; // 데이터 필드 struct ListNode* link; // 링크 필드 ..

배열로 만든 리스트 구현이 간단하다. 삽입, 삭제 시 오버헤드 문제 발생 항목의 개수가 제한적 구조체 구현 #define MAX_SIZE 10 using namespace std; typedef int element; typedef struct { int length; // 저장된 개수 element list[MAX_SIZE]; }ArrayListType; 초기화 함수 void init(ArrayListType* L) { L->length = 0; } is_empty 함수 bool is_empty(ArrayListType* L) { if (L->length == 0) return true; return false; } is_full 함수 bool is_full(ArrayListType* L) { if (..