Trong bài toán này, chúng ta được cung cấp một cây nhị phân và chúng ta phải in tổ tiên của nó là một nút trong cây nhị phân.
Cây nhị phân là một cây đặc biệt mà mỗi nút có tối đa hai nút con. Vì vậy, mọi nút đều là nút lá hoặc có một hoặc hai nút con.
Ví dụ,
Tổ tiên của một nút trong cây nhị phân là một nút ở cấp trên của nút đã cho.
Hãy lấy một ví dụ về nút tổ tiên -
Tổ tiên của một nút có giá trị 3 trong cây nhị phân này là 8 ,
Để giải quyết vấn đề này, chúng ta sẽ đi ngang từ nút gốc đến nút đích. Từng bước đi xuống trong cây nhị phân. Và trong đường dẫn in tất cả các nút đến.
Điều này lý tưởng sẽ liên quan đến việc gọi đệ quy các phương thức giống nhau với mỗi nút đi trong đường dẫn từ nút gốc đến nút đích.
Vì vậy, cách tiếp cận không đệ quy sẽ yêu cầu sử dụng truyền tải lặp đi lặp lại và một ngăn xếp sẽ lưu trữ tổ tiên của nút đích trong cây. Chúng ta sẽ thực hiện việc duyệt qua thứ tự sau của cây nhị phân. Và lưu trữ tổ tiên vào ngăn xếp, và cuối cùng in nội dung của ngăn xếp sẽ là tổ tiên của nút.
Ví dụ
#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;
} Đầu ra
The ancestors of the given node are : 27 25 15