주어진 이진 트리의 한 레벨에 모든 요소 인쇄

이진 트리의 단일 레벨에서 노드를 인쇄 (방문)해야합니다.
이 작업을 수행하는 방법을 알 수는 없지만 일반적으로 알고리즘에 익숙하지는 않습니다.
난폭 한 우선 탐색에서 당신은 큐를 사용하고 큐에 루트 노드를 놓은 다음 시작하여 큐에서 큐를 대기열에 넣고 큐에 넣은 다음 첫 번째 엔큐 된 자식을 큐에서 빼내어 큐에 넣습니다. 등등 ...
그리고 내 이해에 의해 정확히 한 수준이 끝나고 다른 노드가 시작될 때마다이 노드를 할당하지 않으면 이진 트리가 만들어 질 때 수준을 정확하게 파악할 수 없게됩니다. 폭스 퍼스트 트래버 설.주어진 이진 트리의 한 레벨에 모든 요소 인쇄

이 코드는 PHP에 있지만 PHP 관련 질문이 아니며 일반적인 알고리즘 관련 질문입니다. 이것은 노드에 레벨을 저장하는 이진 트리에 노드를 추가하는 함수의 일부입니다. 각 노드는) 추가됩니다

if($this->root == null) 
    { 
     $this->root = $node; 
        $this->root->level = 1; 
     return; 
    } 

    $nextnode = $this->root; 

      $level = 1; 

    while (true) 
    { 
     if($node->value > $nextnode->value) 
     { 
         if($nextnode->right != null) 
         { 
          $nextnode = $nextnode->right; 
          $level++; 
         } 
         else 
         { 
          $nextnode->right = $node; 
          $nextnode->right->level = ++$level; 
          return; 
         } 
     } 
     else if($node->value < $nextnode->value) 
     { 
         if($nextnode->left != null) 
         { 
          $nextnode = $nextnode->left; 
          $level++; 
         } 
         else 
         { 
          $nextnode->left = $node; 
          $nextnode->left->level = ++$level; 
          return; 
         } 
     } 
     else if($node->value == $nextnode->value) 
      return; 
    }

그래서 제 질문은 다음과 같습니다

이는 이진 트리의 단일 수준에 노드를 인쇄하는 유일한 방법이 있나요?
다른 방법이 있습니까?
트리를 만들 때 레벨을 저장하지 않고 다른 방법이 있습니까?

출처

2010-01-23 Para

재귀 솔루션을 사용 하시겠습니까? 나는 이것을 C로 썼다. 나는 이것이 당신에게 문제가되지 않기를 바란다.

void traverse_tree_rec(TreeNode *ptn, int current_level, int targeted_level, (void*)(pVisit)(TreeElement*)){  
    if (ptn==NULL) 
     return; 
    else if(current_level == targeted_level) 
     pVisit(ptn->entry); 
    else{ 
     traverse_tree_rec(ptn->left, current_level+1, targeted_level, pVisit); 
     traverse_tree_rec(ptn->right, current_level+1, targeted_level, pVisit); 
    } 
} 

void traverse_level(Tree *pTree, int level, (void*)(pFunction)(TreeElement)){ 
    traverse_level_rec(pTree->root, 0, level, pFunction); 
}

출처

2010-01-23 08:33:40

level[t] > targeted_level break; 경우 이후 제 1 및 제 2 절은 전환 가능한 또는 간접 참조 널 포인터가있다. 왼쪽 지회를 먼저 방문하는 것이 더 자연 스럽습니다! –

완료되었습니다. 감사합니다. –

@Para,

이 한 단계 다른하지 않는 한 시작 종료하고 정확히 불가능 알 수있다

....

당신은시 전체 트리를 탐색 할 필요가 없습니다 BFS traversal하려고합니다. 배열 레벨 []을 사용하여 위키에있는 BFS psedocode을 수정할 수 있습니다. 다음을 수행해야합니다.

각 노드의 초기화 레벨은 0입니다.
줄에 표시를 할 때마다 : o ← G.opposite(t,e) 레벨 지정 [o] = 레벨 [t] +1;
가 필요 t ← Q.dequeue()

출처

2012-09-10 14:53:31

주어진 이진 트리의 한 레벨에 모든 요소 인쇄

답변

관련 문제