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ố sau 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ố sau là nút xuất hiện tiếp theo 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: 9 Đầu ra: 0 Giải thích: duyệt tiền tố của cây là: 5 9 0 1 2 5. Vì vậy, nút tiền tố sau của 9 là 0.
Để 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ố sau dựa trên vị trí. Vì vậy, nếu vị trí có con trái, thì tiền tố sau là con trái. Nếu nó là nút lá nhưng là con trái thì nút anh em của nó là tiền tố sau. Nếu nó là nút lá và không phải con trái thì chúng ta phải di chuyển lên các nút tổ tiên của nó mà nút con của chúng sẽ là tiền tố sau.
Chương trình sẽ làm cho giải pháp rõ ràng hơn:
Ví dụ
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preOrderSuccessorNode(Node* root, Node* n){
if (n->left)
return n->left;
Node *curr = n, *parent = curr->parent;
while (parent != NULL && parent->right == curr) {
curr = curr->parent;
parent = parent->parent;
}
if (parent == NULL)
return NULL;
return parent->right;
}
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* preOrder = preOrderSuccessorNode(root, root->left->right);
if (preOrder) {
cout<<"Nút tiền tố sau của "<<root->left->right->key<<" là "<<preOrder->key;
} else {
cout<<"Nút tiền tố sau của "<<root->left->right->key<<" là NULL";
}
return 0;
}
Kết quả
Nút tiền tố sau của 50 là 26