Binary Tree แบบ Array Implementation ใน C++

การแทน Binary Tree ด้วย Array

มี 2 วิธี: 1) Dynamic (Linked List) 2) Sequential (Array)

Indexing แบบ 0-based

• Parent index = p
• Left child = 2p + 1
• Right child = 2p + 2
• Root = index 0

Indexing แบบ 1-based

• Parent index = p
• Left child = 2p + 1
• Right child = 2p
• Root = index 1

ตัวอย่างโค้ด C++ (0-based)

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

char tree[10];

int rootnode(char key) {
    if (tree[0] != '\0') cout << "Tree already had root";
    else tree[0] = key;
    return 0;
}

int leftchild(char key, int parent) {
    if (tree[parent] == '\0')
        cout << "\nCan't set child at " << (parent * 2) + 1 << " , no parent found";
    else
        tree[(parent * 2) + 1] = key;
    return 0;
}

int rightchild(char key, int parent) {
    if (tree[parent] == '\0')
        cout << "\nCan't set child at " << (parent * 2) + 2 << " , no parent found";
    else
        tree[(parent * 2) + 2] = key;
    return 0;
}

int traversetree() {
    cout << "\n";
    for (int i = 0; i < 10; i++) {
        if (tree[i] != '\0') cout << tree[i];
        else cout << "-";
    }
    return 0;
}

int main() {
    rootnode('A');
    rightchild('C', 2);
    leftchild('D', 0);
    rightchild('E', 1);
    rightchild('F', 2);
    traversetree();
    return 0;
}

ผลลัพธ์

Can't set child at 6 , no parent found
Can't set child at 6 , no parent found
AD--E-----