Tree

Apa itu tree? tree adalah struktur data, dimana bentuknya menyerupai tree (perumpamaan saja), aslinya structur data ini berbentuk mirip linkedlists-double hanya saja, perumpamaan cabang kiri (diganti dgn nama prev), cabang kanan (diganti dgn nama next)

Perbedaan

• Linkedlists itu monoton, alias saling sambung menyambung dan flat.
• sedangkan tree tidak ada aturan harus saling menyambung, bisa saja linkedlists nya seperti ini

root -> next -> next -> next (dimana ini nanti akan membuat tree yang gambar visualnya bakal menjorok kekanan)

jenis jenis transversal

• preorder (root, kiri, lalu ke-kanan)
• inorder (kiri, root, lalu ke-kanan)
• postorder (kiri, kanan, lalu ke-root)

nb: tranversal adalah cara mengunjungi simpul (tepat satu kali saja)

coding

sudah cukup hal non teknisnya, bagian ini akan membahas bagian koding

struct

struct untuk tree sangat mirip dgn struct untuk linked-list-double. di kasus ini struct dibawah hanya bisa hold data char saja. bisa diganti juga dgn int. dan lain lain

struct ListNode {
        char val;
        ListNode *prev;
        ListNode *next;

        ListNode(char x) : val(x), prev(nullptr), next(nullptr) {}
};

terlihat? selain hold data val yang isinya char, kita ada opsi untuk hold pointer prev dan pointer next. dimana ini adalah kunci dari tree.

contoh meng-isinya

ada tree seperti ini

ini contoh cara mengisinya

ListNode *head = new ListNode('A');
head->prev = new ListNode('B');
head->prev->prev = new ListNode('D');
head->prev->prev->next = new ListNode('G');

head->next = new ListNode('C');
head->next->next = new ListNode('F');
head->next->prev = new ListNode('E');
head->next->prev->prev = new ListNode('H');
head->next->prev->next = new ListNode('I');

kenapa tidak pakai val? karna ketika kita new ListNode('H');, secara otomatis kita mengisi val. val baru dipakai ketika mau diakses.

contoh cara mengaksesnya

contoh singkat ada dibawah, contoh (komplit) nya silahkan klik disini

inorder

cout << "step 1: " << head->prev->prev->next->val <<
" " << head->prev->prev->val <<
" " << head->prev->val <<
" " << head->val <<
" " << head->next->prev->prev->val <<
" " << head->next->prev->val <<
 " " << head->next->prev->next->val <<
 " " << head->next->val <<
" " << head->next->next->val <<
endl;

postorder

cout << "step 9: " << head->prev->prev->next->val << 
" " << head->prev->prev->val << 
" " << head->prev->val << 
" " << head->next->prev->prev->val << 
" " << head->next->prev->next->val << 
" " << head->next->prev->val << 
" " << head->next->next->val <<
" " << head->next->val <<
" " << head->val <<

endl;

preorder

cout << "step 8: " << head->val << 
" " << head->prev->val << 
" " << head->prev->prev->val <<
" " << head->prev->prev->next->val << 
" " << head->next->val << 
" " << head->next->prev->val <<
" " << head->next->prev->prev->val <<
" " << head->next->prev->next->val <<
" " << head->next->next->val << endl;