재귀 후 주문 트리 탐색

Question

나는 다음과 같은 알고리즘을 구현하기 위해 노력하고 있습니다 :

피치의 알고리즘 (한 문자 시퀀스) :

1 단계 : 각 리프 노드 N의 경우, 세트를 만듭니다 잎의 할당 된 문자를 포함하는 Sn.

2 단계 : 자식 u와 v를 가진 각 내부 노드 n에 대해 다음과 같은 집합 Sn을 만듭니다. • Su ∩ Sv가 비어 있지 않은 경우 Su ∩ Sv. • Su ∩ Sv가 이면 비어 있습니다.

단계 3 : 각각의 내부 노드는 N 상위 P와, n.seq 할당 할 캐릭터 같다 : • p.seq 경우 p.seq ∈ 주석의 Sn • 달리 임의의 문자 (또는 N 루트 인 경우).

입력으로 이진 트리가 지정되었습니다.

나는 1 단계를 완료했으며 이제 모든 노드에 세트를 할당하기 위해 이진 트리를 통해 포스트 순서 탐색을 반복적으로 수행해야합니다. 이 일을 시작하는 방법이 궁금합니다. 전순 재귀를 사용하여 트리를 통해 탐색

(이 트리에서 얼마나 많은 잎에 의해 결정 트리의 길이를 계산하는 예에 불과 잎 = 자식이.)과 같은 수행됩니다

def __len__(self): 

    if self.isLeaf(): 
     print('base case - reached leaf!') 
     return 1 

    for t,w in self.children: 
     print('not leaf so sent through loop') 
     numLeaves += len(t) 

    return numLeaves 

Answer 1

그것은 꽤 똑바로 앞으로, 당신은 노드가 더 이상 왼쪽 및 오른쪽 자식을 가지고 방문한 것으로 표시합니다. 루트 노드를 방문하면 알고리즘이 완료됩니다. 재귀를 사용하면 알고리즘이 훨씬 쉬워집니다.

알고리즘에 알맞은 세트를 얻으려면 게시물 순서 탐색에서 캐릭터 라인 할당 (리프라면 1 문자가됩니다) 또는 공백 문자가 있어야합니다 (오른쪽 또는 왼쪽).

게시 순서 기능에서 반환 된 문자열을 추가 한 다음 추가 된 문자열을 반환합니다.

http://en.wikipedia.org/wiki/Tree_traversal#Post-order