Pertemuan ke 4 - Introduction to Tree, Binary Tree And Expression Tree - 2101682242 - Mohammad Refardy

Sub Topics­­

Tree & Binary Tree:

-        Tree Concept

-        Binary Tree Concept

-        Type of Binary Tree

-        Property of Binary Tree

-        Representation of Binary Tree

-        Expression Tree Concept

-        Create Expression Tree from Prefix, Postfix and Infix

-        Prefix, Postfix and Infix Traversal

Tree Concept

Pohon adalah kumpulan dari satu atau lebih node.

DEGREE of TREE = 3

DEGREE of C = 2

HEIGHT = 3

PARENT of C = A

CHILDREN of  A = B, C, D

SIBILING of F = G

ANCESTOR of F = A, C

DESCENDANT of C = F, G

Node di bagian atas disebut sebagai root.

Garis yang menghubungkan orang tua dengan anak itu adalah tepi.

Node yang tidak memiliki anak disebut daun.

Node yang memiliki induk yang sama disebut saudara kandung.

Derajat simpul adalah sub-pohon total dari simpul.

Tinggi / Kedalaman adalah tingkat maksimum simpul di pohon.

Jika ada garis yang menghubungkan p ke q, maka p disebut sebagai leluhur q, dan q adalah keturunan dari hlm.

Binary Tree Concept

Binary tree adalah struktur data pohon berakar di mana setiap node memiliki paling banyak dua anak.

Kedua anak itu biasanya dibedakan sebagai anak kiri dan anak kanan.

Simpul yang tidak memiliki anak disebut daun.

Contoh binary tree

dari 9 node, yang di-root

simpul yang berisi 18.

Daun adalah simpul yang mana

mengandung 9, 12, 10, dan 23.

Type of Binary Tree

Pohon biner SEMPURNA adalah pohon biner dimana setiap tingkat berada pada kedalaman yang sama.

Pohon biner LENGKAP adalah pohon biner di mana setiap tingkat, kecuali yang terakhir, terisi penuh, dan semua simpul sejauh mungkin tertinggal. Pohon biner yang sempurna adalah pohon biner yang lengkap. SKEWED binary tree adalah pohon biner dimana masing-masing node memiliki paling banyak satu anak. Pohon biner BALANCED adalah pohon biner dimana tidak ada daun yang jauh dari akar daripada daun lainnya (skema penyeimbang yang berbeda memungkinkan definisi yang berbeda "jauh lebih jauh").

PERFECT Binary Tree

COMPLETE Binary Tree

SKEWED Binary Tree

Property of Binary Tree

Jumlah maksimum simpul pada tingkat k dari pohon biner adalah 2k.

Dalam beberapa literatur,

tingkat pohon biner

dimulai dengan 1 (root).

Representation of Binary Tree

•        Implementation using linked list

struct node {

               int data;

               struct node *left;

               struct node *right;

               struct node *parent;

};

struct node *root = NULL;

Expression Tree Concept

Ingatlah pembahasan kita tentang aplikasi stack tentang notasi aritmatika (sesi 6).

Di sini kita akan membahas notasi aritmatika menggunakan pohon ekspresi.

Prefix                    : *+ab/-cde

Postfix                  : ab+cd-e/*

Infix                      : (a+b)*((c-d)/e)

Kami akan menggunakan struktur ini untuk setiap node di pohon:

struct tnode {

               char chr;

               struct tnode *left;

               struct tnode *right;
};

ini adalah binary tree.

Create Expression Tree from Prefix

Kita dapat membuat pohon ekspresi dari awalan dengan rekursif.

char s [MAXN];

int p = 0;

void f (struct tnode * curr) {

if (is_operator (s [p])) {

p ++; curr-> left = newnode (s [p]);

f (curr-> kiri);

p ++; curr-> right = newnode (s [p]);

f (curr-> kanan);

}?}

Prefix Traversal

Melakukan awalan atau postfix traversal di pohon ekspresi sederhana.

void prefix(struct tnode *curr) {

               printf( “%c “, curr->chr );

               if ( curr->left  != 0 ) prefix(curr->left);

               if ( curr->right != 0 ) prefix(curr->right);
}

Dalam awalan, Anda harus mencetak / memproses sebelum anaknya diproses.

Postfix Traversal

void postfix (struct tnode * curr) {

jika (curr-> left! = 0) postfix (curr-> left);

if (curr-> right! = 0) postfix (curr-> right) ;? printf ("% c", curr-> chr);

}

Dalam postfix, Anda harus mencetak / memproses setelah anaknya diproses.

Infix Traversal

Bagaimana dengan infix? Bisakah kita hanya melakukan seperti kode dibawah ini?

void infix (struct tnode * curr) {

jika (curr-> left! = 0) infix (curr-> left);

printf ("% c", curr-> chr);

if (curr-> right! = 0) infix (curr-> right) ;?}