1206 트리

트리란?	계층을 가지도록 데이터를 나열한 것
	트리에서는 각각의 요소를 노드라고 한다.
	노드는 데이터와 자식 노드들로 이루어져 있다.
트리의 용어
트리의 루트 노드	가장 윗부분에 있는 노드
트리의 리프 노드	사장 밑부분에 있는 노드
특정 노드의 부모	특정 노드의 상위 노드
특정 노드의 자식	특정 노드의 하위 노드
특정 노드의 형제	부모가 같은 노드
특정 노드의 조상	부모의 부모의 부모의 부모의 ....... 까지
특정 노드의 자손	자식의 자식의 자식의 자식의 ....... 까지
특정 노드의 레벨	루트로부터 얼마나 떨어져 있는가
특정 노드의 차수	자식 노드의 수
트리의 높이	루트에서 제일 먼 리프까지의 거리

이진트리	최대 차수가 2인 트리
삼진트리	최대 차수가 3인 트리
사진트리	최대 차수가 4인 트리
이진탐색트리	데이터를 저장할 때 큰 걸 오른쪽에 작은 걸 왼쪽에 저장

이진탐색트리 구현	root 제일 처음에 저장된 노드를 저장해놓는 변수
add	숫자 하나를 전달받고 반환하는 건 없는 이름이 추가인 메소드
순회
전위 순회 preOder	부모, 왼쪽 자식, 오른쪽 자식 순으로 조회
중위 순회 inOrder (BST에서 중위순회시 데이터가 정렬된다.)	왼쪽 자식, 부모, 오른쪽 자식 순으로 조회
후위 순회 postOrder (컴퓨터가 사칙연산 할 때 사용)	왼쪽 자식, 오른쪽 자식, 부모 순으로 조회

삭제
자식 노드가 없는 노드 삭제	그냥 삭제
자식이 하나인 노드 삭제	삭제하는 노드 대신에 자식 노드로 대체
자식이 두개인 노드 삭제	왼쪽을 기준으로 했을 때 삭제하는 노드 대신에 왼쪽 서브트리에서 가장 큰 노드로 대체
	오른쪽을 기준으로 했을 때   삭제하는 노드 대신에 오른쪽 서브트리에서 가장 작은 노드로 대체