작업은 주어진 이진 트리의 왼쪽 노드를 인쇄하는 것입니다. 먼저 사용자는 데이터를 삽입하여 이진 트리를 생성하고 그렇게 형성된 트리의 왼쪽 보기를 인쇄합니다.
모든 노드는 최대 2개의 자식을 가질 수 있으므로 여기서 프로그램은 노드와 연결된 왼쪽 포인터만 탐색해야 합니다.
왼쪽 포인터가 null이 아니면 출력으로 출력되고 표시될 왼쪽 자식이 아닌 경우 연결된 일부 데이터 또는 포인터가 있음을 의미합니다.
예시
Input : 1 0 3 2 4 Output : 1 0 2
여기서 주황색 노드는 이진 트리의 왼쪽 보기를 나타냅니다.
주어진 그림에서 데이터 1이 있는 노드는 루트 노드이므로 왼쪽 자식으로 가는 것보다 0을 인쇄하고 3으로 가서 왼쪽 자식인 2를 인쇄합니다.
노드의 수준을 저장하고 다른 노드로 반복적으로 이동하기 위해 재귀적 접근 방식을 사용할 수 있습니다.
아래 코드는 주어진 알고리즘의 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 new_data Declare temp variable of node using malloc Set temp->data = new_data Set temp->left = temp->right = NULL return temp Step 3 -> declare function void left_view(struct node* root, int level, int* highest_level) IF root = NULL Exit End IF *highest_level < level Print root->data Set *highest_level = level End Recursively call left_view(root->left, level + 1, highest_level) Recursively call left_view(root->right, level + 1, highest_level) Step 4 -> Declare Function void left(struct node* root) Set int highest_level = 0 Call left_view(root, 1, &highest_level) Step 5-> In main() Call New passing value user want to insert as struct node* root = New(1) Call left(root) STOP
예시
#include <stdio.h>
#include <stdlib.h>
//create a structure of a node
struct node {
int data;
struct node *left, *right; //this pointer will point to the nodes attached with a node
};
struct node* New(int new_data) {
struct node* temp = (struct node*)malloc(sizeof(struct node));
//allocating memory to a pointer dynamically
temp->data = new_data;
temp->left = temp->right = NULL;
return temp;
}
void left_view(struct node* root, int level, int* highest_level) {
if (root == NULL) //if there is no node that means no data
return;
// this function will retrun the root node if there is only root node in a tree
if (*highest_level < level) {
printf("%d\t", root->data);
*highest_level = level;
}
// Recursive function
left_view(root->left, level + 1, highest_level);
left_view(root->right, level + 1, highest_level);
}
void left(struct node* root) {
int highest_level = 0;
left_view(root, 1, &highest_level);
}
int main() {
printf("left view of a binary tree is : ");
struct node* root = New(1);
root->left = New(0);
root->right = New(3);
root->right->left = New(2);
root->right->right = New(4);
left(root);
return 0;
} 출력
위의 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
left view of a binary tree is : 1 0 2