Implementasi BST dalam high score game
Nama : Fakhrian Elanta
NRP : 5025251019
Kelas : Struktur Data D
Full code :
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
/* Node structure */
struct BSTNode {
BSTNode *left, *right;
int key;
};
/* uniqueBST */
struct BST {
// Member
BSTNode *_root;
unsigned int _size;
// Function
void init() {
_root = NULL;
_size = 0u;
}
bool isEmpty() {
return _root == NULL;
}
bool find(int value) {
BSTNode *temp = __search(_root, value);
if (!temp)
return false;
if (temp->key == value)
return true;
else
return false;
}
void insert(int value) {
if (!find(value)) {
_root = __insert(_root, value);
_size++;
}
}
void remove(int value) {
if (find(value)) {
_root = __remove(_root, value);
_size++;
}
}
void traverseInorder() {
__inorder(_root);
}
void traversePreorder() {
__preorder(_root);
}
void traversePostorder() {
__postorder(_root);
}
int maxnode(){
if (isEmpty()) {
return -1;
}
BSTNode* maxNode = __findMaxNode(_root);
return maxNode->key;
}
private:
// Utility Function
BSTNode* __createNode(int value) {
BSTNode *newNode = (BSTNode*) malloc(sizeof(BSTNode));
newNode->key = value;
newNode->left = newNode->right = NULL;
return newNode;
}
BSTNode* __search(BSTNode *root, int value) {
while (root != NULL) {
if (value < root->key)
root = root->left;
else if (value > root->key)
root = root->right;
else
return root;
}
return root;
}
BSTNode* __insert(BSTNode *root, int value) {
if (root == NULL)
return __createNode(value);
if (value < root->key)
root->left = __insert(root->left, value);
else if (value > root->key)
root->right = __insert(root->right, value);
return root;
}
BSTNode* __findMinNode(BSTNode *node) {
BSTNode *currNode = node;
while (currNode && currNode->left != NULL)
currNode = currNode->left;
return currNode;
}
BSTNode* __findMaxNode(BSTNode *node) {
BSTNode *currNode = node;
while (currNode && currNode->right != NULL)
currNode = currNode->right;
return currNode;
}
BSTNode* __remove(BSTNode *root, int value) {
if (root == NULL) return NULL;
if (value > root->key)
root->right = __remove(root->right, value);
else if (value < root->key)
root->left = __remove(root->left, value);
else {
if (root->left == NULL) {
BSTNode *rightChild = root->right;
free(root);
return rightChild;
}
else if (root->right == NULL) {
BSTNode *leftChild = root->left;
free(root);
return leftChild;
}
BSTNode *temp = __findMinNode(root->right);
root->key = temp->key;
root->right = __remove(root->right, temp->key);
}
return root;
}
void __inorder(BSTNode *root) {
if (root) {
__inorder(root->left);
printf("%d ", root->key);
__inorder(root->right);
}
}
void __postorder(BSTNode *root) {
if (root) {
__postorder(root->left);
__postorder(root->right);
printf("%d ", root->key);
}
}
void __preorder(BSTNode *root) {
if (root) {
printf("%d ", root->key);
__preorder(root->left);
__preorder(root->right);
}
}
};
int main(int argc, char const *argv[])
{
BST set;
set.init();
int N;
cout<<"Masukkan banyaknya skor yang ingin dimasukkan: ";
cin>>N;
while(N--){
cout<<"Masukkan skor: ";
int x;
cin>>x;
set.insert(x);
}
cout<<"Skor tertinggi adalah: ";
int bigest = set.maxnode();
cout<<bigest<<endl;
}
Kode memasukan berapa banyak data yang ingin dimasukan dan mencari nilai tertinggi dengan cara traverse ke kanan terus menerus sampai menemui nilai max dari BST itu sendiri. Inisialisasi BST dengan struct yang memiliki anggota key, left dan right, untuk setiap anggota yang lebih kecil dari key saat ini maka akan dimasukan menuju left dan yang lebih besar akan dimasukkan menuju right, di dalam kode pun juga terdapat beberapa fungsi traversal yang bisa digunakan, yakn inorder, postorder dan preorder
Komentar
Posting Komentar