프로그램은 이진 트리의 중간 수준을 인쇄해야 합니다. 이진 트리에 4개의 레벨이 있는 경우 프로그램은 레벨 2 노드를 인쇄해야 하지만 여기서 요구하는 것은 높이를 찾지 않고 레벨을 계산하는 것입니다.
완전 이진 트리는 내부 노드에 두 개의 자식이 있어야 하고 모든 떠나는 노드가 동일한 수준 또는 깊이에 있어야 하는 트리입니다.
여기,
-
내부 노드 21과 32에는 모두 자식이 있습니다.
-
리프 노드는 41, 59, 33, 70으로 모두 같은 레벨에 있습니다.
두 속성을 모두 만족하므로 완벽한 이진 트리입니다.
예시
Input : 12 21 32 41 59 33 70 Output : 21 32
여기에 사용된 접근 방식은 노드의 왼쪽 및 오른쪽 포인터, 즉 함수를 재귀 호출하여 NULL인지 NOT NULL인지 확인하여 연결 목록의 중간 요소를 찾는 것과 같습니다.
아래 코드는 주어진 알고리즘의 c 구현을 보여줍니다.
알고리즘
START Step 1 -> create node variable of type structure Declare int key Declare pointer of type node using *left, *right Step 2 -> create function for inserting node with parameter as value Declare temp variable of node using malloc Set temp->data = value Set temp->left = temp->right = NULL return temp step 3 - > Declare Function void middle(struct Node* a, struct Node* b) IF a = NULL||b = NULL Return IF ((b->left == NULL) && (b->right == NULL)) Print a->key Return End Call middle(a->left, b->left->left) Call middle(a->right, b->left->left) Step 4 -> Declare Function void mid_level(struct Node* node) Call middle(node, node) Step 5 -> In main() Call New passing value user want to insert as struct Node* n1 = New(13); Call mid_level(n1) STOP
예시
#include <stdio.h> #include<stdlib.h> struct Node { int key; struct Node* left, *right; }; struct Node* New(int value) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->key = value; temp->left = temp->right = NULL; return (temp); } void middle(struct Node* a, struct Node* b) { if (a == NULL || b == NULL) return; if ((b->left == NULL) && (b->right == NULL)) { printf("%d ",a->key); return; } middle(a->left, b->left->left); middle(a->right, b->left->left); } void mid_level(struct Node* node) { middle(node, node); } int main() { printf("middle level nodes are : "); struct Node* n1 = New(13); struct Node* n2 = New(21); struct Node* n3 = New(44); struct Node* n4 = New(98); struct Node* n5 = New(57); struct Node* n6 = New(61); struct Node* n7 = New(70); n2->left = n4; n2->right = n5; n3->left = n6; n3->right = n7; n1->left = n2; n1->right = n3; mid_level(n1); }
출력
위의 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
middle level nodes are : 21 44