ต้นไม้ไบนารี เป็นต้นไม้พิเศษที่ทุกโหนดมีโหนดย่อยสูงสุดสองโหนด ดังนั้น ทุกโหนดจึงเป็นโหนดปลายสุดหรือมีโหนดย่อยหนึ่งหรือสองโหนด
ตัวอย่าง
ในปัญหานี้ เราได้รับไบนารีทรี และเรามีโหนดของทรี และเราต้องหาโหนดลูกพี่ลูกน้องของโหนดนั้น ไม่มีการพิมพ์โหนดพี่น้องสำหรับไบนารีทรี
มาดูตัวอย่างกัน
สำหรับไบนารีทรีด้านบน โหนดลูกพี่ลูกน้องคือ 5
เพื่อให้แนวคิดชัดเจนยิ่งขึ้น เรามาอธิบายโหนดลูกพี่ลูกน้องกัน ในไบนารีทรี กล่าวกันว่าโหนดสองโหนดเป็นโหนดลูกพี่ลูกน้อง หากโหนดทั้งสองอยู่ที่ระดับ (ความลึก) เดียวกันในไบนารีทรี แต่ไม่มีโหนดหลักเดียวกัน
มาสร้างวิธีแก้ปัญหานี้กัน
ที่นี่เราต้องพิมพ์โหนดทั้งหมดในระดับเดียวกันของโหนดนั่นคือ โหนดทั้งหมดที่อยู่ห่างจากโหนดรูทเท่ากัน แต่เราต้องกำจัดโหนดที่มีพาเรนต์เดียวกันกับตัวโหนดเอง สำหรับสิ่งนี้ เราจะค้นหาระดับของโหนดก่อน จากนั้นจึงพิมพ์โหนดทั้งหมด ยกเว้นตัวโหนดและโหนดที่มีพาเรนต์เดียวกัน
ตัวอย่าง
ตอนนี้ มาสร้างโปรแกรมตามตรรกะนี้กัน -
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *left, *right;
};
Node *newNode(int item){
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
int levelOfNode(Node *root, Node *node, int level){
if (root == NULL)
return 0;
if (root == node)
return level;
int downlevel = levelOfNode(root->left,
node, level + 1);
if (downlevel != 0)
return downlevel;
return levelOfNode(root->right, node, level + 1);
}
void printCousin(Node* root, Node *node, int level){
if (root == NULL || level < 2)
return;
if (level == 2){
if (root->left == node || root->right == node)
return;
if (root->left)
cout << root->left->data << " ";
if (root->right)
cout << root->right->data;
}
else if (level > 2){
printCousin(root->left, node, level - 1);
printCousin(root->right, node, level - 1);
}
}
void cousinNode(Node *root, Node *node){
int level = levelOfNode(root, node, 1);
printCousin(root, node, level);
}
int main(){
Node *root = newNode(11);
root->left = newNode(15);
root->right = newNode(4);
root->left->left = newNode(3);
root->left->right = newNode(7);
root->left->right->right = newNode(9);
root->right->left = newNode(17);
root->right->right = newNode(8);
root->right->left->right = newNode(5);
cout<<”The cousin nodes are : \t”
cousinNode(root, root->right->right);
return 0;
} ผลลัพธ์
The cousin nodes are : 3 7
