최소에서 최대 2-3 트리 인쇄 방법?

Question

알고리즘에 접근하는 방법을 모르겠습니다.

TreeNode n = root; 
while(n.first.first!=0){ 
    n=n.first; 
} // finding the leftMost parent 
//printing the first child key, then first num of parent, then second child.. and so on 

누군가가 더 나은 아이디어가 있습니까 : 나는 그런 일을 생각했다?

Answer 1

2-3 트리의 정의에 따르면, 당신은 노드의 3 개 종류를 만날 수 :

어린이 2 명 1 개 값
• 내부 노드
세 어린이와 2 값
• 내부 노드 자녀가없는 1 또는 2 개 값

와

잎 이 정보가 있으면 루트 노드에서 시작하여 노드를 통과하는 재귀 적 메서드를 사용할 수 있습니다. 그것이 잎 노드를 만나는 경우 단순히 값을 인쇄합니다. 다른 경우에는 메서드가 가장 왼쪽 노드 (왼쪽 노드로 점프)에 대해 자체 호출 한 다음 첫 번째 값을 인쇄 한 후 다음 노드로 이동해야합니다. 그 후 메소드가 종료되어 전체 알고리즘이 끝나거나 (실제 노드가 루트 노드 인 경우) 부모 노드로 돌아갑니다 (실제 노드가 내부 자식 노드 인 경우)

여기 의사 코드가 있습니다. 나는 너 자신을 위해 실제 구현을 떠났다. 이를 연구하고 메소드의 흐름을 이해했는지 확인하십시오 (디버거를 사용하여 실제 매개 변수를 추적 할 수 있음)

/* you start algorithm by calling recursivePrint(root) */ 

void recursivePrint(node){ 

    if (node is a leaf){ 

     /* Here print node's value/values */ 

    } else if (node has 2 children){ 

     recursivePrint(node.leftChild); 
     /* Here print node's value */ 
     recursivePrint(node.rightChild); 

    } else if (node has 3 children) 

     recursivePrint(node.leftChild); 
     /* Here print node's left value */ 
     recursivePrint(node.middleChild); 
     /* Here print node's right value */ 
     recursivePrint(node.rightChild) 

    } 

    /* Shouldn't be other cases in 2-3 trees */ 
}