Trong bài toán này, chúng ta được cung cấp một cây nhị phân và một giá trị nút. Nhiệm vụ của chúng tôi là in phần tử kế nhiệm của nút đặt hàng trước.
Cây nhị phân là một loại cây đặc biệt, trong đó mỗi nút gốc có thể có tối đa 2 nút con.
Đặt hàng trước Truyền tải là một cách để đi qua các nút của cây. Trong phần này, đầu tiên chúng ta sẽ duyệt qua nút gốc, sau đó là nút con bên trái và sau đó là nút con bên phải.
Đặt hàng trước nút kế nhiệm là nút đến bên cạnh nút trong quá trình đặt hàng trước của nút.
Hãy lấy một ví dụ để hiểu vấn đề
Input: 9 Output 0 Explanation: the preorder traversal of the tree is: 5 9 0 1 2 5. So the preorder successor of 9 is 0.
Để giải quyết vấn đề này, cách tiếp cận điều hướng sẽ là tìm đường truyền đặt trước của cây nhị phân và sau đó in phần tử đứng sau số đã cho.
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 một số đã cho và sau đó tìm kiếm người kế nhiệm của nó dựa trên các vị trí. Vì vậy, nếu vị trí có con bên trái, thì vị trí kế vị đặt hàng trước là con bên trái. Nếu đó là nút lá nhưng là nút con bên trái thì nút anh chị em của nó là nút kế nhiệm đặt hàng trước. Nếu đó là nút lá và không phải là nút con bên trái thì chúng ta phải chuyển đến các nút tổ tiên của nó mà các nút con của nó sẽ là nút kế nhiệm được đặt hàng trước.
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<<"Preorder successor of "<<root->left->right->key<<" is "<<preOrder->key;
} else {
cout<<"Preorder successor of "<<root->left->right->key<<" is NULL";
}
return 0;
} Đầu ra
Preorder successor of 50 is 26