pert 4 - Binary Tree And Expression Tree - 2101680123 - MILLIADY KUSNADI THE BU HIAP

Introduction to Tree,
Binary Tree And Expression Tree

A.   Tree Concept

Tree is a collection of one or more nodes.

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 at the top is called as root.

•         A line connecting the parent to the child is edge.

•         Nodes that do not have children are called leaf.

•         Nodes that have the same parent are called sibling.

•         Degree of node is the total sub tree of the node.

•         Height/Depth is the maximum degree of nodes in a tree.

•         If there is a line that connects p to q, then p is called the ancestor of q, and q is a descendant of p.

B.   Binary Tree Concept

•         Binary tree is a rooted tree data structure in which each node has at most two children.

•         Those two children usually distinguished as left child and right child.

•         Node which doesn’t have any child is called leaf.

A sample of binary tree of 9 nodes, rooted on node which contains 18. Leaves are nodes which contain 9, 12, 10 and 23.

C.   Type of Binary Tree

•         PERFECT binary tree is a binary tree in which every level are at the same depth.

•         COMPLETE binary tree is a binary tree in which every level, except possibly the last, is completely filled, 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 each node has at most one child.

•         BALANCED binary tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

D.   Representation of Binary Tree

•         Implementation using array

Index on array represents node number

Index 0 is Root node

Index Left Child is 2p + 1, where p is parent index

Index Right Child is 2p + 2

Index Parent is (p-1)/2

•         Implementation using linked list

struct node {

          int data;

          struct node *left;

          struct node *right;

          struct node *parent;

};

struct node *root = NULL;

E.   Expression Tree Concept

•      Recall our discussion on stack application about arithmetic notation (session 6).

•      Here we will discuss such arithmetic notation using expression tree.

•      Prefix                   : *+ab/-cde

•      Postfix                  : ab+cd-e/*

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

We will use this structure for each node in the tree:

struct tnode {

          char chr;

          struct tnode *left;

          struct tnode *right;
};

It is a binary tree.

F.    Create Expression Tree from Prefix

We can create an expression tree from a prefix by recursive.

char s[MAXN];

int  p = 0;

void f(struct tnode *curr) {

          if ( is_operator(s[p]) ) {

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

                   f(curr->left);

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

                   f(curr->right);

          }
}

G.  Prefix Traversal

Doing a prefix or postfix traversal in an expression tree is simple.

void prefix(struct tnode *curr) {

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

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

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

In prefix, you have to print/process before its child are processed.

void postfix(struct tnode *curr) {

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

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

}

In postfix, you have to print/process after its child have been processed.

H.  Infix Traversal

How about infix? Can we just do like this code below?

void infix(struct tnode *curr) {

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

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

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

It’s seems right, but infix may have operator precedence ambiguity without brackets.

For example * + a b c in prefix will be encoded in infix as a + b * c with the previous code, while the correct infix is (a + b) * c.

a + b * c      : b is multiplied by c and then added by a

(a + b) * c   : a is added by b and then multiplied by c

Prefix                   : *+abc

Postfix        : ab+c*

Wrong infix          : a+b*c

Correct infix         : (a+b)*c

To fix that, we can add brackets () when expanding an operator.

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( ')' );

}

So * + a b c in prefix will be encoded as ((a + b) * c) in infix, which is correct.

I.      Create Exp-Tree from Postfix

Now, can you create an expression tree given a postfix notation?

Hint: scan from right to left.

J.     Summary

•      Tree is a collection of one or more nodes.

•      Binary tree is a rooted tree data structure in which each node has at most two children.

•      4 types of Binary Tree:

–     PERFECT binary tree

–     COMPLETE binary tree

–     SKEWED binary tree

–     BALANCED binary tree

•      We can create an expression tree from a prefix or postfix by recursive

•      In prefix, you have to print/process before its child are processed.

•      In postfix, you have to print/process after its child have been processed.