고정 크기의 이진 트리 만들기

Question

이진 트리를 만들려고합니다. 내가받은 유일한 것은 트리의 노드 수입니다. 내 머리에 첫 번째로 들려오는 것은 전체 노드 수를 추적하기 위해 인덱스 (BFS order)를 사용하고 재귀 적 정의를 사용하는 것입니다. 여기에 내 의사 코드가 있습니다.

N = 10   //binary tree total node count 
i = 0   //global integer 
function() 
    if i > N 
     return True 

    create node i 
    i = i + 1 
    function(i) //left 
    i = i + 1 
    function(i) //right 

나는 나를 어쩌면 내가 재귀 규칙을 위반하고 같은 느낌이 정의에 전역 변수를 사용해야합니다. 내가하는 일을하는 더 좋은 방법이 있을까요? 이것이 방법 일 텐데, 개선 될 수 있습니까?

참고 : 나는 코드가 아니라 이론적 인 방법에 대해 묻습니다.

편집 :이 메서드는 실패했습니다. 나는 제안을 위해 열려 있습니다.

명확화 :이 트리에 대한 요구 사항은 이전 심도가 노드로 채워지지 않은 경우 (모든 노드에 2 개의 자식이 있음), 이전에이를 언급하지 않은 것을 용서해주십시오. 내가 언급 한 스택은 질문과는 아무런 상관이 없습니다. 나무를 반복적으로 통과하는 일반적인 방법 일뿐입니다. 재귀 적으로 정의 된 경우

Answer 1

나무는 세 가지 요소로 구성

• 루트 노드
• 나무 자체

는 나무 자체

오른쪽 하위 트리가있는 왼쪽 서브 트리,

이 모두는 NULL 일 수 있습니다.

이제 우리는 다음과 같은 방식으로 나무로 범위 [a, b]의 숫자를 배포 할 수 있습니다 :

는

• 루트 (a + b)/2
• 왼쪽 서브 트리를 재귀 적
• 바로 하위 트리의 구축 범위 [a, (a + b)/2 - 1]의 내장 포함 범위 [(a + b)/2 + 1, b] 재귀 적으로

끝이 시작보다 높은 범위는 consi 일 수 있습니다 비어있는 것으로 간주하여 노드가 NULL이됩니다. 이 배포는 좌우 하위 트리의 크기가 1 씩 다르며 다른 레벨이 채워지기 전에 각 레벨이 완전히 채워지도록합니다.

예컨대 :이 알고리즘은 BST를 (실제로는 기본적으로 이진 검색의 "역") 빌드 또한

N = 6 
            [0, 5] 

       [0, 1]    2     [3, 5] 

     [0]  1  []    [3]   4   [5] 

[]  0  []      []  3  []  [] 5 [] 

.이제 알고리즘 자체에 대한 :

function(a, b): 
    if b < a: return NULL 

    n = create node (a + b)/2 
    n.left = function(a, (a + b)/2 - 1) 
    n.right = function((a + b)/2 + 1, b) 

    return n 

트리를 호출하여 생성 할 수 있습니다 :

function(1, N) 

가 또는 다른 매개 변수 a 및 b 작동합니다, a + N - 1 = b 보유 곳. 두 매개 변수는 트리에서 보유해야하는 범위 (둘 모두 포함)를 나타냅니다.