이진 트리 : 이진 트리에서 노드의 조상을 인쇄하는 비 반복적 루틴?

Question

이진 트리에서 주어진 노드의 조상 (상위 부모)을 인쇄하는 비 재귀 프로그램을 작성해야합니다. 어떤 논리를 사용해야합니까?

Answer 1

사용 비 재귀 서브 루틴 (이진 트리를 탐색하는 조각 아래의 [2] 마지막 두 단계를 기억하는 포인터의 배열을 사용하여 http://en.wikipedia.org/wiki/Tree_traversal#Implementations 참조) 스택에 모든 부모 노드를 저장하고 스택에서 팝업 할 때마다 스택에서 요소를 적절하게 팝합니다. 마지막으로 요소를 찾으면 스택의 두 번째 최상위 요소가 조상이됩니다.

Answer 2

조부모 노드에 도달하면 반복 구현 중 하나를 사용하고 (node.Left.Left = desired OR node.Left.Right = desired 또는 node.Right.Left = desired OR node.Right.Right = 원하는). 먼저 후보 노드에 실제로 손주가 있음을 테스트해야합니다.

Answer 3

표준 트리 워크를 수행하고 제한된 스택처럼 마지막 두 단계를 기억할 수 있습니다. ("OPA"는 "할아버지"에 대한 네덜란드 참고) :

#include <stdio.h> 
#include <stdlib.h> 

struct tree_node { 
    struct tree_node * left; 
    struct tree_node * right; 
    int data; 
}; 

     /* a bonsai-tree for testing */ 
struct tree_node nodes[10] = 
/* 0 */ {{ nodes+1, nodes+2, 10} 
/* 1 */ ,{ nodes+3, nodes+4, 5} 
/* 2 */ ,{ nodes+5, nodes+6, 17} 
/* 3 */ ,{ nodes+7, nodes+8, 3} 
/* 4 */ ,{ nodes+9, NULL, 7} 
/* 5 */ ,{ NULL, NULL, 14} 
/* 6 */ ,{ NULL, NULL, 18} 
/* 7 */ ,{ NULL, NULL, 1} 
/* 8 */ ,{ NULL, NULL, 4} 
     }; 

struct tree_node * find_opa(struct tree_node *ptr, int val) 
{ 
struct tree_node *array[2] = {NULL,NULL}; 
unsigned step=0; 

for (step=0; ptr; step++) { 
     if (ptr->data == val) break; 
     array[ step % 2] = ptr; 
     ptr = (val < ptr->data) ? ptr->left : ptr->right; 
     } 

return ptr ? array[step %2] : NULL; 
} 

void show(struct tree_node *ptr, int indent) 
{ 
if (!ptr) { printf("Null\n"); return; } 

printf("Node(%d):\n", ptr->data); 
printf("%*c=", indent, 'L'); show (ptr->left, indent+2); 
printf("%*c=", indent, 'R'); show (ptr->right, indent+2); 
} 

int main(void) 
{ 
struct tree_node *root, *opa; 

root = nodes; 
show (root, 0); 

opa = find_opa(root, 4); 
printf("Opa(4)=:\n"); 
show (opa, 0); 
return 0; 
}