C++で再帰せずに特定の二分木ノードの祖先を出力する

この問題では、二分木が与えられ、ノードの祖先を二分木に出力する必要があります。

二分木は、すべてのノードに最大2つの子ノードがある特別なツリーです。したがって、すべてのノードはリーフノードであるか、1つまたは2つの子ノードを持っています。

例

祖先 二分木のノードのは、指定されたノードの上位レベルにあるノードです。

祖先ノードの例を見てみましょう-

このバイナリツリーの値が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