Tree ADT

트리 용어 정리

• 트리는 뿌리(Root), 가지(Branch), 잎(Leaf)로 이루어짐
  > Root: 트리 자료구조 가장 위 노드
  > Branch: Root, Leaf 사이 모든 노드
  > Leaf: = terminal node 가지 끝에 달린 노드

• Parent(부모), Children(자식), 형제(Sibling)

• Path(경로): 한 노드에서 다른 노드 이르는 길 사이에 있는 노드 순서 ex) B,D,F

• Length(길이): 출발노드에서 목적지 노드까지 거쳐야 하는 Node 사이의 길 ex) B, D, F 의 Length = 2

• Depth(노드의 깊이): 뿌리 노드에서 해당 노드까지 이르는 경로 길이 (Root Node는 0)

• Level(레벨): 깊이가 같은 노드의 집합

• Height(트리의 높이): 가장 깊은 곳에 있는 잎 노드까지의 깊이

• Degree(차수)
  > 노드의 차수: 노드의 자식 노드 개수
  > 트리의 차수: 트리 내에 있는 노드들 가운데 자식이 가장 많은 노드의 차수
  

트리 표현 방법

1. 중첩된 괄호(Nested Parenthesis)
2. 중첩된 집합(Nested Set)
3. 들여쓰기(Indentation)

노드 표현 방법

1. N-Link: 노드 차수만큼 자식들을 링크
2. Left Child-Right Sibling: 자식 포인터는 자식중 가장 왼쪽 자식을 가리킴, 형제 포인터는 자신의 오른쪽에있는 형제를 가리킴 포인터를 따라가면 모든 자식을 visit 가능

• VitaminQuiz 4-1

void LCRS_PrintNodesAtLevel(LCRSNode* Root, int level)
{
	int depth = 0;
	if (level == 0)
	{
		printf("%c\n", Root->data);
	}


	if (Root->LeftChild != NULL)
	{
		LCRS_PrintNodesAtLevel(Root->LeftChild, level - 1);
	}
	if (Root->RightSibling != NULL)
	{
		LCRS_PrintNodesAtLevel(Root->RightSibling, level);
	}

	
}

이진 트리

이진 트리 용어

• 이진트리 : 하나의 노드가 자식 노드를 2개까지만 가질 수 있는 트리
• 포화 이진 트리
• 완전 이진 트리
• 높이 균형 트리
• 완전 높이 균형 트리

이진 트리 순회

• 전위 순회(Preorder) : 1. 뿌리 2. 왼쪽 하위트리 3. 오른쪽 하위트리
• 중위 순회(Inorder) 1. 왼쪽 하위트리 2. 뿌리 3. 오른쪽 하위트리
• 후위 순회 (Postorder) 1. 왼쪽 하위트리 2. 오른쪽 하위트리 3. 뿌리
  뿌리를 기준으로 전위 중위 후위 라고 생각하기

• 트리를 파괴할때는 반드시 잎 노드부터 파괴 -> 후위 순회 이용