Trong bài toán này, chúng ta có một cây nhị phân và một nút. Nhiệm vụ của chúng ta là in phần kế tiếp thứ tự sau của nút trong cây nhị phân.
Nhị phân cây là một loại cây đặc biệt trong đó mỗi nút có thể có tối đa 2 nút con.
Truyền tải đơn hàng sau là một kỹ thuật duyệt cây, trong đó cây con bên trái đầu tiên được duyệt qua cây con bên phải và gốc được duyệt qua ở cuối.
duyệt theo thứ tự của cây ở trên: 8 4 2 7 9 6
Hãy lấy một ví dụ để hiểu vấn đề.
Đầu vào - cây nhị phân trong ví dụ trên, node =7
Đầu ra - 9
Giải thích - chúng ta có thể thấy nó trong trình duyệt thứ tự sau của cây nhị phân.
Để giải quyết vấn đề này, một giải pháp đơn giản, dễ dàng và của noob sẽ chỉ là tìm đường truyền của đơn hàng bưu điện và sau đó in số bên cạnh nó trong đường truyền.
Nhưng chúng ta cần tìm hiểu một giải pháp hiệu quả hơn,
Một giải pháp hiệu quả sẽ liên quan đến việc sử dụng một số quan sát chung về quá trình truyền đơn hàng.
-
Vì nút gốc là nút cuối cùng trong quá trình truyền theo thứ tự sau, người kế nhiệm của nó là NULL.
-
Trong trường hợp nút hiện tại là nút con bên phải, nút mẹ là nút kế thừa.
-
Trong trường hợp nút hiện tại là nút con bên trái, thì
-
Nếu anh chị em bên phải vắng mặt, nút kế thừa là nút cha
-
Nếu nút bên phải tồn tại thì nút hoặc nút con ngoài cùng bên trái của nó là nút kế nhiệm.
-
Phương pháp này có hiệu quả, độ phức tạp về thời gian là O (h), chiều cao của cây.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int value;
};
struct Node* insertNode(int value) {
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->value = value;
return temp;
}
Node* findPostorderSuccessor(Node* root, Node* n) {
if (n == root)
return NULL;
Node* parent = n->parent;
if (parent->right == NULL || parent->right == n)
return parent;
Node* curr = parent->right;
while (curr->left != NULL)
curr = curr->left;
return curr;
}
int main(){
struct Node* root = insertNode(6);
root->parent = NULL;
root->left = insertNode(2);
root->left->parent = root;
root->left->left = insertNode(8);
root->left->left->parent = root->left;
root->left->right = insertNode(4);
root->left->right->parent = root->left;
root->right = insertNode(9);
root->right->parent = root;
root->right->left = insertNode(7);
root->right->left->parent = root->right;
root->left->right->left = insertNode(14);
struct Node* successorNode = findPostorderSuccessor(root, root->left->right);
if (successorNode)
cout<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
else
cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
return 0;
} Đầu ra
Postorder successor of 4 is 2