이진 트리가 레벨 순서로 채워진 경우 선주문 순회 배열을 레벨 순회 배열로 변환 (또는 그 반대로)

Question

레벨 순서로 채워진 이진 트리가 있다고 가정합니다. 즉, 모든 레벨은 그 레벨의 노드의 자식. 이러한 트리는 레벨 순회에 의해 고유하게 정의 될 수 있습니다. 예를 들어 {1,2,3,4,5,6}는 {1,2,4,5,3,6}

인가 이것의 전순 주사 배열을 생산하는 것

1 
2  3 
4 5 6 

입니다 이 배열 중 하나를 다른 배열로 직접 변환하는 방법은 실제 트리를 생성하고 실제 트리를 수행하는 것보다 빠릅니다. (노드가 n 인 트리의 경우)

Answer 1

네, 모두 단일 패스로 가능합니다.

첫째로, 미리 주문하는 것이 좋습니다. 조금 더 쉽기 때문입니다. 이것은 레벨이 채워진 트리이므로 배열의 모든 노드에 대해 인덱스가 i 인 경우 왼쪽 하위 트리 노드의 인덱스에 대한 수식은 2*i+1이고 오른쪽에 대해서는 2*i+2입니다. 그래서 우리는 선 주문으로 재귀 적으로 호출하고 원하는 배열의 뒤에 루트 노드를 추가합니다.

def level_to_pre(arr,ind,new_arr): 
    if ind>=len(arr): return new_arr #nodes at ind don't exist 
    new_arr.append(arr[ind]) #append to back of the array 
    new_arr = level_to_pre(arr,ind*2+1,new_arr) #recursive call to left 
    new_arr = level_to_pre(arr,ind*2+2,new_arr) #recursive call to right 
    return new_arr 

이렇게하면 마지막 빈 배열이 채워집니다.

ans = level_to_pre([1,2,3,4,5,6],0,[]) 

이제 레벨 이전 단계로 이동하기 전에 dfs가 장면 뒤의 스택을 사용하는 재귀를 사용한다는 점을 기억하십시오. bfs가 queue를 사용하는 곳. 그리고 우리의 손에있는 문제, 배열을 레벨 우선으로 채우는 것은 기본적으로 bfs입니다. 따라서 재귀 호출 (예 : 스택) 대신 재귀 호출을 에뮬레이트하기 위해 명시 적으로 대기열을 유지 관리해야합니다.

우리가 여기서하는 것은 서브 트리의 루트가 주어지면 먼저 배열에 응답하도록 추가하는 것입니다. 이제 위의 문제와 달리 하위 노드의 색인을 찾는 것이 쉽지 않습니다. 왼쪽 하나는 쉬우 며, 곧 루트가됩니다. 오른쪽의 인덱스를 찾으려면 왼쪽 하위 트리의 전체 크기를 계산합니다. 레벨이 채워 졌기 때문에 가능합니다. 우리는 이제 전체 트리의 크기가 주어진 왼쪽 하위 트리의 크기를 반환하는 도우 함수 left_tree_size(n)을 사용합니다. 따라서 루트의 인덱스를 제외하고 재귀의 경우 전달할 두 번째 매개 변수는이 하위 트리의 크기입니다. 이를 반영하기 위해 큐에 (루트, 크기) 튜플을 넣습니다.

from math import log2 
import queue 

def pre_to_level(arr): 
    que = queue.Queue() 
    que.put((0,len(arr))) 
    ans = [] #this will be answer 
    while not que.empty(): 
     iroot,size = que.get() #index of root and size of subtree 
     if iroot>=len(arr) or size==0: continue ##nodes at iroot don't exist 
     else : ans.append(arr[iroot]) #append to back of output array 
     sz_of_left = left_tree_size(size) 
     que.put((iroot+1,sz_of_left)) #insert left sub-tree info to que 
     que.put((iroot+1+sz_of_left,size-sz_of_left-1)) #right sub-tree info 

    return ans 

마지막으로 여기에 도우미 기능이 있으며, 몇 가지 예를 따라 작동하는 이유를 알아보십시오. 이 또는 어떤 대답은 귀하의 질문에 체크 표시를 클릭하여 수용 고려하시기 바랍니다 해결 한 경우

def left_tree_size(n): 
    if n<=1: return 0 
    l = int(log2(n+1)) #l = no of completely filled levels 
    ans = 2**(l-1) 
    last_level_nodes = min(n-2**l+1,ans) 
    return ans + last_level_nodes -1