Nhiệm vụ là in các nút bên phải của một cây nhị phân cho trước. Đầu tiên người dùng sẽ chèn dữ liệu để tạo cây nhị phân và in ra chế độ xem bên phải của cây được hình thành như vậy.
Sơ đồ trên giới thiệu cây nhị phân được tạo với các nút 10, 42, 93, 14, 35, 96, 57 và 88 trong số các nút này, nút nằm ở phía bên phải của cây được chọn và hiển thị trên màn hình. Ví dụ:10, 93, 57 và 88 là các nút ngoài cùng bên phải của cây nhị phân.
Ví dụ
Input : 10 42 93 14 35 96 57 88 Output : 10 93 57 88
Có hai con trỏ được liên kết với mỗi nút, tức là trái và phải. Theo câu hỏi này, chương trình chỉ phải đi qua các nút bên phải. Vì vậy, không cần phải bận tâm về phần con bên trái của một nút.
Chế độ xem bên phải lưu trữ tất cả các nút là nút cuối cùng của cấp độ của chúng. Vì vậy, chúng ta có thể đơn giản sử dụng phương pháp đệ quy để lưu trữ và truy cập các nút theo cách sao cho cây con bên phải được duyệt trước cây con bên trái. Bất cứ khi nào chương trình phát hiện nút có cấp lớn hơn cấp của nút trước đó so với nút trước đó sẽ được hiển thị vì nó sẽ là nút cuối cùng của cấp đó.
Đoạn mã dưới đây cho thấy cách triển khai c của thuật toán đã cho
Thuật toán
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
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau.
right view of a binary tree is : 10 93 57 88