데이터 구조 제4 장 나무 - 나무의 기본 개념 과 기본 용어 및 이 진 트 리 의 기본 개념

데이터 구조의 세 가지 전형 적 인 조작: (1) 삽입;(2) 삭제;(3) 찾기.데이터 구조의 기본 동작 중 하나: 찾기: (1) 정적 찾기: 집합 에 기록 되 어 있 는 것 은 고정 적 이 고 삽입 과 삭제 등 작업 이 없 으 며 찾기 동작 만 있 습 니 다.(2) 동적 검색: 집합 에 기 록 된 것 은 동적 이 고 삽입, 삭제, 찾기 등 이 있 습 니 다.
정적 질서 찾기 는 2 분 찾기 알고리즘 을 사용 할 수 있 습 니 다 (C 언어 는 다음 과 같 습 니 다).

int binary_search( ElementType a[], ElementType x, int n )
{
	int low = 0, mid, high = n - 1;
	while( low <= high ){
		mid = ( low + high ) / 2;
		if( a[mid] == x )
			return mid;
		else if( a[mid] > x )
			high = mid - 1;
		else
			low = mid + 1;
	}
	return 0;
}

나무의 정의: 나무 (Tree) 는 n (n > = 0) 개의 노드 로 구 성 된 유한 집합 입 니 다. n = 0 시 에 빈 나무 라 고 부 릅 니 다. 비 빈 나무의 특징 은 다음 과 같 습 니 다. (1) 있 고 하나의 노드 (root) r 만 있 습 니 다.(2) n > 1 시 나머지 결점 은 m (m > 0) 개의 서로 교차 하지 않 는 유한 집합 으로 나 눌 수 있 는데 그 중에서 각 집합 자 체 는 또 하나의 나무 로 원래 나무의 자나무 (Subtree) 라 고 부른다.
나무의 정 의 는 재 귀 적 이 고 재 귀 적 인 데이터 구조 로 분 층 구조 로 분 층 조직 은 관리 에 있어 더욱 높 은 효율 을 가진다.
나무의 일부 특징 (나무 와 비 나 무 를 판단 하 는 근거): (1) 나무의 뿌리 결점 은 전구 결점 이 없고 다른 결점 은 있 으 며 전구 결점 만 있다.(2) 각 결점 마다 0 개 이상 의 후계 결점 이 있 을 수 있다.(3) 자 수 는 서로 교차 하지 않 는 다.(4) n 개의 결점 이 있 는 나 무 는 n - 1 개의 변 이 있다.
기본 용어: (1) 결점 의 도 (Degree): 결점 의 하위 트 리 개수 (결점 이 아래 에 연 결 된 개수);(2) 나무의 도: 나무의 모든 결점 중 가장 큰 도;(3) 엽 결점 (단말기 결점) (Leaf): 도 0 의 결점;(4) 아버지 결점 (부모 결점) (Parent): 아들 나무의 결점 은 아들 나무 뿌리 결점 의 아버지 결점 이다.(5) 자 결점 (아이 결점) (Child): 아버지 결점 이 있 는 노드 는 아버지 결점 의 자 결점 이다.(6) 형제 결점 (Silbing): 같은 아버지 결점 을 가 진 각 노드 는 서로 형제 결점 이다.(7) 경로 와 경로 길이: 한 결점 에서 다른 결점 까지 의 경 로 는 하나의 결점 서열 이 고 경로 에 포 함 된 변 의 개 수 를 경로 의 길이 라 고 한다.(8) 조상 결점 (Ancestor): 나무 뿌리 를 따라 특정한 결점 까지 의 모든 결점 은 이 결점 의 조상 결점 이다.(9) 자손 결점 (Descendant) 의 어떤 결점 나무 중의 모든 결점 은 이 결점 의 자손 결점 이다.(10) 노드 의 차원 (Level): 뿌리 노드 를 1 층 에 규정 하고 다른 모든 노드 의 차원 은 이 노드 의 부모 노드 차원 + 1 (위 에서 아래로 층 을 누적) 이다.(11) 나무의 깊이 (Depth): 나무의 결점 중 가장 큰 층 차 는 이 나무의 깊이 이다.(12) 분지 결점: 도가 0 보다 큰 결점 을 분지 결점 이 라 고 한다.(13) 나무의 높이: 나무 에 있 는 결점 의 최대 층수 (바닥 에서 위로 층 층 이 누적);(14) 질서 있 는 나무 와 무질서 한 나무: 나무 에 점 이 있 는 서브 나무의 좌우 서브 나 무 는 순서 가 있 으 면 교환 할 수 없 는 나 무 를 질서 있 는 나무 라 고 부 르 고 그렇지 않 으 면 무질서 한 나무 라 고 부른다.(15) 숲: 숲 은 m (m > = 0) 그루 가 서로 교차 하지 않 는 나무의 결합 이다.
나무의 성질: (1) 나무의 결점 수 는 모든 결점 의 도수 에 1 을 더 하 는 것 과 같다.(2) 도 m 인 나무 중 i 층 은 m ^ (i - 1) 개의 결점 (i > = 1) (도 m 인 나무 중 i 층 의 결점 이 가장 많은 수량 은 만 m 진 나무 i 층 의 결점 수량 과 같다).(3) 높이 가 h 인 m 포크 트 리 는 기껏해야 (m ^ h - 1) / (m - 1) 개의 결점 (최대 상황 은 만 이 포크 트 리 에 대응 하고 계산 방법 은 등비 수열 구 화) 이 있다.(4) n 개의 결점 을 가 진 m 포크 트 리 의 최소 높이 를 계산 할 때 대응 하 는 완전 m 포크 트 리 (또는 만 m 포크 트 리) 의 상황 (즉, 높이 를 h 로 설정 하면 (m ^ h - 1) / (m - 1) = n, 계 산 된 h 아래로 추출) 을 고려 합 니 다.
이 진 트 리: 유형 이름: 이 진 트 리 (비어 있 을 수 있 습 니 다. 비어 있 지 않 으 면 뿌리 노드 와 교차 하지 않 는 왼쪽 나무, 오른쪽 나무 로 구성 되 어 있 습 니 다). 그 특징 은 모든 노드 에 두 개의 서브 트 리 (즉 이 진 트 리 중 결점 의 최대 도 는 2) 가 있 고 이 진 트 리 는 질서 있 는 나무 입 니 다.데이터 대상 집합: 가난 한 결점 집합작업 집합:

int IsEmpty( BT ptrt );                 //          
BT CreateBinTree();                     //       
void Traversal( BT ptrt );              //           

두 갈래 나무 와 두 갈래 나무의 차이: (1) 두 갈래 나 무 는 질서 있 는 나무 이다.(2) 이 진 트 리 는 비어 있 을 수 있다.
몇 개의 특수 한 이 진 트 리: (1) 이 진 트 리 (Full Binary Tree) (완벽 한 이 진 트 리 (Perfect Binary Tree): 나무의 층 마다 가장 많은 결점 이 있 습 니 다. (2) 완전 이 진 트 리 (Complete Binary Tree): 위 에서 아래로, 왼쪽 에서 오른쪽으로, 모든 결점 의 번 호 는 이 진 트 리 의 번호 와 같 습 니 다. (마지막 층 오른쪽 결점 이 없어 도 됩 니 다)두 갈래 정렬 트 리 (두 갈래 검색 트 리): 뒷부분 상세 설명, (4) 균형 두 갈래 트 리: 뒷부분 상세 설명.
이 진 트 리 의 성질: (1) 비 공 이 진 트 리 의 잎 결 점 수 는 2 의 결 점 수 에 1, 즉 n0 = n2 + 1 (이전 나무의 성질 에 따라 나무의 결 점 수 는 모든 결 점 의 도수 에 1 을 더 하여 n0 + n1 + n2 = n1 + n2 * 2 + 1 을 얻어 이 등식 을 얻 을 수 있다). (2) 비 공 이 진 트 리 의 k 층 은 최대 2 ^ (k - 1) 개의 결 점 이 있다. (3)높이 가 h 인 이 진 트 리 에는 최대 2 ^ h - 1 개의 결점 (이 진 트 리 에 대응) 이 있 습 니 다. (4) 완전 이 진 트 리 에 대해 결점 번호 가 i 인 부모 결점 번 호 는 [i / 2] 이 고 왼쪽 아이 가 있 으 면 왼쪽 아이 번 호 는 2 * i 이 며 오른쪽 아이 가 있 으 면 오른쪽 아이 번 호 는 2 * i + 1 입 니 다. (5)완전 이 진 트 리 의 높이 를 계산 할 때 성질 3 을 이용 하여 n + 1 을 대 수 를 취한 후 아래로 조정 합 니 다.