In các nút của cây nhị phân khi chúng trở thành nút lá trong C++

Cho một cây nhị phân, ta phải in các nút lá, sau đó xóa các nút lá đó và lặp lại cho đến khi không còn nút nào trong cây.

Ví dụ

Kết quả đầu ra của bài toán:

6 7 9 13 14 3 4 2 1

Phương pháp

Ta dùng phương pháp DFS (tìm kiếm theo chiều sâu).

Gán giá trị tạm 0 cho mọi nút, sau đó gán cho mỗi nút giá trị max(giá trị hai con) + 1.

Thuật toán

BẮT ĐẦU
BƯỚC 1: ĐỊNH NGHĨA struct Node VỚI THÀNH VIÊN data, order, *left, *right
BƯỚC 2: ĐỊNH NGHĨA HÀM struct Node* newNode(int data, int order)
    KHỞI TẠO node, GÁN data, order, left=NULL, right=NULL, TRẢ VỀ node
HÀM void postod(struct Node* node, vector<pair<int, int> >& v)
    BƯỚC 1: NẾU node == NULL THÌ TRẢ VỀ
    BƯỚC 2: GỌI postod(node->left, v)
    BƯỚC 3: GỌI postod(node->right, v)
    BƯỚC 4: NẾU node->right == NULL VÀ node->left == NULL THÌ
        GÁN node->order = 1
        v.push_back(make_pair(node->order, node->data))
        NGƯỢC LẠI
        node->order = max((node->left)->order, (node->right)->order) + 1
        v.push_back(make_pair(node->order, node->data))
    KẾT THÚC IF
HÀM void printLeafNodes(int n, vector<pair<int, int> >& v)
    BƯỚC 1: sort(v.begin(), v.end())
    BƯỚC 2: VỚI i = 0 ĐẾN i < n, i++
        NẾU v[i].first == v[i+1].first THÌ IN v[i].second
        NGƯỢC LẠI IN v[i].second
    KẾT THÚC VỚI
TRONG main()
    BƯỚC 1: TẠO NÚT GỐC struct Node* root = newNode(8, 0)
    BƯỚC 2: KHAI BÁO VÀ GÁN n = 9
    BƯỚC 3: GỌI postod(root, v)
    BƯỚC 4: GỌI printLeafNodes(n, v)

Ví dụ mã C++

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

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

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

void postod(struct Node* node, vector<pair<int, int> >& v) { 
    if (node == NULL) 
        return; 
    postod(node->left, v); 
    postod(node->right, v); 
    if (node->right == NULL && node->left == NULL) { 
        node->order = 1; 
        v.push_back(make_pair(node->order, node->data)); 
    } else { 
        node->order = max((node->left)->order, (node->right)->order) + 1; 
        v.push_back(make_pair(node->order, node->data)); 
    } 
} 

void printLeafNodes(int n, vector<pair<int, int> >& v) { 
    sort(v.begin(), v.end()); 
    for (int i = 0; i < n; i++) { 
        if (v[i].first == v[i + 1].first) 
            cout << v[i].second << " "; 
        else 
            cout << v[i].second << "\n"; 
    } 
} 

int main() { 
    struct Node* root = newNode(1, 0); 
    root->left = newNode(2, 0); 
    root->right = newNode(3, 0); 
    root->left->left = newNode(4, 0); 
    root->left->right = newNode(6, 0); 
    root->right->left = newNode(14, 0); 
    root->right->right = newNode(9, 0); 
    root->left->left->left = newNode(7, 0); 
    root->left->left->right = newNode(13, 0); 
    int n = 9; 
    vector<pair<int, int> > v; 
    postod(root, v); 
    printLeafNodes(n, v); 
    return 0; 
}

Kết quả

Chương trình sẽ in ra:

6 7 9 13 14 3 4 2 1