[2018] 4 - Introdicton to Tree_ Binary Tree and Expression Tree - 2101673042 - Kevin Surya Pranata

Welcome Back ^_^
Today we shall discuss about Tree

In Tree we will learn about 

-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

Let's just start

Tree Concept

A tree is recursively defined as a set of one or more nodes where one node is designated as the root of the tree and all the remaining nodes can be partitioned into non-empty sets each of which is a sub-tree of the root.

 

There are :

Root Node , which is the topmost node in tree . Our root node in that picture is A

Edge . Line that connecting the parent to the child

Sub-trees . If the root node is not NULL , then the trees T1 ,T2 , T3 are called sub trees of A

Leaf node , is a node that has no children

Path , a sequence of consecutive edges . For example path from node A to I is A,D,I

Ancestor node , is all node that have connected edges above it's node 

                            For example ancestor of G is C,G

Descendant node , is all node that have connected edges below it's node

                            For example descendant of A is B,C,D,E,F,G,H,I,J,K

Level number . Level is started from ROOT which is Zero (0).  All children nodes has +1 level number from it's parents

                           For example level from node K is 3

Degree . Degree of a node is equal to the number of children that a node has. The degree of a leaf node is zero.

In-degree .  In-degree of a node is the number of edges arriving at that node.

Out-degree . Out-degree of a node is the number of edges leaving that node.

Now we will discuss about Binary Tree

Binary tree is a rooted tree data structure in which node has at MOST two (2) children
Those two children usually known as left child and right child.
Node which doesn't have any child is called leaf
Let examine this tree

From this tree we known that this tree has 9 nodes, and it's root is 18
This tree has 4 leaves which is node with number 9 - 12 - 10 - 23

There are four type of Binary Tree

Perfect Binary Tree

Complete Binary Tree

Skewed Binary Tree

Balanced Binary Tree

Perfect Binary Tree is a binary tree in which every level are at the same depth
this is the picture


Complete Binary Tree is like Perfect Binary Tree , but except possibly the last is don't have child, and all nodes are as far left as possible. A perfect binary tree is a complete binary tree


Skewed Binary Tree is a binary tree in which every node has exactly just one child
This the picture of Skewed one






Balanced Binary Tree is a binary tree in which no leaf is much farther away from the root than any other leaf. In other words means that it's look balanced for a reason




 After you saw this following tree above us. What do you think?
We can count on maximum numbers of nodes on a level.
With formula Max on level k = 2^k
On level 0 = 2^0 = 1
On level 1 = 2^1 = 2
On level 2 = 2^2 = 4
On level 3 = 2^3 = 8
On level 4 = 2^4 = 16
and so on :)

Now if we'd like to count total number of nodes on a binary tree of an height let say n
How do we count that?
Well as you can see
Level 0 = 1 = 2^0
Level 1 = Level 0 + 2^1 = 1 + 2 = 3 = 4 - 1 =2^2 - 1
Level 2 = Level 1+ 2^2 = 3 + 4 = 7 = 8 - 1 =2^3 - 1
Level 3 = Level 2 + 2^3 = 7 + 8 = 15 = 2^4 - 1
on Level n then = 2^(n+1) - 1
that's the formula

Now we will learn about representation of binary tree in array 

Let examine this picture




With this following manners we can transpose any tree into array correctly and wisely not to do so
but let we try
Index 0 is reserved for the root node
Now the index of left child is 2p+1 , p is the parent index
Meanwhile the index of right child is 2p+2
If you'd like to find the index of any child is (p-1)/2  with round down

Now we will learn about representation binary tree using linked list

please examine this picture again :)

As you can see. Each node has 3 links and has a value let say an int data
so it has code declaration like this
struct node{
  int data;
  struct node *left;
  struct node *right;
  struct node *parent;
};

struct node *root = NULL;
//nah this one is to declare that if our tree is empty then we set the root NULL

Now we want to discuss about Expression Tree Concept
Here we want to discuss such that arithmetic notation using expression tree

Let examine this tree

In Infix it's actually (a+b)*((c-d)/e)
If we manage to make that to prefix and postfix
Prefix : *+ab/-cde
Postfix : ab+cd-e/*

If you wondering the structure code of this tree
struct tnode{
  char chr; 
  struct tnode *left;
  struct tnode *right;
} 

Now if we want to create an expression tree from a prefix, we can use recursive
this is the code

struct tnode *root = newnode(s[0]);
f(root);

char s[MAXN];
int p = 0 ;
void f(struct tnode *curr){
 if(is_operator(s[p])){
  p++; curr->next = newnode(s[p]);
  f(curr->left);
  p++; curr->right = newnode(s[p]);
  f(curr->right);
 }
}

Now. Doing a prefix or postfix traversal in an expression tree is simple
This code will help you understand

void prefix(struct tnode *curr){
 print("%c",curr->chr);
 if(curr->next != 0 ) prefix(curr->left);
 if(curr->next != 0 ) prefix(curr->right);
}

take a note : you have to print / process before its child are processed
BUT in postfix

void postfix(struct tnode*curr){
 if(curr->next != 0 ) prefix(curr->left);
 if(curr->next != 0 ) prefix(curr->right); 
 print("%c",curr->chr);
}

in postfix, you have to print / process after is child have been processed

Now I will show you how to make infix, but remember with infix, computer and user
may found ambiguity , then we shall use brackes to help understanding

void infix(tnode *curr) {

  if ( is_operator(curr->chr) ) putchar( '(' );

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

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

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

  if ( is_operator(curr->chr) ) putchar( ')' );

}

Imagine  if we have * + a b c

The resulting infix we have is ((a+b)*c)     [:

Now I want to share formula to use if you'd like to have any  postfix or prefix [?]

Have a good day everybody !