pertemuan4-Introduction to Tree, Binary Tree And Expression Tree-ihsan-2101669790

   

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

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.

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

PERFECT Binary Tree

COMPLETE Binary Tree

SKEWED Binary Tree

Property of Binary Tree

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

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

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

Representation of Binary Tree

struct node {

            int data;

            struct node *left;

            struct node *right;

            struct node *parent;

};

struct node *root = NULL;

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

It is a binary tree.

Create Expression Tree from Prefix

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

            }
}

Prefix Traversal

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

void postfix(struct tnode *curr) {

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

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

}

Infix Traversal

void infix(struct tnode *curr) {

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

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

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