Session 4-Introduction to Tree, Binary Tree And Expression Tree

Subtopic:
-Tree Concept
-Binary Tree Concept
-Type of Binary Tree
-Property of Binary Tree
-Representation of Binary Tree
-Expression Tree Concept
-Prefix, Postfix, and Infix Traversal

Tree Concept

Degree of Tree = 3

Degree of C = 2

Height = 3

Parent of C = A

Children of A = B, C, D

Sibling of F = G

Ancestor of F = A, C

Descendant of C = F, G


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

Rooted = 18

Leaves = 9, 12 ,10, and 23

Type of Binary Tree

Perfect Binary Tree

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

Complete Binary Tree

is binary tree in which every level, except possibly the last, is completely filled, and all nodes far as possible

Skewed

is a binary tree in which each node has at most one child

Property of Binary Tree 

is a binary tree in which no leaf is much father away from the root

-Explanation for  the Example Property of Binary Tree

Maximum nodes of a binary tree of height 3

= 1 + 2 + 4 + 8

= 20 + 21 + 22 + 23

= 24 – 1

= 15

Representation of Binary Tree

-Using Array

Ex:

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

-Using Linked List
Ex:

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

Expression Tree Concept

Ex:





Prefix             : *+ab/-cde

Postfix            : ab+cd-e/*

Wrong Inflix   : a+b*c-d/e

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





Prefix, Postfix, and Inflix Traversal

Prefix Traversal Ex:

void prefix(struct tnode *curr) {

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

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

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

Postfix Traversal Ex:

void postfix(struct tnode *curr) {

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

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

}

Inflix Traversal Ex:

void infix(struct tnode *curr) {

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

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

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