Tree Implementation
Pada blog ini akan membahas terkait implementasi tree dalam bahasa C++.
Implementasi Dasar
#include <bits/stdc++.h>
using namespace std;
struct Node{
char data;
Node *left, *right;
Node (char val){
data = val;
left=right=NULL;
}
};
void preorder(Node *root){
if(root == NULL) return;
cout << root->data<<" ";
preorder(root->left);
preorder(root->right);
}
void inorder(Node *root){
if(root == NULL) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
void postorder(Node *root){
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
void levelorder(Node *root){
if(root == NULL) return;
queue<Node*> q;
q.push(root);
while (!q.empty()){
Node *current = q.front();
q.pop();
cout << current->data << " ";
if (current->left != NULL) q.push(current->left);
if (current->right != NULL) q.push(current->right);
}
}
int main(void){
Node *root = new Node('A');
root->left = new Node('B');
root->right = new Node('C');
root->left->left = new Node('D');
root->left->right = new Node('E');
root->right->right = new Node('F');
cout << "Preorder : ";
preorder(root);
cout << "\nInorder : ";
inorder(root);
cout << "\nPostorder : ";
postorder(root);
cout << "\nLevelOrder: ";
levelorder(root);
return 0;
}
- Pertama-tama yang harus dilakukan adalah mendeklarasikan node yang berisi data beserta node kiri dan node kanan. Berikut adalah structurenya
struct Node{
char data;
Node *left, *right;
Node (char val){
data = val;
left=right=NULL;
}
};
- Selanjutnya juga perlu membuat fungsi untuk menampilkan node secara preorder yaitu mengunjungi tree mulai dari root, lalu ke sub-tree kiri, dan diakhiri ke sub-tree kanan (Root-Left-Right).
void preorder(Node *root){
if(root == NULL) return;
cout << root->data<<" ";
preorder(root->left);
preorder(root->right);
}
- Menampilkan node secara inorder yaitu mengunjungi tree mulai dari sub-tree kiri, lalu ke root, dan diakhiri ke sub-tree kanan (Left-Root-Right).
void inorder(Node *root){
if(root == NULL) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
- Menampilkan node secara postorder yaitu mengunjungi tree mulai dari sub-tree kiri, lalu ke sub-tree kanan, dan diakhiri ke root(Left-Right-Root).
void postorder(Node *root){
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
- Yang terakhir ditampilkan secara levelorder yaitu mengunjungi tree lapis demi lapis mulai dari tingkat teratas hingga terbawah secara berurutan dari kiri ke kanan.
void levelorder(Node *root){
if(root == NULL) return;
queue<Node*> q;
q.push(root);
while (!q.empty()){
Node *current = q.front();
q.pop();
cout << current->data << " ";
if (current->left != NULL) q.push(current->left);
if (current->right != NULL) q.push(current->right);
}
}
Berikut adalah program utamanya
int main(void){
Node *root = new Node('A');
root->left = new Node('B');
root->right = new Node('C');
root->left->left = new Node('D');
root->left->right = new Node('E');
root->right->right = new Node('F');
cout << "Preorder : ";
preorder(root);
cout << "\nInorder : ";
inorder(root);
cout << "\nPostorder : ";
postorder(root);
cout << "\nLevelOrder: ";
levelorder(root);
return 0;
}
Jika program dijalankan, maka outputnya akan sebagai berikut
Source code
https://github.com/xbggnr/Tree-Implementation.git
-- Terimakasih --
Komentar
Posting Komentar