Trong bài toán này, chúng ta được cung cấp một cây nhị phân và các con trỏ cha. Nhiệm vụ của chúng ta là Tìm anh / chị / em bên phải của cây nhị phân với các con trỏ mẹ.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
Node = 3
Đầu ra
7
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm nút lá của tổ tiên gần nhất (không phải là nút hiện tại cũng không phải là nút hiện tại) ở cùng mức với nút hiện tại. Điều này được thực hiện bằng cách đếm các cấp độ trong khi đi lên và sau đó khi xuống dưới đếm ngược. Và sau đó tìm nút.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right, *parent;
};
Node* newNode(int item, Node* parent) {
Node* temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
temp->parent = parent;
return temp;
}
Node* findRightSiblingNodeBT(Node* node, int level) {
if (node == NULL || node->parent == NULL)
return NULL;
while (node->parent->right == node ||
(node->parent->right == NULL && node->parent->left == node)) {
if (node->parent == NULL || node->parent->parent == NULL)
return NULL;
node = node->parent;
level++;
}
node = node->parent->right;
if (node == NULL)
return NULL;
while (level > 0) {
if (node->left != NULL)
node = node->left;
else if (node->right != NULL)
node = node->right;
else
break;
level--;
}
if (level == 0)
return node;
return findRightSiblingNodeBT(node, level);
}
int main(){
Node* root = newNode(4, NULL);
root->left = newNode(2, root);
root->right = newNode(5, root);
root->left->left = newNode(1, root->left);
root->left->left->left = newNode(9, root->left->left);
root->left->left->left->left = newNode(3, root->left->left->left);
root->right->right = newNode(8, root->right);
root->right->right->right = newNode(0, root->right->right);
root->right->right->right->right = newNode(7, root->right->right->right);
Node * currentNode = root->left->left->left->left;
cout<<"The current node is "<<currentNode->data<<endl;
Node* rightSibling = findRightSiblingNodeBT(currentNode, 0);
if (rightSibling)
cout<<"The right sibling of the current node is "<<rightSibling->data;
else
cout<<"No right siblings found!";
return 0;
} Đầu ra
The current node is 3 The right sibling of the current node is 7