컴퓨터과학 자료구조 트리

트리 : 검색의 편리함, 논리적 계층, 계급적 특성

트리의 구성 : 부모노드-자식노드 => 상하 계층구조가 있음

루트노드 : 트리의 최상위 노드, 진입차수 = 0 

서브트리 : 부모노드를 삭제하면 생기는 트리들

리프노드 : 트리의 맨 아래 있으면서 자신의 서브트리를 갖지 않는 노드, 진출 차수 = 0

노드의 레벨 : 루트로부터 해당 노드까지 이어진 선(경로)의 길이

이진트리

 - 모든 노드의 차수가 2이하인 트리(0, 1, 2)

완전이진트리 : 이진트리에서 각 레벨에서 허용하는 최대 개수를 가지는 트리

포화이진트리 : k-2 레벨까지 다 채우고 마지막 k-1 레벨에서 왼쪽부터 노드들이 차례로 채워진 이진트리

이진트리의 순회

 - 전위순회(PLR) : 루트 방문, 왼쪽 서브트리를 전위 순회로 순회, 오른쪽 서트트리 전위 순회

 - 중위순회(LPR) : 왼쪽 서브트리를 중위 순회로 순회, 루트 방문, 오른쪽 서트트리 중위 순회

 - 후위순회(LRP) : 왼쪽 서브트리를 후위 순회로 순회, 오른쪽 서트트리 후위 순회, 루트 방문

연습문제

1. 트리의 최상위 혹은 부모가 없는 노드는 무엇인가? 루트노드

2. 아래 프로그램은 어떤 트리순회인가? 전위순회 ( left -> right )

struct node *nodeptr ;

void preorder(struct node *tree_ptr) {

   if (tree_ptr) {

        printf("%d", tree_ptr->info) ;

        preorder(tree_ptr->left) ;

        preorder(tree_ptr->right) ;

   } }