깊이 우선 이진 심화 알고리즘을 사용하여 이진 트리 너비를 먼저 인쇄하십시오.

Question

저는 프로그래머가 아니지만 제 개인 프로젝트의 일부로 이진 트리를 인쇄 할 수있는 재귀 적 솔루션이 있는지 이해하려고합니다. 폭 우선, 레벨 순서? 반복 깊이 우선 알고리즘을 사용할 수 있다는 것을 알고 있습니까? 다음 이진 트리를 들어

#Helper method 
def getChildren(node): 
    children=[] 
    hasLeft = node.left is not None 
    hasRight = node.right is not None 
    if not hasLeft and not hasRight: 
     return [] 
    if hasLeft: 
     children.append(node.left) 
    if hasRight: 
     children.append(node.right) 
    return children 

def DLS(node, depth): 
    """Depth Limited Search""" 
    if (depth == 0): 
     return node 
    elif (depth > 0): 
     print node.value, 
     children = getChildren(node) 
     for child in children: 
      DLS(child, depth-1) 
    else: 
     return False 

: (1)3 (2)2 (4)1 (8)1 (9)0 (5)1 (3)1 (6)1 (7)0 None

첫 번째 레벨 순서 만 예약 주문 깊이되지 않습니다 : 나는이 통과 출력을 얻고있다
(1)3
(2)2 (3)1
(4)1 (5)1 (6)1 (7)0
(8)1 (9)0

.

DLS 함수의 깊이를 반복해야합니까? 어떻게 이진 트리의 레벨 순서 출력을 구현할 수 있습니까?

많은 감사 알렉스 데이터 구조의 관점에서

Answer 1

는, 깊이 우선 및 폭 우선 차이는 그 깊이 우선 스택을 사용하고, 폭은 최초의 큐를 이용한다.

깊이 우선, 아이디어는 "당신이 처리 한 마지막 결과의 처리"입니다. 따라서 스택을 사용하면 푸시 된 마지막 노드가 항상 튀어 나오고 올바른 동작을 얻을 수 있습니다.

우선적으로, 아이디어는 "선택한 노드의 모든 결과를 먼저 처리 한 다음 계속 진행하십시오"라는 개념입니다. 그래서 결과를 먼저 알아 내고 저장하십시오. 그런 다음에야 발견 한 순서대로 처리 할 수 ​​있습니다. 이를 지원하는 가장 간단한 데이터 구조는 대기열입니다.

재귀는 스택 (호출 스택)을 사용한다는 점에서 문제가 있습니다. 그래서 당신은 데이터 구조를 보지 못했지만 실제로는 거기에 있습니다. 호출을 대기시키는 (단순한) 방법이 없으므로 명시 적 대기열을 사용하지 않고 너비 우선 탐색을 코드로 변환 할 수 없습니다.

너비 우선 구현에 대한 정보가 필요하면 Wikipedia을 확인해 보는 것이 좋습니다.