작업은 주어진 이진 트리의 올바른 노드를 인쇄하는 것입니다. 먼저 사용자는 바이너리 트리를 생성하기 위한 데이터를 삽입하고 그렇게 형성된 트리의 오른쪽 보기를 인쇄합니다.
위의 다이어그램은 노드 10, 42, 93, 14, 35, 96, 57, 88로 생성된 이진 트리를 보여줍니다. 이 노드 중 트리의 오른쪽에 있는 노드가 선택되어 화면에 표시됩니다. 예를 들어, 10, 93, 57 및 88은 이진 트리의 가장 오른쪽 노드입니다.
예
Input : 10 42 93 14 35 96 57 88 Output : 10 93 57 88
각 노드와 연관된 두 개의 포인터, 즉 왼쪽과 오른쪽이 있습니다. 이 질문에 따라 프로그램은 올바른 노드만 통과해야 합니다. 따라서 노드의 왼쪽 자식에 대해 신경 쓸 필요가 없습니다.
오른쪽 보기는 해당 수준의 마지막 노드인 모든 노드를 저장합니다. 따라서 재귀적 접근 방식을 사용하여 오른쪽 하위 트리가 왼쪽 하위 트리보다 먼저 탐색되는 방식으로 노드를 저장하고 액세스할 수 있습니다. 프로그램이 이전 노드보다 이전 노드의 레벨보다 높은 노드를 감지할 때마다 해당 레벨의 마지막 노드로 표시됩니다.
아래 코드는 주어진 알고리즘의 c 구현을 보여줍니다.
알고리즘
START Step 1 -> create node variable of type structure Declare int data Declare pointer of type node using *left, *right Step 2 -> create function for inserting node with parameter as item Declare temp variable of node using malloc Set temp->data = item Set temp->left = temp->right = NULL return temp step 3 -> Declare Function void right_view(struct node *root, int level, int *end_level) IF root = NULL Return IF *end_level < level Print root->data Set *end_level = level Call right_view(root->right, level+1, end_level) Call right_view(root->left, level+1, end_level) Step 4 -> Declare Function void right(struct node *root) Set int level = 0 Call right_view(root, 1, &level) Step 5 -> In Main() Pass the values for the tree nodes using struct node *root = New(10) Call right(root) STOP
예
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *left, *right;
};
struct node *New(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
void right_view(struct node *root, int level, int *end_level) {
if (root == NULL) return;
if (*end_level < level) {
printf("%d\t", root->data);
*end_level = level;
}
right_view(root->right, level+1, end_level);
right_view(root->left, level+1, end_level);
}
void right(struct node *root) {
int level = 0;
right_view(root, 1, &level);
}
int main() {
printf("right view of a binary tree is : ");
struct node *root = New(10);
root->left = New(42);
root->right = New(93);
root->left->left = New(14);
root->left->right = New(35);
root->right->left = New(96);
root->right->right = New(57);
root->right->left->right = New(88);
right(root);
return 0;
} 출력
위의 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
right view of a binary tree is : 10 93 57 88