Contoh Coding Binary Search Tree C++

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