트리 구조의 일반 탐색

Question

내 트리 (글쎄, 바이너리 트라이)를 쓰려고합니다. 더 일반적인 방식입니다. 지금은 매우 비슷한 코드가 반복되어 있기 때문입니다.

나는 사전 식 inorder에서 나무를 걷고있다. 나는 보편적 인 트리 탐색에 의해 추상화 될 수 있다고 생각 함수의 예 (의사 코드)입니다 : 내가 코드를 올바른 방향으로 그냥 밀어 기능을 요구하고 있지 않다

items(node*, key, list&) { 
    if(node->value) 
     list.push({node->value, key}) 
    if(node->left) 
     items(node->value, key + "0") 
    if(node->right) 
     items(node->value, key + "1") 
} 

draw(node*, id, ostream&) { 
    drawNode(node, id) 
    if (node->left) 
     drawLine(node, node->left, "0", ostream&) 
     draw(node->left, ++id, ostream&) 
    if (node->right) 
     drawLine(node, node->right, "1", ostream&) 
     draw(node->right, ++id, ostream&) 

. 함수를 인수로 사용하는 템플릿을 사용해야합니까? 순회가 단일 왼쪽/오른쪽 노드 (두 트라이의 병합이이 추상화의 후보와 너무 비슷해 보임)의 존재에 의해 조건이 충족되지 않는 더 복잡한 경우는 어떻습니까?

Answer 1

순회의 일반적인 추상화는 적절한 반복자 형태입니다. 순회가 일련의 선형 위치가되면, 일반적인 반복자 중 하나를 사용하여 포지셔닝 할 수 있습니다. 대부분 BidirectionalIterator를 모델링합니다. 나무의 횡단 (또는보다 일반적인, 그래프)을 일반화 할 때, 반복 조작이 다른 방향으로 움직일 수 있습니다.