[Coding Interview University] 트리 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 트리

: 하나의 루트 코드를 가진다

: 루트 노드는 0개 이상의 자식 노드를 갖고 있다

: 트리에는 사이클 존재할 수 없다

: 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다

: 각 노드는 어떤 자료형으로도 표현이 가능하다

노드(node)	트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소
간선(edge)	노드와 노드를 연결하는 연결선
루트 노드(root node)	트리 구조에서 최상위에 존재하는 A와 같은 노드
단말 노드(terminal node, leaf node)	아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드
내부 노드(internal node),비 단말 노드(non-terminal node)	단말 노드를 제외한 모든 노드로 A, B와 같은 노드
디그리(degree,차수)	각 노드에서 뻗어나온 가지의 수 A=3, B=2
트리의 디그리	노드들의 디그리 중에서 가장 많은 수 A가 3개의 디그리를 가지기 때문에 트리의 디그리는 3이다.
부모 노드(parent node)	어떤 노드에 연결된 이전 레벨의 노드 E,F의 부모노드는 B
형제 노드(brother node)	동일한 부모를 갖는 노드들 E의 형제노드는 F

 

높이(height)	트리의 최고 레벨을 가리켜 '높이'라 한다
레벨(level),	깊이 트리에서의 각 층별로 숫자로 매겨서 이를 트리의 '레벨'이라 한다

 

🫧 BFS 노트

• level order (BFS, 큐를 사용하여)
• 시간 복잡도: O(n)
• 공간 복잡도: 최고: O(1) 최악: O(n/2)=O(n)

 

🫧 DFS 노트

• 시간 복잡도: O(n)
• 공간 복잡도: 최고: O(log n) - 평균적으로, 트리의 높이이다. 최악: O(n)
• 중위(inorder) (DFS: 왼쪽, 자신, 오른쪽)
• 후위(postorder) (DFS: 왼쪽, 오른쪽, 자신)
• 전위(preorder) (DFS: 자신, 왼쪽, 오른쪽)

 

🫧 노드의 선언

#define N 10

typedef struct tagNode {
	char data;
	int degree;
	struct tagNode child[N];
} Node;

 

🫧 트리의 선언

typedef struct tagTree {
	Node *root;
}Tree;

 

🫧 생성자

Node* newNode(char data) {
	Node* returnNode = (Node*)malloc(sizeof(Node));
	returnNode->data = data;
	returnNode->degree = 0;
	returnNode->child = NULL;
	return returnNode;
}

Tree* newTree() {
	Tree* returnTree = (Tree*)malloc(sizeof(Tree));
	returnTree->root = NULL;
	return returnTree;
}

 

🫧 트리

#include <stdio.h>
#include <stdlib.h>

typedef struct node //구조체 정의
{
    int data;
    struct node *left;
    struct node *right;
}NODE;
  
/* newNode(): 노드에 메모리 할당하고 초기화*/
NODE* newNode(int data)
{
  //노드에 메모리 할당 
  NODE* node = (NODE*)malloc(sizeof(NODE));
  
  //데이터 넣음
  node->data = data;
  
  // 왼쪽, 오른쪽 노드를 NULL로 초기화
  node->left = NULL;
  node->right = NULL;
  return(node);
}
  
  
int main()
{
  /*루트 노드를 만든다*/
  NODE *root = newNode(1);  
  /* 루트 노드를 만든 상태
  
        1
      /   \\
     NULL  NULL  
  */
    
  
  root->left        = newNode(2);
  root->right       = newNode(3);
  /* 루트 노드1에 왼쪽, 오른쪽에 각각 2, 3이라는 자식 노드 추가한 상태
           1
         /   \\
        2      3
     /    \\    /  \\
    NULL NULL NULL NULL
  */
  
  
  root->left->left  = newNode(4);
  /* 2의 왼쪽 자식으로 4를 추가한 상태
           1
       /       \\
      2          3
    /   \\       /  \\
   4    NULL  NULL  NULL
  /  \\
NULL NULL
*/
  
  getchar();
  return 0;
}