이진 트리 재귀 기능

Question

I는 다음과 같습니다 이진 트리를 인쇄해야합니다 라인의 왼쪽 첫 번째를 제외하고 라인의 오른쪽면을 인쇄하기 위해 재귀를 사용

--------x------- 
----x-------x--- 
--x---x---x---x- 
-x-x-x-x-x-x-x-x 
xxxxxxxxxxxxxxxx 

선. 따라서 함수는 왼쪽 시작점과 오른쪽 끝점의 매개 변수를 사용하여 표시 함수를 호출합니다. 그런 다음 왼쪽과 오른쪽에서 각각 두 번 호출합니다.

#include <stdio.h> 

#define LENGTH 16 

void makeBranches(int, int); 
void display(int, int); 

int main(){ 

    makeBranches(0, LENGTH-1); 
} 

void makeBranches(int left, int right){ 

    if(left >= right){ 
    return; 
    } else{ 
    display(left, right); 
     makeBranches(left, (right+left)/2); 
     makeBranches((right+left)/2+1, right); 
    } 
} 

void display(int left, int right){ 
    int mid = (left+right)/2; 
    int i; 

    for(i = left; i <= right; i++){ 
    if(i == mid) 
     printf("X"); 
    else 
     printf("-"); 
    } 

    if(right == LENGTH-1) 
    printf("\n"); 

} 

이것은 여러 번 변경되었지만 현재 내 코드의 모습입니다.

makeBranches의 첫 번째 호출을 실행 한 다음 두 번째 호출을받는 방법을 알아낼 수 없습니다. 지금 만 왼쪽 호출을 수행하고 다음과 같습니다 : 이미 볼 수 있듯이

-------X-------- 
---X-----X--X- 

Answer 1

이 문제는 재귀 함수를 호출의 구조 트리 내에 자리 잡고 있습니다. 이러한 유형의 동작을 방지하려면 아무 것도 인쇄하기 전에 전체 트리를 스캔하는 디자인을 구현해야합니다.

귀하의 호출 구조는 지금과 같이 작동합니다 :

makeBranches(left,right) -> 
    makeBranches(left, (right+left)/2) -> 
    makeBranches(left, ((right+left)/2+left)/2) -> 
     makeBranches(left, (((right+left)/2+left)/2+left)/2) -> etc. 
    makeBranches((right+left)/2+1,right) -> 
    makeBranches((right+(right+left)/2+1)/2+1,right) -> 
     makeBranches((right+(right+(right+(right+left)/2+1)/2+1)/2+1)/2+1,right) -> etc. 

인쇄하기 전에 각 레벨을 캡처 무엇 당신이해야 할 목표로해야이 문제를 평평하게하기 위해. 이렇게하려면 각면에 추가 할 링크드 목록과 같은 컬렉션 형식이 필요합니다. 그런 다음 전체 트리를 스캔 한 후 도면을 재구성 할 수 있습니다.

if(right == LENGTH-1) 
    printf("\n"); 

그래서의 디스플레이 호출을 수정할 수 있습니다 : 당신의 display 함수 내에서

당신은 이미이 왼쪽 또는 오른쪽 라인의 측면이 있는지 알고 수표를 만들었습니다. 지금부터

void display(int left, int right){ 
    int mid = (left+right)/2; 
    int i; 
    string thisLine = ""; 

    for(i = left; i <= right; i++){ 
    if(i == mid) 
     thisLine += "X"; 
    else 
     thisLine += "-"; 
    } 

    if(right == LENGTH-1) { 
    rightList.add(thisLine); 
    } else { 
    leftList.add(thisLine); 
    } 
} 

, 당신의 전체 트리 인쇄 밖으로 left->right->"\n"가는 각 목록의 모든 노드를 구축 한 후 (빈 때까지 반복) main().

주의 할 점은 있지만 처음 설계 한 코드는 display입니다. 내 코드를 사용하면 right 목록에있는 코드를 삭제할 수 있습니다. 그리는 것처럼 right->(left->right->"\n")repeat

의미가 있습니까? 나는 이것을 개념적으로 다 했으므로 나는 무엇이든 건너 뛰지 않았 으면 좋겠다 : \

Answer 2

당신은 breadth-first traversal을해야 할 것이다.