Nút tiền tố trước của một nút trong cây nhị phân trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân và một giá trị nút. Nhiệm vụ của chúng ta là in nút tiền tố trước của nút đó.

Cây nhị phân là một loại cây đặc biệt mà mỗi nút gốc có tối đa 2 nút con.

Duyệt tiền tố là một cách để duyệt các nút của cây. Trong này, chúng ta sẽ trước tiên duyệt nút gốc, sau đó nút con trái và rồi nút con phải.

Nút tiền tố trước là nút xuất hiện trước nút đó trong duyệt tiền tố của nút.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào: 1
Đầu ra: 9

Để giải quyết bài toán này, một cách tiếp cận naive sẽ là tìm duyệt tiền tố của cây nhị phân và sau đó in phần tử xuất hiện sau số cho trước.

Một giải pháp hiệu quả hơn sẽ liên quan đến việc kiểm tra vị trí của số cho trước và sau đó tìm tiền tố trước dựa trên vị trí. Nếu nút là nút gốc, trả về NULL, không có tiền tố trước. Nếu nút là con phải, thì con trái sẽ là tiền tố trước.

Chương trình minh họa triển khai giải pháp:

Ví dụ

#include <iostream>
using namespace std;
struct Node {
    struct Node *left, *right, *parent;
    int key;
};
struct Node* insertNode(int key){
    Node* temp = new Node;
    temp->left = temp->right = temp->parent = NULL;
    temp->key = key;
    return temp;
}
Node* preOrderPredecessorNode(Node* root, Node* n){
    if (n == root)
        return NULL;
    Node* parent = n->parent;
    if (parent->left == NULL || parent->left == n)
        return parent;
    Node* curr = parent->left;
    while (curr->right != NULL)
        curr = curr->right;
    return curr;
}
int main() {
    Node* root = insertNode(99);
    root->parent = NULL;
    root->left = insertNode(4);
    root->left->parent = root;
    root->left->left = insertNode(18);
    root->left->left->parent = root->left;
    root->left->right = insertNode(50);
    root->left->right->parent = root->left;
    root->right = insertNode(26);
    root->right->parent = root;
    root->right->left = insertNode(5);
    root->right->left->parent = root->right;
    root->right->right = insertNode(10);
    root->right->right->parent = root->right;
    Node* preOrderPredecessor = preOrderPredecessorNode(root, root->left->right);
    if (preOrderPredecessor)
        cout<<"Nút tiền tố trước của "<<root->left->right->key<<" là "<<preOrderPredecessor->key;
    else
        cout<<"Nút tiền tố trước của "<<root->left->right->key<<" là NULL";
    return 0;
}

Kết quả

Nút tiền tố trước của 50 là 18