C++에서 재귀 없이 주어진 이진 트리 노드의 조상 인쇄

이 문제에서는 이진 트리가 주어지고 이진 트리에서 노드의 조상을 인쇄해야 합니다.

이진 트리는 모든 노드에 최대 두 개의 자식 노드가 있는 특수 트리입니다. 따라서 모든 노드는 리프 노드이거나 하나 또는 두 개의 하위 노드가 있습니다.

예

선조 바이너리 트리의 노드는 주어진 노드의 상위 레벨에 있는 노드입니다.

조상 노드의 예를 들어 보겠습니다 -

이 바이너리 트리에서 값이 3인 노드의 조상은 8입니다. ,

이 문제를 해결하기 위해 루트 노드에서 대상 노드로 트래버스합니다. 이진 트리에서 단계적으로 아래로. 그리고 경로에서 오는 모든 노드를 인쇄합니다.

이것은 루트 노드에서 대상 노드로의 경로에 오는 각 노드와 동일한 메소드의 재귀 호출을 이상적으로 포함합니다.

따라서 비재귀적 접근 방식은 반복 순회와 대상 노드의 조상을 트리에 저장할 스택을 사용해야 합니다. 우리는 이진 트리의 후위 순회를 할 것입니다. 그리고 스택에 조상을 저장하고, 마지막으로 노드의 조상이 될 스택의 내용을 출력합니다.

예시

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Node{
   int data;
   struct Node *left, *right;
};
struct Stack{
   int size;
   int top;
   struct Node* *array;
};
struct Node* insertNode(int data){
   struct Node* node = (struct Node*) malloc(sizeof(struct Node));
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
struct Stack* createStack(int size){
   struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
   stack->size = size;
   stack->top = -1;
   stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
   return stack;
}
int isFull(struct Stack* stack){
   return ((stack->top + 1) == stack->size);
}
int isEmpty(struct Stack* stack){
   return stack->top == -1;
}
void push(struct Stack* stack, struct Node* node){
   if (isFull(stack))
      return;
   stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack){
   if (isEmpty(stack))
      return NULL;
   return stack->array[stack->top--];
}
struct Node* peek(struct Stack* stack){
   if (isEmpty(stack))
      return NULL;
   return stack->array[stack->top];
}
void AncestorNodes(struct Node *root, int key){
   if (root == NULL) return;
   struct Stack* stack = createStack(MAX_SIZE);
   while (1){
      while (root && root->data != key){
         push(stack, root);
         root = root->left;
      }
      if (root && root->data == key)
         break;
      if (peek(stack)->right == NULL){
         root = pop(stack);
         while (!isEmpty(stack) && peek(stack)->right == root)
            root = pop(stack);
      }
      root = isEmpty(stack)? NULL: peek(stack)->right;
   }
   while (!isEmpty(stack))
      printf("%d ", pop(stack)->data);
}
int main(){
   struct Node* root = insertNode(15);
   root->left = insertNode(10);
   root->right = insertNode(25);
   root->left->left = insertNode(5);
   root->left->right = insertNode(12);
   root->right->left = insertNode(20);
   root->right->right = insertNode(27);
   root->left->left->left = insertNode(1);
   root->left->right->right = insertNode(14);
   root->right->right->left = insertNode(17);
   printf("The ancestors of the given node are : ");
   AncestorNodes(root, 17);
   getchar();
   return 0;
}

출력

The ancestors of the given node are : 27 25 15