벡터 기반 이진 트리 탐색

Question

저는 벡터 기반 이진 트리가 있고 다양한 트래버스 방법을 사용하여 트리의 각 값에 함수를 적용해야합니다. 선주문 탐색은 재귀 함수를 사용하여 구현하기가 매우 쉬웠지만 inorder와 postorder traversals와 동일한 작업을 수행하는 데 어려움을 겪고 있습니다. 누구라도 도움이된다면 위대한 것입니다!

다음과 같은 몇 가지 추가 정보가 포함되어 있어야합니다. 각 노드에 해당 노드가 채워지는지 여부 및 서식이 지정된 데이터 변수인지를 나타내는 부울 변수가 포함 된 노드 벡터를 사용하고 있습니다. 각 노드는 인덱스 "i"에 저장되고 왼쪽 자식은 인덱스 "2i + 1"에 있고 오른쪽 자식은 "2i + 2"에 저장됩니다.

목록에 전순 주사를 적용하려면 I 먼저 번 인덱스 내 "N"파라미터와 같은 1 & 2로 시작이 재귀 함수

template <typename Item, typename Key> 
template <typename Function> 
void BST<Item,Key>::preTraverse(int n, Function f) { 
    if(tree[n].occupied == false) return; 
    else { 
     f(tree[n].data); 
     preTraverse(2*i+1,f); 
     preTraverse(2*i+2,f); 
    } 
} 

라고 다음 인덱스 0에 저장된 데이터를 처리.

Answer 1

최대 채워 왼쪽 지배적 인 표현을 당신의 나무입니다 가정하면, 다음 주어진 점 당신의 i 위치의 배열에는 2*i+1 및위치의 자식이 있습니다.. 사소한 거리가 :

Node Children 
===== =========== 
ar[0]: ar[1], ar[2] 
ar[1]: ar[3], ar[4] 
ar[2]: ar[5], ar[6] 
ar[3]: ar[7], ar[8] 
ar[4]: ar[9], ar[10] etc... 

이 정의, 예약 주문, postorder을 감안할 때

와의 주문은 모두 간단한 인덱스 전달하고 '점령'플래그에 대한 몇 가지 검사 수행 할 수 있습니다. 다음 템플리트는 유형이 T이 '점유'멤버가있는 구조 유형이라고 가정합니다.

template<typename T> 
void preorder(const T ar[], size_t i, size_t count, void (&visit)(const T&)) 
{ 
    if (i>=count || !ar[i].occupied) 
     return; 

    visit(ar[i]); 
    preorder(ar, 2*i+1, count, visit); 
    preorder(ar, 2*(i+1), count, visit); 
} 

template<typename T> 
void inorder(const T ar[], size_t i, size_t count, void (&visit)(const T&)) 
{ 
    if (i>=count || !ar[i].occupied) 
     return; 

    inorder(ar, 2*i+1, count, visit); 
    visit(ar[i]); 
    inorder(ar, 2*(i+1), count, visit); 
} 

template<typename T> 
void postorder(const T ar[], size_t i, size_t count, void (&visit)(const T&)) 
{ 
    if (i>=count || !ar[i].occupied) 
     return; 

    postorder(ar, 2*i+1, count, visit); 
    postorder(ar, 2*(i+1), count, visit); 
    visit(ar[i]); 
} 

Answer 2

예약 주문 :

do something with the value 
f(go to the left) 
f(go to the right) 

중위 :

f(go to the left) 
do something with the value 
f(go to the right) 

postorder :에

f(go to the left) 
f(go to the right) 
do something with the value