Tìm nút K-th trong duyệt chéo của cây nhị phân trong C++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm nút thứ K trong duyệt chéo (diagonal traversal) của cây nhị phân.

Các bước giải quyết

• Khởi tạo cây nhị phân với dữ liệu mẫu.
• Khởi tạo số K.
• Duyệt cây nhị phân theo đường chéo sử dụng hàng đợi (queue):
  • Giảm K trên mỗi nút.
  • Trả về nút khi K bằng 0.
• Trả về -1 nếu không tìm thấy nút.

Ví dụ

Dưới đây là mã nguồn C++:

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

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

Node* getNewNode(int data) { 
    Node* node = (Node*)malloc(sizeof(Node)); 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 

int findDiagonalKthElement(Node* root, int k) { 
    if (root == NULL || k == 0) { 
        return -1; 
    } 
    int result = -1; 
    queue<Node*> q; 
    q.push(root); 
    q.push(NULL); 
    while (!q.empty()) { 
        Node* temp = q.front(); 
        q.pop(); 
        if (temp == NULL) { 
            if (q.empty()) { 
                if (k == 0) { 
                    return result; 
                } else { 
                    break; 
                } 
            } 
            q.push(NULL); 
        } else { 
            while (temp) { 
                if (k == 0) { 
                    return result; 
                } 
                k--; 
                result = temp->data; 
                if (temp->left) { 
                    q.push(temp->left); 
                } 
                temp = temp->right; 
            } 
        } 
    } 
    return -1; 
} 

int main() { 
    Node* root = getNewNode(10); 
    root->left = getNewNode(5); 
    root->right = getNewNode(56); 
    root->left->left = getNewNode(3); 
    root->left->right = getNewNode(22); 
    root->right->right = getNewNode(34); 
    root->right->right->left = getNewNode(45); 
    root->left->right->left = getNewNode(67); 
    root->left->right->right = getNewNode(100); 
    int k = 9; 
    cout << findDiagonalKthElement(root, k) << endl; 
    return 0; 
}

Kết quả

Nếu bạn chạy mã trên, kết quả sẽ là:

67

Kết luận

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.