POHON BINER (LANJUTAN)
Pohon (Tree) adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan kedua simpul di dalam pohon. Pohon dilengkapi dengan Root (akar).
Pohon biner terbuat dari node, di mana setiap node berisi pointer "kiri", pointer "kanan", dan elemen data. Pointer "root" menunjuk ke simpul paling atas di pohon. Pointer kiri dan kanan secara rekursif menunjuk ke "subtree" yang lebih kecil di kedua sisi. Pointer nol menunjukkan pohon biner tanpa elemen - pohon kosong. Definisi rekursif formal adalah: pohon biner baik kosong (diwakili oleh pointer nol), atau terbuat dari satu node, di mana pointer kiri dan kanan (definisi rekursif di depan) setiap titik ke pohon biner.
Pohon pencarian biner (BST) atau "tree binary berurutan" adalah jenis pohon biner di mana node disusun secara berurutan: untuk setiap node, semua elemen di subtree kirinya kurang dari node ( <), dan semua elemen di subtree kanannya lebih besar dari node (>).
5
/ \
3 6
/ \ \
1 4 9 Pohon yang ditunjukkan di atas adalah pohon pencarian biner - simpul "root" adalah 5, dan simpul subtree kirinya (1, 3, 4) adalah <5, dan simpul subtree kanannya (6, 9) adalah> 5. Secara rekursif, masing-masing subtree juga harus mematuhi batasan pohon pencarian biner: pada subtree (1, 3, 4), 3 adalah root, 1 <3 dan 4> 3.
I. Proses
a. Inisialisasi
b. Pembuatan sebuah simpul
c. Pembuatan simpul akar
d. Penambahan (insert) simpul kedalam sebuah pohon
e. Penghapusan (delete) simpul dari sebuah pohon
f. Pembacaan/penelusuran pohon biner
II. Deklarasi simpul
struct Node{
int INFO;
struct Node *LEFT;
struct Node *RIGHT;
};
Node *ROOT, *P, *Q, *R;
III. Proses Inisialisasi
void Inisialisasi()
{
ROOT=NULL;
P=NULL;
}
IV. Pembuatan sebuah simpul
void BuatSimpul(int x)
{
P=(Node *)malloc(sizeof(Node));
if(P!=NULL)
{
P->INFO=x;
P->LEFT=NULL;
P->RIGHT=NULL;
}
else
cout<<”Pembuatan simpul gagal”;
}
V. Menjadikan sebuah simpul menjadi simpul akar
void BuatSimpulAkar(void){
if(ROOT==NULL){
if(P!=NULL){
ROOT=P;
ROOT->LEFT=NULL;
ROOT->RIGHT=NULL;
}
else
cout<<”Simpul Belum Dibuat”;
}
else
cout<<”Root sudah ada”;
}
VI. Menambahkan simpul ke pohon yang sudah ada
VI.a. Insert urut nomor simpul/level per level
0 komentar: