Introduction to Tree, Binary Tree And Expression Tree

Introduction to Tree, Binary Tree

and Expression Tree

1. Tree Concept

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.

2. 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 contains

9, 12, 10, and 23.

3. Types 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

3       4. Property of Binary Tree

a      

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

Maximum nodes

of a binary tree of

height 3

= 1 + 2 + 4 + 8

= 20 + 21 + 22 + 23

= 24 – 1

= 15

5. 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;

   6. Expression Tree Concept

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;
};

7. Prefix Transversal

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.

8. Postfix Transversal

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.

9. Infix Transversal

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.