분류 전체보기44 [자료구조]이진 트리를 Linked List로 표현하기 이진 트리를 배열이 아닌 Linked List로 표현하는 경우가 많습니다. 다음은 이진 트리를 Linked List로 표현하기 위해 만든 각 노드를 나타낼 구조체 입니다. typedef struct treeNode* treePointer; typedef struct treeNode{ int data; treePointer leftChild; treePointer rightChild; } treeNode; data에는 각 노드에 할당된 값이 들어갑니다. leftChild에는 왼쪽 자식 노도의 주소값이 들어갑니다. 만약 왼쪽 자식이 없다면 leftChild에는 NULL을 넣습니다. rightChild에는 오른쪽 자식 노도의 주소값이 들어갑니다. 만약 오른쪽 자식이 없다면 rightChild에는 NULL을 넣.. 2023. 5. 24. [자료구조]완전 이진 트리를 배열로 나타내기 일반적으로 leftChild와 rightChild를 통해 노드를 연결해가면서 트리를 만듭니다. 하지만 이 완전 이진 트리를 배열 형태로 나타낼 수 있습니다. 위와 같은 완전 이진 트리 있다고 가정합시다. 위 이진 트리에는 12개의 노드가 있습니다. 충분한 크기의 배열이 있다고 가정합시다. root 노드인 노드 A의 값을 1번째 인덱스에 넣습니다. 노드 A의 leftChild인 노드 B의 값을 2번째 인덱스에 넣습니다. 노드 A의 rightChild인 노드 C의 값을 3번째 인덱스에 넣습니다. 그 다음, 노드 B의 leftChild인 노드 D의 값을 4번째 인덱스에 넣습니다. 이런 식으로, level이 낮은 노드부터, level이 같다면 왼쪽에 있는 노드부터 차례대로 배열에 넣습니다. 여기에는 한 가지 규.. 2023. 5. 24. [자료구조]두 이진 트리가 같은지 판별하는 법(Testing for Equality of Binary Trees) 재귀적인 방식을 통해 두 이진 트리의 구조와 각 노드에서의 값을 비교함으로써 두 이진 트리가 같은지 판별할 수 있다. 아래는 이진 트리의 각 노드로 사용될 구조체입니다. typedef struct treeNode* treePointer; typedef struct treeNode{ int data; treePointer leftChild; treePointer rightChild; } treeNode; 아래 함수의 매개변수로 두 이진 트리의 root를 넣으면, isEqual 함수가 재귀적으로 실행되면서 두 이진 트리의 구조와 각 노드에서의 값을 비교하면서 같은지 같지 않은지를 판별합니다. 같으면 1을 리턴하고, 같지 않다면 0을 리턴합니다. int isEqual(treePointer first, tree.. 2023. 5. 23. [자료구조]이진 트리를 복사하는 법(Copying Binary Trees) 재귀적인 방식을 통해 기존의 이진 트리를 복사할 수 있습니다. 아래는 이진 트리의 각 노드로 사용될 구조체입니다. typedef struct treeNode* treePointer; typedef struct treeNode{ int data; treePointer leftChild; treePointer rightChild; } treeNode; 아래 함수에 기존 이진 트리의 root(treePointer)를 넣으면 재귀적인 방식으로 복사되어, 최종적으로는 복사되어 만들어진 이진 트리의 root(treePointer)가 반환됩니다. treePointer copyBinaryTree(treePointer original){ treePointer temp; if(original) { temp = (treeP.. 2023. 5. 23. [자료구조]트리 순회(Tree Traversals) 트리 순회(Tree Traversals)의 개념 -트리 구조에서, 모든 노드를 효율적이고 체계적인 방법으로 한 번씩 순회하는 과정 트리 순회의 종류 -트리 순회 방식에는 대표적으로 4가지가 있습니다. 전위 순회(Preorder Traversal) 중위 순회(Inorder Traversal) 후위 순회(Postorder Traversal) 레벨 순서 순회(Level Order Traversal) 아래는 각 트리 순회에 사용될 코드입니다.(C언어) typedef struct treeNode* treePointer; typedef struct treeNode{ int data; treePointer leftChild; treePointer rightChild; } treeNode; 1. 전위 순회(Preord.. 2023. 5. 23. [자료구조]이진 트리(Binary Tree)의 종류 이진 트리(Binary Tree)의 개념 -이진 트리(Binary Tree) : 모든 노드의 자식 노드가 최대 두 개인 트리 이진 트리(Binary Tree)의 종류 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있고, 마지막 노드는 왼쪽부터 있는 이진 트리 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 혹은 2개의 자식 노드를 갖는 이진 트리 포화 이진 트리(Perfect Binary Tree) : 모든 레벨이 전부 채워져 있는 이진 트리 사향 이진 트리(Skewed Binary Tree) : 모든 내부 노드가 한쪽 방향으로 1개의 자식 노드만을 가진 이진 트리 1. 완전 이진 트리(Complete Binary Tre.. 2023. 5. 19. 이전 1 ··· 4 5 6 7 8 다음
