Tree atau Pohon, sekumpulana 1 data atau lebih yang berhubungan.

Konsep Tree :

• Node paling atas disebut root
• Suatu garis yang menghubungkan kedua node disebut edge
• Node yang tidak memiliki child disebut leaf
• Node yang mempunyai parent yang sama disebut sibling

Konsep Binary Tree :

•  Setiap Node mempunyai paling banyak 2 child
• Setiap childnya biasa dibedakan dengan LEFT dan RIGHT
• Node yang tidak mempunyai child disebut leaf

Expression Tree

Prefix : *+ab/-cde
Postfix : ab+cd-e/*
Infix : (a+b)*((c-d)/e)

Structure Node yang digunakan adalah :
struct tnode
{
char chr;
struct tnode *left;
struct tnode *right;
};

Prefix Traversal (Print Left Right):
void prefix (struct tnode *curr)
{
printf(“%c”, curr->chr);
if (curr->left) prefix(curr->left);
if (curr->right) prefix(curr->right);
}

Post Traversal (Left Right Print):
void postfix (struct tnode *curr)
{
if (curr->left) postfix (curr->left);
if (curr->right) postfix (curr->right);
printf(“%c”, curr->chr);
}

Infix Traversal (Left Print Right) :
void infix (struct tnode *curr)
{
if (is_operator(curr->chr)) putchar(‘(‘);
if (curr->left) infix(curr->left);
printf(“%c”, curr->chr);
if (curr->right) infix(curr->right);
if (is_operator(curr->chr)) putchar(‘)’);
}