04/01 수업내용 메모

2021/04/01

힙 자료구조가 완전이진트리에 해당

배열로 이진트리
레벨 순으로 왼쪽에서 오른쪽으로 저장
A[0]는 루트노드

왼쪽추가(부모인덱스, 데이터)
왼쪽노드 계산 : (부모인덱스 * 2) + 1
계산한 인덱스에 데이터 추가

오른쪽추가(부모인덱스, 데이터)
오른쪽노드 계산 : (부모인덱스 * 2) + 1
계산한 인덱스에 데이터 추가

트리 순회
전위, 중위, 후위, 레벨

반복문 전위순회
루트 노드를 스택에 넣음
스택이 빌때까지 루프를 돌음
 스택에서 pop하여 노드 출력
 오른쪽 노드가 있으면 스택에 저장
 왼쪽 노드가 있으면 스택에 저장

반복문 중위순회
1
루트 노드에서 최좌측 노드까지 스택에 저장
스택이 빌때까지 루프를 돌음
 스택에서 pop하여 노드를 출력
 오른쪽 노드가 있으면 오른쪽 노드부터 오른쪽 서브트리의 최좌측노드까지 스택에 저장

2
//스택 만든다

            //변수에 루트 넣는다

            //변수에 노드가 있거나 스택에 요소가 있다면 반복

                //변수에 노드가 있다면 반복

                    //변수의 노드를 스택에 넣는다

                    //변수에 노드의 왼쪽 노드를 넣는다.

                //스택에서 꺼냄

                //출력

                //변수에 오른쪽 노드를 넣는다 (스택에 오른쪽에 있는 서브루트에서 최좌즉까지 넣기 위함)


반복문 후위순회
루트 노드에서 최좌측노드까지 오른쪽 자식노드와 루트노드를 스택에 저장
스택이 빌 때까지 루프
 스택에서 pop하여 변수 n에 저장, n의 오른쪽 노드가 스택의 top과 동일한지 체크
 동일하지 않으면 변수 n 출력
 동일하다면 스택의 top에 있는 오른쪽 노드를 pop하고 기존 루트(변수n)를 다시 스택에 push


이진 탐색 트리
왼쪽노드의 값이 루트 노드의 값보다 작고, 오른쪽 노드의 값이 루트노드의 값조다 큰 값을 갖음
이러한 값 순서는 이진 탐색 트리의 모든 서브트리에 적용
모든 노드의 키가 유일하다는 정의를 포함시키는 것이 일반적
주로중위순회방식
노드 클래스를 사용
루트 노드를 내부 private 필드로 가짐
이진탐색트리의 추가 메서드(Add)
먼저 루트 노드로부터 키를 비교하여 좌, 우 노드로 계속 이동해 내려가면서 새키를 추가할 장소를 찾음

이진 탐색 트리의 탐색 메서드(search)

이진 탐색 트리의 삭제 메서드(remove)
삭제할 때 삭제할 노드가 자식 노드를 가지고 있을 수 있기 때문에 어려움
0개 부모 노드에서 삭제할 노드의 링크를 null
찾은경우, 못찾은 경우