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 tiền đặt hàng trước của nút.
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 tiền nhiệm là nút đến trước 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: 1 Output: 9
Để giải quyết vấn đề này, hãy điều hướng phương pháp tiếp cận sẽ là tìm duyệt đặt hàng 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ố nhất định và sau đó tìm kiếm tiền thân của nó dựa trên các vị trí. Nếu nút là nút gốc, thì trả về NULL, không có tiền nhiệm. Nếu nút là nút con bên phải, thì nút con bên trái sẽ là nút tiền nhiệm.
Chương trình hiển thị việc thực hiện 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<<"Preorder Predecessor of "<<root->left->right->key<<" is "<<preOrderPredecessor->key;
else
cout<<"Preorder Predecessor of "<<root->left->right->key<<" is NULL";
return 0;
} Đầu ra
Preorder Predecessor of 50 is 18