หาพี่น้องทางขวาของต้นไม้แบบทวิภาคที่มี parent pointers ใน C++

ในปัญหานี้ เราได้รับต้นไม้แบบทวิภาคและ parent pointers งานของเราคือ หาพี่น้องทางขวาของต้นไม้แบบทวิภาคที่มี parent pointers

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

Node = 3

Output

7

วิธีแก้ปัญหา

วิธีแก้ที่ง่ายคือหาโหนดใบของ ancestor ใกล้ที่สุด (ซึ่งไม่ใช่โหนดปัจจุบันและไม่ใช่ parent ของโหนดปัจจุบัน) ซึ่งอยู่ในระดับเดียวกับโหนดปัจจุบัน สิ่งนี้ทำได้โดยนับระดับขณะขึ้นไป และเมื่อลงมาให้นับลงมา แล้วหาโหนดนั้น

โปรแกรมแสดงการทำงานของวิธีแก้

ตัวอย่าง

#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; 
}

ผลลัพธ์

The current node is 3 The right sibling of the current node is 7