Tìm nút bên phải tiếp theo của khóa cho trước trong cây nhị phân C++

Giới thiệu

Cho cây nhị phân và một giá trị khóa. Tìm nút nằm ngay bên phải của nút có khóa đó ở cùng cấp độ (level).

Ví dụ minh họa

Đầu vào

key = 4

Đầu ra

5

Giải thích

Nút 4 và 5 cùng cấp độ, 5 nằm bên phải 4.

Phương pháp giải: Duyệt theo cấp độ (Level Order Traversal)

Sử dụng hàng đợi (queue) lưu cặp (node, level). Khi tìm thấy khóa, kiểm tra phần tử tiếp theo trong hàng đợi có cùng level không.

Chương trình minh họa

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    struct Node *left, *right;
    int key;
};

Node* newNode(int key) {
    Node *temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

Node* findNextRightNode(Node *root, int k) {
    if (!root) return NULL;
    queue q;
    queue levelQ;
    q.push(root);
    levelQ.push(0);
    
    while (!q.empty()) {
        Node *node = q.front(); q.pop();
        int level = levelQ.front(); levelQ.pop();
        
        if (node->key == k) {
            if (levelQ.empty() || levelQ.front() != level)
                return NULL;
            return q.front();
        }
        
        if (node->left) {
            q.push(node->left);
            levelQ.push(level+1);
        }
        if (node->right) {
            q.push(node->right);
            levelQ.push(level+1);
        }
    }
    return NULL;
}

int main() {
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    
    int key = 4;
    cout << "The next right node of " << key << " is ";
    Node *nextNode = findNextRightNode(root, key);
    if (nextNode) cout << nextNode->key;
    else cout << "not available";
    return 0;
}

Đầu ra

The next right node of the node 4 is 5