자바 필기시험 문제 흔한 지식점: 나무 관련 지식점(주로 두 갈래 나무)

소제목

나무와 두 갈래 나무의 전환, 삼림과 두 갈래 나무의 전환: 나무 선서 <=> 두 갈래 나무 선서 나무 후서 <=> 두 갈래 나무 중서 삼림 선서 <=> 두 갈래 나무 선서 삼림 중서 <=> 두 갈래 나무 중서

이차수 성질: (1) 이차수 i층의 결점수<=2^(i-1)(2) 이차수 깊이는 k, 총결점수<=2^k-1(3) 이차수 잎수는 n0, 도 2의 결점수는 n2이면 n0=n2+1(4) 총결점수는 n의 완전 이차수 깊이는logn"+ 1그루의 일반 이차수 깊이 범위는 [logn'+1,n]이다

헤프만 나무(최우수 두 갈래 나무): 주어진 권한 집합에 따라 헤프만 나무를 구성하고 권한 경로 길이 결점의 권한 경로 길이 정의를 구한다. 이 결점에서 나무 뿌리 사이의 경로 길이와 결점의 권한 값을 곱한 나무의 권한 경로 길이 정의: 나무에 잎사귀 결점이 있는 권한 경로 길이와 헤프만 나무(최우수 두 갈래 나무) 정의: 권한 경로 길이가 가장 작은 두 갈래 나무

헤프만 나무는 도수가 1인 결점이 없고 구조할 때 최대한 만족한다. 권치가 클수록 뿌리 결점과 가깝다(보통 밑바닥부터 구조하기 시작하는데 가장 작은 두 권치를 먼저 찾아라...) 예제: 데이터 집합 {1,6,8,2,9,4}를 권치로 한 그루의 헤프만 나무를 구성하는데 그 권경로의 길이는?

                   30
       13                         17
   6         7                8        9            
          3      4                             
        1   2                                     

  length =  (6 + 8 + 9) * 2 + 4 * 3 + (1 + 2) * 4

두 갈래 정렬 트리의 평균 찾기 길이: 줄로 보면 다음과 같은 그림에서 첫 번째 줄에는 원소가 하나 있고 두 번째 줄에는 원소가 2개 있고 세 번째 줄에는 원소가 3개 있다

            45
     24           53
 12     37            93

ASL=(11+22+3*3)/6=7/3

이미 알고 있는 서열(50,30,80,20,40,90,35,85,32,88)을 순서대로 삽입하는 방법에 따라 두 갈래 서열 트리를 생성하면 이 트리에서 키워드 값이 35인 결점을 찾는 데 필요한 비교 횟수는?정답은 4.순서대로 두 갈래 정렬 트리를 구성한 후 목표 요소가 트리에 있는 위치를 찾으면 트리의 몇 번째 층(1부터 계산)에 있고 이 요소를 찾으려면 몇 번을 비교해야 한다

붉은색 검은 나무의 성질(1)은 균형 정렬 두 갈래 나무(2)의 뿌리 결점은 검은색이고 잎 노드는 모두 검은색(3)이다. 하나의 결점은 빨간색이고 그 자결점은 모두 검은색이다. (4) 어떤 결점에서 각 잎 결점까지의 모든 경로는 같은 수의 검은색 결점을 포함한다

알고리즘 문제

위에서 아래로 두 갈래 나무를 인쇄하다https://blog.csdn.net/chao_ji_cai/article/details/96128153두 갈래 나무를 여러 줄로 인쇄하다https://blog.csdn.net/chao_ji_cai/article/details/97386193서열화 두 갈래 나무https://blog.csdn.net/chao_ji_cai/article/details/97210961두 갈래 나무의 다음 결점https://blog.csdn.net/chao_ji_cai/article/details/97203142두 갈래 나무의 거울https://blog.csdn.net/chao_ji_cai/article/details/96105310대칭적인 두 갈래 나무https://blog.csdn.net/chao_ji_cai/article/details/96864345평형 두 갈래 나무https://blog.csdn.net/chao_ji_cai/article/details/96570545두 갈래 나무의 깊이https://blog.csdn.net/chao_ji_cai/article/details/96568282두 갈래 트리 중 하나가 되는 경로https://blog.csdn.net/chao_ji_cai/article/details/96293729두 갈래 나무를 재건하다https://blog.csdn.net/chao_ji_cai/article/details/95938896
두 갈래 검색 트리의 k 번째 결점https://blog.csdn.net/chao_ji_cai/article/details/97206963두 갈래 검색 트리와 양방향 체인 테이블https://blog.csdn.net/chao_ji_cai/article/details/96425068두 갈래 검색 트리의 뒷차례 반복 시퀀스https://blog.csdn.net/chao_ji_cai/article/details/96271541나무의 하위 구조https://blog.csdn.net/chao_ji_cai/article/details/96101454