이진 트리의 속성은 무엇인가요?
속성 1: 이진 트리의 i번째 수준(i≥1)에는 최대 2i-1개의 노드가 있습니다.
증명: 트리가 비어 있지 않다고 가정하고 수학적 귀납법으로 증명합니다.
귀납 기준: i=1일 때 전체 이진 트리에는 루트 노드가 하나만 있습니다. 이때 2i-1=20=1이라는 결론이 성립됩니다.
귀납 가설: i=k일 때 결론이 성립한다고 가정합니다. 즉, k번째 레이어의 총 노드 수는 최대 2k-1개입니다.
이제 i=k+1일 때 결론이 성립한다는 것이 증명되었습니다. 이진 트리의 각 노드의 차수는 최대 2이므로 k+1번째 레벨의 총 노드 수는 최대 k번째 레벨의 최대 노드 수의 두 배, 즉 2k-1=2입니다. (k+1)-1이므로 결론이 성립됩니다.
속성 2: 깊이가 k인 이진 트리에는 최대 2k-1개의 노드(k≥1)가 포함됩니다.
증명: 속성 1에 따르면 i번째 레이어는 최대 2i-1(1≤i≤k)개의 노드를 가지므로 깊이 k인 이진 트리의 총 노드 수는 최대 1개입니다. 221+...+2k-1= 2k-1(개).
속성 2: 임의의 이진 트리 T에 대해 터미널 노드의 수가 n0이고 차수가 2인 노드의 수가 n2이면 n0=n2+1입니다.
증명:
(1) 이진 트리의 총 노드 수를 n이라고 가정하고, n1은 이진 트리에서 1차 노드의 총 수이며, 총합은 이진 트리의 노드 수는 0차 노드와 1차 노드 더하기 2차 노드의 합과 같습니다. 따라서 n=nn1+n2입니다.
(2) 반면, 이진 트리에서는 1차 노드에는 하나의 자식이 있고, 2차 노드에는 두 개의 자식이 있으며, 루트 노드는 어떤 노드의 자식도 아닙니다. 따라서 총 노드 수는 n =n1+2n2+1입니다.
(2) 두 방정식을 빼고 정렬하면 n0=n2+1이 나오므로 결론이 성립됩니다.
속성 4: n 노드가 있는 완전한 이진 트리의 깊이는 "log2n#+1 또는 $log2(n+1)입니다. 여기서 "log2n#은 "보다 작거나 같은 정수 부분을 취함을 의미합니다." log2n#, $log2(n+1)은 log2(n+1)보다 크거나 같은 정수 부분을 취하는 것을 의미합니다.
증명: n 노드가 있는 완전한 이진 트리의 깊이가 k라고 가정합니다. 속성 2에 따르면, k-1 레벨 전이진 트리의 노드 수는 n1=2k-1-1이고, k-계층 전이진 트리의 노드 수는 n2임을 알 수 있다. =2k-1이므로 완전한 이진 트리의 노드 수 n은 n1 이후. k-1과 k는 두 개의 인접한 정수 k-1="log2n#, k="log2n#+1이므로 결론이 성립됩니다. 속성 5: n 노드가 있는 완전한 이진 트리의 경우. , 위에서 아래로, 왼쪽에서 오른쪽으로 계층적으로 번호가 지정되고, 이진 트리에서 i(1≤i≤n) 번호가 지정된 모든 노드에 대해: (1) i>1이면 일련 번호 노드 i의 부모 노드는 "i/2#입니다. i=1이면 노드 i는 루트 노드이고 부모 노드가 없습니다. (2) 2i≤n이면 노드의 왼쪽 자식의 시퀀스 번호입니다. i가 2i>n이면 노드 i에는 왼쪽 자식이 없습니다. (2) 2i+1≤n이면 노드 i의 오른쪽 자식의 시퀀스 번호는 2i+1입니다. 2i+1>n이면 노드 i에는 오른쪽 자식이 없습니다. 이 속성은 그림 6-8(b)의 예를 통해 이해할 수 있습니다. 이는 깊이가 4이고 총 12개의 노드를 갖는 완전한 이진 트리입니다. 첫 번째 항목의 경우 i=1일 때 루트 노드임이 분명합니다. 예를 들어 i>1일 때 노드 G의 시퀀스 번호는 7이고 해당 부모는 "7/2#=2입니다. 노드 I의 시퀀스 번호는 9이고 부모는 "9/2#=4입니다. 두 번째, 예를 들어 노드 H의 시퀀스 번호는 8입니다. 2?8=16이 총 노드 수인 12를 초과하므로 노드 H에는 왼쪽 자식이 없으며 리프 노드입니다. 마찬가지로 노드 F의 시퀀스 번호는 6입니다. 2?6=12가 정확히 총 노드 수 12이고 왼쪽 자식이 노드 L이기 때문입니다. Article 3, 예를 들어 노드 I의 시퀀스 번호는 9입니다. 2?9+1=19가 전체 노드 수인 12보다 크므로 오른쪽 자식이 없기 때문입니다. 노드 E의 시퀀스 번호는 5입니다. 2? 5 + 1 = 11이 12보다 작으므로 오른쪽 자식은 노드 K입니다.