트리

- 계층 구조 (부모 & 자식 관계)

트리 구조

- n개의 노드를 갖는 이진 트리의 높이

최대 n

최소⌈log_2⁡(n+1)⌉

 

- 완전 이진 트리(complete b-tree)

레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

 

- 이진 트리 구현 

--> 배열 : 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

–노드 i의 부모 노드 인텍스 = i/2

–노드 i의 왼쪽 자식 노드 인텍스 = 2i

–노드 i의 오른쪽 자식 노드 인텍스 = 2i+1

--> 링크 :

–연결 리스트처럼 포인터를 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법

typedef struct TreeNode { ////구조체

  int data;

  struct TreeNode *left, *right;

} TreeNode;

int  main()

{

  TreeNode *n1, *n2, *n3;

 

  n1= (TreeNode *)malloc(sizeof(TreeNode));

  n2= (TreeNode *)malloc(sizeof(TreeNode));

  n3= (TreeNode *)malloc(sizeof(TreeNode));

 

 n1->data = 10;     // 첫번째 노드를 설정한다.

  n1->left = n2;

  n1->right = n3;

 

  n2->data = 20;     // 두번째 노드를 설정한다.

  n2->right = NULL;

 

  n3->data = 30;     // 세번째 노드를 설정한다.

  n3->right = NULL;

}