Materi pertemuan 5 Introduction to Tree, Binary Tree And Expression Tree

Materi pertemuan 5

Introduction to Tree,
Binary Tree And Expression Tree

1.   Tree

     

Tree defined recursively.

A tree is a collection of nodes.  The collection can be empty; otherwise, a tree consists of a distinguished node r, called the root, and zero or more non-empty (sub) trees T₁, T₂, …, T_k each of whose roots are connected by a directed edge from r.

A tree is a collection of N nodes, one of which is the root and N-1 edges.

Tree terminology

·       The root of each subtree is said to be a child of r and r is said to be the parent of each subtree root.

·       Leaves: nodes with no children (also known as external nodes)

·       Internal Nodes: nodes with children

·       Siblings: nodes with the same parent

·       A path from node n₁ to n_k is defined as a sequence of nodes n₁, n₂, …, n_k such that n_i is the parent of n_i+1 for 1<= i <= k.

·       The length of this path is the number of edges on the path namely k-1.

·       The length of the path from a node to itself is 0.

·       There is exactly one path from the root to each node.

·       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.

·       Depth (of node): the length of the unique path from the root to a node.

·       Depth (of tree): The depth of a tree is equal to the depth of its deepest leaf.

·       Height (of node): the length of the longest path from a node to a leaf.

o   All leaves have a height of 0

o   The height of the root is equal to the depth of the tree

2.   Binary trees

A binary tree is a tree in which no node can have more than two children.

Each node has an element, a reference to a left child and a reference to a right child.

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”).

Tree traversals

·       A binary tree is defined recursively: it consists of a root, a left subtree, and a right subtree

·       To traverse (or walk) the binary tree is to visit each node in the binary tree exactly once

·       Tree traversals are naturally recursive

Property of Binary Tree

·       Maximum number of nodes on level k of a binary tree is 2^k.

In some literatures, level of binary tree starts with 1 (root).

·       Maximum number of nodes on a binary tree of height h is 2^h+1 - 1.

Ex : Maximum nodes of a binary tree of height 3

= 1 + 2 + 4 + 8

= 2⁰ + 2¹ + 2² + 2³

= 2⁴ – 1

= 15

·       Minimum height of a binary tree of n nodes is ²log(n).

Maximum height of a binary tree of n nodes is n - 1.

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;

3.   Expression Tree Concept

Here we will discuss such arithmetic notation using expression tree.

•       Prefix   : operator is written before operands

•       Infix      : operator is written between operands

•       Postfix : operator is written after operands

·       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.

·       Postfix Traversal

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.

·       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

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.

Example :

Prefix                  : *+ab/-cde

Postfix               : ab+cd-e/*

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