트리 탐색/링크 된 목록 구조

Question

하이브리드 트리/링크 된 목록 구조와 비슷합니다. 다음은 구조를 정의한 방법입니다.

struct node { 
    nodeP sibling; 
    nodeP child; 
    nodeP parent; 
    char name[100];  
}; 

노드에는 연결된 목록에 연결된 자식이 있습니다. 연결된 목록의 다른 요소는 연결된 목록 또는 자체로 연결된 자체 자식이있을 수 있습니다.

내 질문에, 어떻게이 노드를 탐색하여 특정 노드의 경로를 인쇄 할 수 있습니까?

의견을 보내 주시면 감사하겠습니다. 감사

업데이트 다음은 printPath 기능 :

//node -> root of the tree 
//current = this is the node that i need to print path to 

void printPath(nodeP node, nodeP current){ 

    if (node != NULL){ 
     if ((strcmp(node->name, current->name) == 0)) 
     { 
      printf("%s/", node->name); 
      return; //it returns to the previous recursive call and then continues until the node is null 
     } 
     printPath(root->childDir, currentDir); 
     printPath(root->sibling, currentDir); 
     printf(" %s/", node->name); 
    } 
} 

내 문제는 한 번 마무리 인쇄 경로의 경우 현재 노드에 재귀 호출 벗어나 려한다.

Answer 1

질문에 제시된 노드 구조는 이름 child 대신 기존의 left 및 right의 sibling를 사용하는 일반 이진 트리와 동일합니다. 원하는 노드의 경로를 인쇄하려면 루트 각 노드의 하위 트리의 값을 인쇄해야합니다. 그래서 여기 의사 코드입니다 : 루트가 null의 경우 여기에

function printPath(root, searchName) 
    if root is null 
     return false 
    if root.name is searchName or 
     printPath(root.child, searchName) or 
     printPath(root.sibling, searchName) then 
     print root.name 
     return true 
    else 
     return false 

, 그것은 원하는 노드를 포함하지 않는, 그래서 우리는 아무것도 인쇄하지 않습니다이 경로에 대해 false를 돌려줍니다. 그러나 이름이 우리가 원하는 이름이거나 하위 트리 중 하나에 원하는 이름이 들어 있으면 이름을 인쇄하고 true를 반환합니다. 이 방법을 사용하면 리프에서 루트까지 순서대로 경로가 인쇄됩니다.