입력에서 힙 (heap)으로 주어진 이진 트리에서 노드의 좌표를 찾는 방법은 무엇입니까? 같은 입력으로 힙을 감안할 때

Question

, '-'

1 2 3 - 5 - 7 

빈 노드를 나타내며, 나는 노드의 좌표를 찾으려 BE 위의 입력을위한 것 :

[1, 0] [0, 2] [2, 2] [-1, -1] [1, 4] [-1, -1] [3, 4] 

위한

규칙 변환 좌표는 다음과 같다 : 트리의 각각의 "층"들 사이의 공간

• 이 있어야 1 행, 우리는 각각의 계층 2와 Y 값을 증가 의미한다.
• 왼쪽 노드의 X 좌표 = 0이어야합니다.
• 각 노드 사이에는 적어도 하나의 공백이 있어야합니다.
• 모든 좌표는 정수 여야합니다.
• 루트 노드에 두 개의 자식이있는 경우 루트는 두 개의 자식이 중간에 있어야합니다.
• 루트 노드에 자식이 하나만있는 경우 루트의 왼쪽 또는 오른쪽 자식에 따라 루트의 왼쪽 또는 오른쪽 중 하나에 자식을 배치해야합니다.
• 루트 노드에 두 개의 하위 트리가있는 경우 오른쪽 하위 트리의 노드에 대한 모든 x 좌표가 왼쪽 하위 트리의 노드에 대한 x 좌표보다 커야합니다.
• 빈 노드의 좌표는 [-1 , -1]

나는이 문제를 해결할 수있는 방법을 찾아 낼 수 없으므로 도움을 주시면 감사하겠습니다.

Answer 1

힙을 보면 각 수준의 노드 수가 이전 수준의 두 배인 것을 알 수 있습니다. 그래서 당신은 1, 2, 4, 8, 16 등으로 진행합니다.

입력 배열에서 노드의 인덱스를 감안할 때, 인덱스의 2 진 로그와 반올림을 사용하여 쉽게 레벨을 결정할 수 있습니다 하위. 우리는 1 기반 색인을 사용하는 경우 그 다음입니다 : 2로

log2(1) = 0 
log2(2) = 1 
log2(3) = 1 
log2(4) = 2 
log2(5) = 2 
log2(6) = 2 
log2(7) = 2 

곱하기 그 값은 Y 좌표를 얻을 수 있습니다. 당신이 인덱스를 가지고 그 위의 모든 단계에서 발생하는 노드의 수를 뺄 경우 X 좌표

는, 당신은 해당 행에 해당 항목 의 인덱스를 가지고있다. 목록에있는 네 번째 (1 기반) 항목을 고려하십시오. 당신은 레벨 2에 있다는 것을 압니다. 그 전에 오는 노드의 수는 (2^2)-1, 또는 3입니다. 그리고 4-3 = 1입니다. 따라서 목록의 네 번째 항목은 해당 수준의 색인 1에 있습니다.

귀하의 질문에 어떻게 행 인덱스를 변환 하려는지 확실하지 않습니다. 마지막 행에서 모든 항목에 값이있는 경우 X 좌표는 0, 1, 2, 3이됩니다. 이것이 각 행을 수행하는 방법 인 경우 이전 단락에서 설명한 계산에서 1을 뺍니다.