ddoeun_gongdaeimo

이진트리 ADT 구현과 메쏘드 배열에 기초한 이진트리 1D 배열을 이용한 이진트리 표현 순위 i의 노드의 대해 왼쪽 자식의 위치 순위 2i, 오른쪽 자식의 위치 순위 2i+1, 부모의 위치순위 i/2 0에 관한 연산 오류를 피하기 위해 순의 0셀은 사용하지않음, 사용하지 않는 셀도 표시 널마커('#')나 널포인터 만약 MAX를 노드 순위 중 최대값이라 하면 배열크기 N = MAX로 해야함 배열크기 N = n 인 경우가 최선임 이 경우는 크기 N인 배열의 순위 0을 제외한 모든 셀이 이진트리의 노드를 표현하는 데 사용되어 기억장소의 낭비가 전혀 없는 상황 편향이진트리가 최악의 경우가 됨 연결리스트에 기초한 이진트리 연결리스트에 기초하여 이진트리 저장 각 노드는 원소, 부모노드, 왼쪽 자식노드, 오른쪽 자식..

트리 용어 노드 : 데이터 원소 간선 : 노드 사이의 부모-자식 관계를 표시 루트 : 트리 맨 위에 있는 부모가 없는 노드 내부노드(중간노드) : 적어도 한 개의 자식을 가진 노드 외부노드(잎) : 자식이 없는 노드 형제 : 같은 부모를 가진 노드들 노드의 조상 : 루트를 향해 간선을 따라 올라가면 만나게 되는 부모, 조부모, 증조부모 등의 직계 상위 노드들 노드의 자손 : 잎을 향해 간선을 따라 내려가면 만나게 되는 자식, 손주, 증손주 등의 직계 하위 노드들 부트리 : 노드와 그 노드의 자손들로 구성된 트리 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스 경로길이 : 경로 내 간선의 수 노드의 깊이 : 루트로부터 그 노드에 이르는 유일한 경로의 길이 노드의 높이 : 그 노드로부터 외부노드에 이르는..