Chương trình C++ in đường đi từ gốc đến nút cho trước trong cây nhị phân

In đường đi từ gốc đến nút cho trước trong cây nhị phân. Cây có nút phân biệt, tìm đường đến nút x.

Dùng đệ quy: duyệt cây, tìm nút x, lưu đường đi trong vector. Tìm thấy thì trả true, không thì pop_back và trả false.

Ví dụ mã nguồn

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

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

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

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

void print_path(Node *root, int x) {
    vector<int> arr;
    if (is_path(root, arr, x)) {
        for (int i = 0; i < arr.size() - 1; i++)
            cout << arr[i] << " -> ";
        cout << arr[arr.size() - 1];
    } else
        cout << "Path doesn't exist" << endl;
}

int main() {
    struct Node *root = create_node(13);
    root->left = create_node(21);
    root->right = create_node(43);
    root->left->left = create_node(34);
    root->left->right = create_node(55);
    root->right->left = create_node(68);
    root->right->right = create_node(79);
    int x = 68;
    print_path(root, x);
    return 0;
}

Kết quả đầu ra

13 -> 43 -> 68