Tìm nút thứ N trong duyệt preorder của cây nhị phân trong C++

Giới thiệu

Cho cây nhị phân và số nguyên N. Tìm nút thứ N trong thứ tự duyệt preorder (gốc - trái - phải).

Ví dụ minh họa

Đầu vào

N = 6

Đầu ra

6

Giải thích

Preorder: 1, 2, 4, 5, 3, 6, 7 → phần tử thứ 6 là 6

Phương pháp giải: Đệ quy preorder với bộ đếm

Duyệt preorder đệ quy: thăm gốc, tăng bộ đếm, kiểm tra N, sau đó đệ quy trái và phải.

Chương trình minh họa

#include <iostream>
using namespace std;

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

Node* createNode(int item) {
    Node* temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}

void findPreOrderTraversalRec(Node* root, int N) {
    static int nodeCount = 0;
    if (!root) return;
    if (nodeCount <= N) {
        nodeCount++;
        if (nodeCount == N)
            cout << root->data;
        findPreOrderTraversalRec(root->left, N);
        findPreOrderTraversalRec(root->right, N);
    }
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    int N = 6;
    cout << N << "th node in preorder traversal is ";
    findPreOrderTraversalRec(root, N);
    return 0;
}

Đầu ra

6th node in preorder traversal is 6