03/31 수업내용 메모

2021/03/31

왼쪽자식 오른쪽형제 트리
부모가 가진 자식들을 알기 위해서는 부모의 왼쪽 자식노드의 오른쪽
형제노드를 찾아가야함

이진트리
.net은 이진트리, 이진 탐색 트리를 제공하지 않음
트리 중 자식노드가 2개 이하인 것(0, 1, 2)
1.사향이진트리
한쪽으로만 기운 트리
2.포화이진트리
3.완전이진트리
연결리스트 또는 배열로 이진트리 구현가능

Preorder
부모노드를 먼저 순회하고 다음 왼쪽 서브트리를, 마지막으로 오른쪽 서브트리를
순회하는 방식

배열을 이용한 이진 트리의 구현
배열에 이진트리를 저장하는 방식은 기본적으로 트리 레벨 순으로 왼쪽에서 오른쪽으로
저장, 배열 A의 A[0]에는 루드노드, A[1]에는 루트의 왼쪽 자식노드, A[2]에는
오른쪽 자식노드를 저장

??
null이 아닌 경우 왼쪽 피연산자의 값을 반환

트리순회방법
전위 순회
중위 순회
후위순회
레벨 순서 순회

반복방식으로 구현한 이진트리 순회
루트 노드를 스택에 넣음