In đường đi giữa hai nút bất kỳ trong cây nhị phân (C++)

Cho một cây nhị phân các nút phân biệt và hai nút bất kỳ, in đường đi giữa hai nút đó trong cây.

Ví dụ – In đường đi từ nút 140 đến 211, đầu ra:

Output: 140->3->10->211

Ý tưởng: tìm đường từ gốc đến hai nút, lưu vào hai vector path1 và path2.

Có hai trường hợp:

• Hai nút ở hai cây con khác nhau của gốc – Một ở trái, một ở phải. Gốc nằm giữa đường đi. In path1 ngược rồi in path2.

• Hai nút ở cùng một cây con – Cả hai ở trái hoặc cả hai ở phải. Đường từ gốc đến hai nút có điểm giao trước đó đường chung. Tìm điểm giao và in từ điểm đó như trường hợp trên.

Thuật toán

BẮT ĐẦU
BƯỚC 1: ĐỊNH NGHĨA struct Node VỚI int data, Node *left, *right
BƯỚC 2: HÀM struct Node* tree(int data) TẠO NÚT MỚI
HÀM bool path(Node* root, vector& arr, int x)
    BƯỚC 1: NẾU root NULL TRẢ VỀ false
    BƯỚC 2: arr.push_back(root->data)
    NẾU root->data == x TRẢ VỀ true
    BƯỚC 3: NẾU path(root->left, arr, x) HOẶC path(root->right, arr, x) TRẢ VỀ true
    BƯỚC 4: arr.pop_back(), TRẢ VỀ false
HÀM void printPath(Node* root, int n1, int n2)
    BƯỚC 1: KHAI BÁO vector<int> path1, path2
    BƯỚC 2: GỌI path(root, path1, n1)
    BƯỚC 3: GỌI path(root, path2, n2)
    BƯỚC 4: intersection = -1, i = 0, j = 0
    BƯỚC 5: WHILE i != path1.size() HOẶC j != path2.size()
        NẾU i == j VÀ path1[i] == path2[j] THÌ i++, j++
        NGƯỢC LẠI intersection = j - 1, BREAK
    BƯỚC 6: FOR i = path1.size()-1 ĐẾN i > intersection, i-- IN path1[i]
    BƯỚC 7: FOR i = intersection ĐẾN i < path2.size(), i++ IN path2[i]

Ví dụ mã C++

#include <bits/stdc++.h> 
using namespace std; 

struct Node { 
    int data; 
    Node *left, *right; 
}; 

struct Node* tree(int data) { 
    struct Node* newNode = new Node; 
    newNode->data = data; 
    newNode->left = newNode->right = NULL; 
    return newNode; 
} 

bool path(Node* root, vector<int>& arr, int x) { 
    if (!root) return false; 
    arr.push_back(root->data); 
    if (root->data == x) return true; 
    if (path(root->left, arr, x) || path(root->right, arr, x)) return true; 
    arr.pop_back(); 
    return false; 
} 

void printPath(Node* root, int n1, int n2) { 
    vector<int> path1, path2; 
    path(root, path1, n1); 
    path(root, path2, n2); 
    int intersection = -1, i = 0, j = 0; 
    while (i != path1.size() || j != path2.size()) { 
        if (i == j && path1[i] == path2[j]) { i++; j++; } 
        else { intersection = j - 1; break; } 
    } 
    for (int i = path1.size() - 1; i > intersection; i--) 
        cout << path1[i] << " "; 
    for (int i = intersection; i < path2.size(); i++) 
        cout << path2[i] << " "; 
} 

int main() { 
    struct Node* root = tree(1); 
    root->left = tree(2); 
    root->left->left = tree(4); 
    root->left->left->left = tree(6); 
    root->left->right = tree(5); 
    root->left->right->left = tree(7); 
    root->left->right->right = tree(8); 
    root->right = tree(3); 
    root->right->left = tree(9); 
    root->right->right = tree(10); 
    int node1 = 5, node2 = 9; 
    printPath(root, node1, node2); 
    return 0; 
}

Kết quả

Chương trình in ra:

5 2 1 3 9