program binary tree c++
Berikut source code program binary tree c++:
#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
using namespace std;
struct tree_node{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;
bool isEmpty()
{return root==NULL;}
void insert(int d) {
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
if(isEmpty())root = t;
else {
tree_node* curr;
curr = root;
while(curr!=NULL)
{
parent = curr;
if(t->data
> curr->data) curr = curr->right;
else curr =
curr->left;
}
if(t->data <
parent->data)
parent->left = t;
else
parent->right = t;
}}
void inorder(tree_node* p) {
if(p!=NULL) {
if(p->left)
inorder(p->left);
cout<<"
"<<p->data<<" ";
if(p->right)
inorder(p->right);
} else
return;
}
void print_inorder() {
inorder(root);
}
void preorder(tree_node* p) {
if(p!=NULL) {
cout<<"
"<<p->data<<" ";
if(p->left)
preorder(p->left);
if(p->right)
preorder(p->right);
} else
return;
}
void print_preorder() {
preorder(root);
}
void postorder(tree_node* p) {
if(p!=NULL) {
if(p->left)
postorder(p->left);
if(p->right)
postorder(p->right);
cout<<"
"<<p->data<<" ";
} else
return;
}
void print_postorder() {
postorder(root);
}
int count(tree_node* p) {
if(p==NULL)return 0;
return count(p->right) + count(p->left) + 1;
}
int height(tree_node* p) {
if(p==NULL) return 0;
int u = height(p->left),v = height(p->right);
if(u > v)
return u+1;
else
return v+1;
}
void cari_terbesar(tree_node* p) {
if(p==NULL)
return;
else
if(p->right==NULL) {
cout<<"
"<<p->data<<" ";
return;
}
else {
cari_terbesar(p->right);
return;
}}
void cari_terkecil(tree_node* p) {
if(p==NULL)
return;
else
if(p->left==NULL) {
cout<<"
"<<p->data<<" ";
return;
}
else {
cari_terkecil(p->left);
return;
}}
int main() {
root=NULL;
int ch;
int tmp;
while(1) {
system("cls");
cout<<endl;
cout<<"BINARY TREE"<<endl;
cout<<"==========="<<endl;
cout<<"1. Insert (Tambah) Data"<<endl;
cout<<"2. Lihat secara In-Order"<<endl;
cout<<"3. Lihat secara Pre-Order"<<endl;
cout<<"4. Lihat secara Post-Order"<<endl;
cout<<"5. Hitung jumlah node"<<endl;
cout<<"6.
Hitung tinggi tree"<<endl;
cout<<"7. Mencari Data Terbesar"<<endl;
cout<<"8. Mencari Data Terkecil"<<endl;
cout<<"9. Exit"<<endl;
cout<<"Pilihan Anda : ";
cin>>ch;
cout<<endl;
switch(ch) {
case 1 :
cout<<"Masukkan Data :";
cin>>tmp;
insert(tmp);
break;
case 2:
cout<<endl;
cout<<"Tampil secara In-Order"<<endl;
cout<<"--------------------------"<<endl;
print_inorder();
getch();
break;
case 3:
cout<<endl;
cout<<"Tampil secara Pre-Order"<<endl;
cout<<"------------------------"<<endl;
print_preorder();
getch();
break;
case 4:
cout<<"Tampil secara Post-Order"<<endl;
cout<<"----------------------------------"<<endl;
print_postorder();
getch();
break;
case 5:
cout<<"Hitung jumlah node"<<endl;
cout<<"---------------------------"<<endl;
cout<<"Jumlah Node = "<<count(root);
getch();
break;
case 6:
cout<<"Hitung tinggi tree"<<endl;
cout<<"---------------------------"<<endl;
cout<<"Tinggi tree = "<<height(root);
getch();
break;
case 7:
cout<<"Mencari Data Terbesar"<<endl;
cout<<"------------------------------"<<endl;
cout<<"Data terbesar adalah = "<<endl;
cari_terbesar(root);
getch();
break;
case 8:
cout<<"Mencari Data Terkecil"<<endl;
cout<<"------------------------------"<<endl;
cout<<"Data terkecil adalah = "<<endl;
cari_terkecil(root);
getch();
break;
case 9: return 0;
break;
default:
cout<<"Pilihan salah!"<<endl;
getch();
break;
}}}
Output program
Tambah data
Lihat secara In Order
Lihat secara Pre Order
Lihat secara Post Order
Jumlah Node
Tinggi tree
Mencari data terbesar
Mencari data terkecil
Algoritma program
·
Pendeklarasian variabel item, pointer ke subtree
left dan pointer ke subtree right.
·
Pengecekan binary tree dalam kondisi kosong atau
tidak.
·
Pengecekan dilakukan pada variabel root.
·
Jika root menunjuk null, kondisi kosong dan
mengembalikan nilai true. Sebaliknya jika root tidak menunjuk null berarti
kondisi binary tree tidak kosong dan mengembalikan nilai false.
·
Untuk menambahkan data
-
Inisilaisasi awal node yang baru dibuat
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
-
Cek apakah root masih kosong, jika ya lanjutkan
proses dibawahnya yaitu
-
Cek apakah t->data < parent->data
Jika ya, (sebagai cabang kanan) curr=curr->right
Jika tidak, (sebagai cabang kiri) curr=curr->left
-
Cek apakah t->data < parent->data
Jika ya, (sebagai cabang kiri) parent->left=t
Jika tidak, (sebagai cabang kanan) parent->right=t
·
Untuk mencetak data dengan kunjungan in order
-
Cek apakah p!=NULL, jika ya lanjutkan proses
dibawahnya yaitu
-
Panggil fungsi: inorder(p->left)
-
Cetak p->data
-
Panggil fungsi: inorder(p->right)
·
Untuk mencetak data dengan kunjungan pre order
-
Cek apakah p!=NULL, jika ya lanjutkan proses
dibawahnya yaitu
-
Cetak p->data
-
Panggil fungsi: preorder(p->left)
-
Panggil fungsi: preorder(p->right)
·
Untuk mencetak data dengan kunjungan post order
-
Cek apakah p!=NULL, jika ya lanjutkan proses
dibawahnya yaitu
-
Panggil fungsi: postorder(p->left)
-
Panggil fungsi: postorder(p->right)
-
Cetak p->data
·
Untuk mengetahui jumlah node dalam tree
-
Menghitung root subtree kiri kemudian subtree
kanan dan masing-masing node dicatat jumlahnya.
-
Jumlah node yang ada di subtree kiri dijumlahkan
dengan jumlah node yang ada di subtree kanan ditambah 1 yaitu node root.
·
Untuk mengetahui kedalaman node tree
-
Penghitungan kedalaman dihitung dari setelah
root, yang dimulai dari subtree kiri kemudian subtree kanan.
-
Untuk masing-masing kedalaman kiri dan kanan
akan dibandingkan.
-
Kedalaman yang dipakai adalah bagian subtree
yang lebih dalam.
·
Untuk mencari data terbesar
-
Cek apakah p==NULL, jika tidak lanjutkan proses
dibawahnya yaitu
-
Jika p->right==NULL, cetak p->data
-
Atau bisa juga panggil fungsi: cari_terbesar(p->right)
·
Untuk mencari data terkecil
-
Cek apakah p==NULL, jika tidak lanjutkan proses
dibawahnya yaitu
-
Jika p->left==NULL,
cetak p->data
-
Atau bisa juga panggil fungsi: cari_terkecil(p->left)
Referensi :
https://sayfudinblogz.blogspot.com/2013/06/algoritma-dan-struktur-data-binary-tree.html 
Komentar
Posting Komentar