왼쪽 자식 오른쪽 형제 트리에서 노드의 부모를 찾는 방법은 무엇입니까?

Question

왼쪽 자식 오른쪽 형제 트리에서 노드 N의 부모를 찾고 싶습니다. 나무는 아이들을 주문했고 아이들의 수에는 제한이 없습니다.

Node getParent(Node n) 
{ 
    .... 
    return parent; 
} 

정말 도움이 필요합니다. 직접 찾을 방법이 없기 때문에 도움이 필요합니다.

답변은 의사 코드 또는 프로그래밍 언어 일 수 있습니다.

Answer 1

루트에서 시작하여 마지막으로 분기 한 시간을 기억하여 검색하십시오. 키를 찾으면 마지막으로 왼쪽에서 가져온 노드가 부모 노드입니다. 왼쪽 분기를 가져 가면 부모가 없습니다.

BTW 상기 Wikipedia definition

좌측 아이 오른쪽 형제 이진 트리는 K 진 트리의 이진 트리의 표현이다. 1 k-ary 트리에서 LC-RS 이진 트리로 변환하는 프로세스 (Knuth transform 2라고도 함)는 일반적으로 추가 정보없이 되돌릴 수 없습니다.

추가 정보없이 은 일반적으로 되돌릴 수 없습니다 구절은 무엇을 당신이하려고하는 것은 불가능하다는 것을 의미한다.그러나 나는 동의하고, 그래서 여기에

Answer 2

this Wikipedia discussion page 내 대답은하지만 많은 경우에서 테스트되지 않지만 여기

traverse(rootofthistree, NULL, integerWearlookingfor); 

Answer 3

방법처럼 당신은 트래버스 함수가 ​​호출

struct node{ 
    node* left; 
    node* right; 
    int i; 

    node(int _i,node* _left,node* _right){ 
     i=_i; 
     left = _left; 
     right = _right; 
    } 
}; 

node* traverse(node* root,node* parent, int y){ 
    if(root == NULL) return NULL; 
    if(root->i == y) return parent; 

    node* result = traverse(root->left,root,y); 
    if(result) return result; 

    result = traverse(root->right, parent , y); 
    if(result) return result; 

    return NULL; 

} 

아이디어를 얻을 수 있습니다 귀하의 데이터 구조를 이해합니다 :

• node.left은중 하나입니다. (node 먼저 형제 인 경우) (node 트리의 루트 인 경우)
  • 이전 형제 (node가없는 경우 첫 번째 형제)
  • 부모는
  • null는
• node.right 중 하나입니다 :
  • 다음 형제 (node이 마지막 형제가 아닌 경우)
  • null (node 마지막 형제 인 경우)
• node.child
중 하나입니다 :
• 첫 번째 자식 (node은 아이가있는 경우)
• null
( node 나무 잎 인 경우)

그러면 노드 N의 부모를 다음 알고리즘을 통해 얻을 수 있습니다.

node* get_parent(node* N) 
{ 
    //define parent of nullptr to be nullptr 
    if (!N) 
     return nullptr; 
    while (true) 
    { 
     if (N->left) 
     { 
      //N->left is either the previous sibling or the parent 
      if (N->left->child == N) //N->left is the parent 
       return N->left; 
      else //N->left is the previous sibling 
       N = N->left; 
     } 
     else //a node with left==nullptr is the root, so its parent is nullptr 
     { 
      return nullptr; 
     } 
    } 
}