Contoh Coding Binary Search Tree C++
Hai teman teman
kali ini saya akan mengeshare tentang Coding untuk binary search tree
sebelumnya untuk lebih jelasnya kita review dulu yah tentang binary search tree.
secara sederhana :
sebuah binary search tree (bst) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. value pada semua node subpohon sebelah kiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing – masing subpohon tersebut (kiri&kanan)
tanpa basa basi untuk coding C++ nya sebagai berikut
#include<iostream>
#include<cstdlib>
using namespace std;
class BinarySearchTree{
private:
struct node{
node* left;
node* right;
int data;
};
node* root;
public:
BinarySearchTree(){
root = NULL;
}
bool isEmpty() const {return root==NULL;}
struct node* newNode(int data){
struct node* node = new(struct node);
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
struct node* insert(struct node* node, int data){
if(node == NULL){
return(newNode(data));
}
else{
if (data <= node->data) node->left = insert(node->left, data);
else node->right = insert(node->right, data);
return(node);
}
}
void insert(int data){
if(isEmpty()){
root = newNode(data);
}else{
insert(root,data);
}
}
void printTree(struct node* node){
if(node == NULL)return;
/*InOrder
printTree(node->left);
cout<<" "<<node->data;
printTree(node->right);
/*PreOrder
cout<<" "<<node->data;
printTree(node->left);
printTree(node->right);*/
/*PostOrder
printTree(node->left);
printTree(node->right);
cout<<" "<<node->data;*/
}
void callPrintTree(){
printTree(root);
}
int callLookup(int target){
return lookup(root,target);
}
int lookup(struct node* node,int target){
if(node==NULL) return 0;
if(node->data == target)return 1;
else{
if(target < node->data)
return lookup(node->left,target);
else
return lookup(node->right,target);
}
}
int callMin(){
return min(root);
}
int min(struct node* node){
if(node->left==NULL) return node->data;
else return min(node->left);
}
int callMax(){
return max(root);
}
int max(struct node* node){
if(node->right==NULL)return node->data;
else return max(node->right);
}
int callDept(){
return dept(root);
}
int dept(struct node* node){
if(node == NULL) return 0;
else{
int l = dept(node->left);
int r = dept(node->right);
if(l < r) return 1 + r;
else return 1 + l;
}
}
};
int main(){
BinarySearchTree b;
b.insert(5);
b.insert(3);
b.insert(9);
b.insert(1);
b.insert(4);
b.insert(6);
//b.callPrintTree();
cout<<b.callLookup(4)<<endl; //output : 1
cout<<b.callLookup(2)<<endl; //output : 0
cout<<b.callMin()<<endl; //output : 1
cout<<b.callMax()<<endl; //output : 9
cout<<b.callDept()<<endl; // output : 3
system("pause");
return 0;
}
sekian postingan dari saya
jangan lupa like commend dan share yah
terima kasih
