Cây nhị phân triển khai mảng C++

Biểu diễn cây nhị phân bằng mảng. Chỉ số 0-based: gốc tại 0, con trái 2*i+1, con phải 2*i+2. Chỉ số 1-based: gốc tại 1, con trái 2*i, con phải 2*i+1.

Triển khai mảng 0-based

Mảng char tree[10]. Hàm setRoot, setLeft, setRight kiểm tra cha tồn tại. Duyệt in mảng (ký tự hoặc '-' cho rỗng).

Ví dụ minh họa

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

char tree[10];

void setRoot(char key) {
    if (tree[0] != '\0') cout << "Da co goc";
    else tree[0] = key;
}

void setLeft(char key, int parent) {
    if (tree[parent] == '\0')
        cout << "\nKhong the dat con tai " << (parent*2+1) << ", khong co cha";
    else
        tree[parent*2+1] = key;
}

void setRight(char key, int parent) {
    if (tree[parent] == '\0')
        cout << "\nKhong the dat con tai " << (parent*2+2) << ", khong co cha";
    else
        tree[parent*2+2] = key;
}

void printTree() {
    cout << "\n";
    for (int i = 0; i < 10; i++)
        cout << (tree[i] ? tree[i] : '-');
}

int main() {
    setRoot('A');
    setRight('C', 2);  // loi: cha 2 chua co
    setLeft('D', 0);
    setRight('E', 1);
    setRight('F', 2);  // loi
    printTree();  // AD--E-----
    return 0;
}

Kết quả

Khong the dat con tai 6, khong co cha
Khong the dat con tai 6, khong co cha
AD--E-----