면접 문제 집계 - 데이터 구조 부분 (지속 업데이트)

823 단어
1. 완전 이 진 트 리 의 성질
면접 문제: 완전 이 진 트 리 의 결산 점 이 768 개 라면 잎 결산 점 의 개 수 를 구 합 니 다.
이 진 트 리 의 성질 로 알 수 있 듯 이 n0 = n2 + 1, 이 를 768 = n0 + n1 + n2 에 가 져 가면 768 = n1 + 2n2 + 1, 완전 이 진 트 리 가 1 인 결점 개수 가 0 이거 나 1 이기 때문에 n1 = 0 또는 1 을 모두 공식 에 대 입 하면 n1 = 1 이 조건 에 부합 하 는 것 을 쉽게 발견 할 수 있다.그래서 n2 = 383 을 계산 해 냈 기 때문에 잎 결점 개수 n0 = n2 + 1 = 384.
총 결 규칙: 만약 에 한 그루 의 완전 이 진 트 리 의 결산 점 이 n 이 라면 잎 결산 점 은 n / 2 (n 이 짝수 일 때) 또는 (n + 1) / 2 (n 이 홀수 일 때) 와 같다.
        T, n0         、n2     2         ,        n0 = n2 + 1。

        ,        。

  :  ,       N    ,          ?   N - 1,         ,                 ,   N           N - 1   。         ,     (       )   ,             0*n0 + 1*n1 + 2*n2       。

  ,      N - 1 = n1 + 2*n2, N  n0 + n1 + n2   ,  n0 + n1 + n2 - 1 = n1 + 2*n2,   

    n0 = n2 + 1。    。

좋은 웹페이지 즐겨찾기