숙제 : 이진 트리 - 레벨 순서 전환

Question

저수준에서 상위 (루트)로 이진 트리를 방문하는 방법은 무엇입니까?

루트 수준에서 가장 낮은 수준까지! (레벨 순서 탐색 및 스택을 사용하지 ...!)

<는 --- 그 반대 ..

너무 어렵습니다 ... 감사합니다!

Answer 1

제공된 질문 : 올바르게 잎을 먼저 가로 지르고 루트를 마지막으로 탐색하려는 경우 트리를 가로 질러 돌아 오는 길에 노드를 방문 할 수 있습니다.

function traverse(node) 
    for each child of node 
     traverse(child) 
    end 
    visit(node) 
end 

당신이 레벨 순서로 노드를 방문하려면, 다음과 같이 (스택을 사용하지만 할 수 - 난 당신이 사용하는 모든 하나 또는 어떤 특정 솔루션을 원하지 않았다 여부를 확실하지 않다 스택) :

for i = treedepth down to 0 
    queue.push(root) 
    while queue is not empty 
     node = queue.pop() 
     if node has depth i 
      visit(node) 
     else 
      for each child of node 
       queue.push(child) 
      end 
     end 
    end 
end 

나무를 : 당신이 이런 식으로 할 경우

queue.push(root) 
while queue is not empty 
    node = queue.pop() 
    for each child of node 
     queue.push(child) 
     stack.push(child) 
    end 
end 
while stack is not empty 
    visit(stack.pop()) 
end 

당신은,하지만 더 시간 복잡도와 만 큐를 사용하여 작업을 수행 할 수 있습니다 깊이 및 노드 레벨은 필요한 경우 초기 통과를 사용하여 찾을 수 있습니다.

그러나 재귀 호출을 허용하면 실제로 스택 (호출 스택)에 액세스 할 수 있습니다. 이것은 두 번째 솔루션을 구현하기 위해 악용 될 수 있지만 스택을 암시 적으로 만듭니다. 거의 모든 다른 데이터 구조 (목록, 배열, 우선 순위 큐, 덱 등)에 액세스 할 수있는 경우

function unwind(queue) 
    if queue is not empty 
     node = queue.pop() 
     unwind(queue) 
     visit(node) 
    end 
end 

queue.push(root) 
while queue is not empty 
    node = queue.pop() 
    for each child of node 
     queue.push(child) 
     queue2.push(child) 
    end 
end 

unwind(queue2) 

그리고 물론

, 당신은 쉽게 스택을 직접 구현할 수 있습니다. 그러나 우선 스택을 금지하는 것이 무의미 할 것입니다.

Answer 2

아마도 쉽게 할 수 있습니다. IF 당신은 가장 깊은 곳에서 노드에 대한 포인터를 유지 관리했습니다. 그렇지 않으면 탐색을 시작하기 전에 해당 노드를 찾아야합니다. 또한 노드에는 모두 부모에 대한 포인터가 있어야합니다.

Answer 3

다른 솔루션으로 이어질 여기에 몇 가지 문제가있다 :

1. 당신이 나무를 통과 할 수 있습니까? 종종 데이터 구조가 설정되어 사용자가 이동할 수 있습니다. 모든 리프 노드를 찾아 레벨별로 우선 순위 대기열에 넣은 다음 위로 이동합니다.

2. O (추가) 데이터를 저장할 수 있습니까? 이전의 솔루션 에서처럼 레벨별로 우선 순위 대기열에 포인터를 삽입하는 일반적인 폭 우선 방식으로 트래버스 할 수 있지만 이번에는 처음 통과하는 동안 모든 노드를 삽입합니다. 이것은 트래버스 중에 사용되는 보조 데이터의 최대 크기를 증가시킵니다.

3. 나무가 힙 같은 나무처럼 균형 잡혀 있고 가득 차 있는지 보장 받습니까? 그렇다면 올바른 장소로 이동하여 더 간단한 방식으로 트래버스 할 수 있습니다.

Answer 4

더 나은 방법으로 설명합니다.대수 표현 트리가 있습니다 (균형이 맞지 않습니다). 큐를 사용하여 그것을 평가해야합니다 (및 큐만). 트리 (+ (* (2) (2)) (3))

: 나는 유일한 방법은 루트까지, 가장 낮은 수준에서 시작 노드를 취할 생각 때문에 ...

예를 들어이 질문을

대기열에 걸리고 다음과 같습니다.

enqueue (1); enqueue (2);

(*) ----- dequeue; 디큐; 결과 = 2 * 2; enqueue (결과); 큐 삽입 3; (+) -----> dequeue; 디큐; 결과 = 4 + 3; 결과를 내라.

그래서이 트래버스가 필요합니다. 2; 2; *; 삼 ; +

내가 분명히인지 잘 모릅니다

...

Answer 5

대기열이 나무의 잎에 뿌리에서 레벨 순서를 통과하는 경우에만 유용합니다.

특정 레벨 인쇄에는 우선 우선 순회를 사용할 수 있습니다. 이처럼 :

void printLevel(BinaryTree *p, int level) { 
    if (!p) return; 
    if (level == 1) { 
    cout << p->data << " "; 
    } else { 
    printLevel(p->left, level-1); 
    printLevel(p->right, level-1); 
    } 
} 

는 루트에 잎까지의 모든 레벨을 인쇄하려면, 당신은 트리의 최대 깊이를 찾을 필요가있다. 이것은 depth-first traversal을 사용하여 쉽게 수행 할 수 있습니다 (솔루션을 쉽게 찾을 수 있습니다).

void printLevelOrder(BinaryTree *root) { 
    int height = maxHeight(root); 
    for (int level = height; level >= 1; level--) { 
    printLevel(root, level); 
    cout << endl; 
    } 
} 

놀랍게도 런타임 복잡도는 O (N)입니다. 여기서 N은 노드의 총 수입니다.

더 많은 정보와 실행 시간 복잡도 분석은 아래 페이지를 참조 해주십시오 : 그것은 균형 트리

http://www.ihas1337code.com/2010/09/binary-tree-level-order-traversal-using_17.html