Chương trình sẽ in mức giữa của cây nhị phân, ví dụ:nếu có 4 mức trong cây nhị phân thì chương trình phải in ra các nút mức 2 nhưng yêu cầu ở đây là tính mức mà không cần tìm chiều cao.
Cây nhị phân hoàn hảo là cây trong đó các nút bên trong phải có hai nút con và tất cả các nút rời phải ở cùng mức hoặc độ sâu.
Đây,
-
Các nút bên trong 21 và 32 đều đang có con
-
Các nút lá là 41, 59, 33 và 70 đều nằm ở cùng một mức.
Vì nó đáp ứng cả hai thuộc tính nên nó là một cây nhị phân hoàn hảo.
Ví dụ
Input : 12 21 32 41 59 33 70 Output : 21 32
Cách tiếp cận được sử dụng ở đây giống như việc tìm kiếm các phần tử giữa của một danh sách được liên kết bằng cách kiểm tra con trỏ trái và phải của một nút, tức là NULL hay NOT NULL bằng cách thực hiện một lệnh gọi đệ quy đến một hàm.
Đ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 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
Ví dụ
#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);
} Đầ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.
middle level nodes are : 21 44