In nút trái nhất và phải nhất của cây nhị phân trong C

Cho cây nhị phân, in ra các nút góc (leftmost và rightmost) trên mỗi cấp độ của cây.

Ví dụ

Input: 106 20 320 100 21 61 52
Output: 106 20 320 100 52

Thuật toán (BFS theo cấp độ)

BẮT ĐẦU
BƯỚC 1: CẤU TRÚC NÚT (data, left, right)
BƯỚC 2: HÀM newNode(val) TẠO NÚT MỚI
BƯỚC 3: HÀM print(node* root)
    NẾU root == NULL TRẢ VỀ
    queue<node*> que; que.push(root)
    vector ans
    KHI !que.empty() LẶP
        n = que.size()
        VỚI i=0 ĐẾN i<n, i++
            temp = que.front(); que.pop()
            NẾU i==0 HOẶC i==n-1 THÌ ans.push_back(temp->data)
            NẾU temp->left THÌ que.push(temp->left)
            NẾU temp->right THÌ que.push(temp->right)
        KẾT THÚC VỚI
    KẾT THÚC KHI
    IN các phần tử trong ans
BƯỚC 4: MAIN() TẠO CÂY, GỌI print(root)
KẾT THÚC

Chương trình C++ ví dụ

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

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

struct node* newNode(int val) {
    node* temp = new node;
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}

void print(node* root) {
    if (root == NULL) return;
    queue que;
    que.push(root);
    vector ans;
    while (!que.empty()) {
        int n = que.size();
        for (int i = 0; i < n; i++) {
            node* temp = que.front(); que.pop();
            if (i == 0 || i == n-1)
                ans.push_back(temp->data);
            if (temp->left) que.push(temp->left);
            if (temp->right) que.push(temp->right);
        }
    }
    for (auto i : ans) cout << i << " ";
}

int main() {
    node* root = newNode(106);
    root->left = newNode(20);
    root->right = newNode(320);
    root->left->left = newNode(100);
    root->left->right = newNode(21);
    root->right->left = newNode(61);
    root->right->right = newNode(52);
    print(root);
    return 0;
}

Kết quả

106 20 320 100 52