Tree: A Non-linear Data Structure
23 April 2012
Programming and Data Structure
Background
Linked lists use dynamic memory allocation, and hence enjoys some advantages over static representations using arrays. A problem
Searching an ordinary linked list for a given element.
Time complexity O(n).
Can the nodes in a linked list be rearranged so that we can search in O(nlog2n) time?
23 April 2012
Programming and Data Structure
Illustration
50
Level 1
75
30
Level 2 Level 3
12
45
53
80
20
35
48
78
85
Level 4
23 April 2012
Programming and Data Structure
Binary Tree
A new data structure
Binary means two.
Definition
A binary tree is either empty, or it consists of a node called the root, together with two binary trees called the left subtree and the right subtree.
Root
Left subtree
23 April 2012
Right subtree
Programming and Data Structure 4
Examples of Binary Trees
23 April 2012
Programming and Data Structure
Not Binary Trees
23 April 2012
Programming and Data Structure
Binary Search Trees
A particular form of binary tree suitable for searching. Definition
A binary search tree is a binary tree that is either empty or in which each node contains a key that satisfies the following conditions:
All keys (if any) in the left subtree of the root precede the key in the root. The key in the root precedes all keys (if any) in its right subtree. The left and right subtrees of the root are again binary search trees.
23 April 2012 Programming and Data Structure 7
Examples
10 50
15
30
75
12
20
12
45
53
80
20
35
48
78
85
23 April 2012
Programming and Data Structure
How to Implement a Binary Tree?
Two pointers in every node (left and right).
struct nd { int element; struct nd *lptr; struct nd *rptr; }; typedef nd node; node *root;
/* Will point to the root of the tree */
23 April 2012
Programming and Data Structure
An Example
Create the tree b 5
15 10
a
20
c d
a = (node *) malloc (sizeof (node)); b = (node *) malloc (sizeof (node)); c = (node *) malloc (sizeof (node)); d = (node *) malloc (sizeof (node)); a->element = 10; a->lptr = b; a->rptr = c; b->element = 5; b->lptr = NULL; b->rptr = NULL; c->element = 20; c->lptr = d; c->rptr = NULL; d->element = 15; d->lptr = NULL; d->rptr = NULL; root = a;
23 April 2012
Programming and Data Structure
10
Traversal of Binary Trees
In many applications, it is required to move through all the nodes of a binary tree, visiting each node in turn.
For n nodes, there exists n! different orders. Three traversal orders are most common:
Inorder traversal Preorder traversal Postorder traversal
23 April 2012
Programming and Data Structure
11
Inorder Traversal
Recursively, perform the following three steps:
Visit the left subtree. Visit the root. Visit the right subtree. LEFT-ROOT-RIGHT
23 April 2012
Programming and Data Structure
12
Example:: inorder traversal
10
10
20
30
20
30
40
25
50
60
20 10 30
40 20 25 10 50 30 60
23 April 2012
Programming and Data Structure
13
. d g b . a h e j i k c f
23 April 2012 Programming and Data Structure 14
Preorder Traversal
Recursively, perform the following three steps:
Visit the root. Visit the left subtree. Visit the right subtree. ROOT-LEFT-RIGHT
23 April 2012
Programming and Data Structure
15
Example:: preorder traversal
10
10
20
30
20
30
40
25
50
60
10 20 30
10 20 40 25 30 50 60
23 April 2012
Programming and Data Structure
16
a b d . g . c e h i j k f
23 April 2012 Programming and Data Structure 17
Postorder Traversal
Recursively, perform the following three steps:
Visit the left subtree. Visit the right subtree. Visit the root. LEFT-RIGHT-ROOT
23 April 2012
Programming and Data Structure
18
Example:: postorder traversal
10
10
20
30
20
30
40
25
50
60
20 30 10
40 25 20 50 60 30 10
23 April 2012
Programming and Data Structure
19
. g d . b h j k i e f c a
23 April 2012 Programming and Data Structure 20
Implementations
void inorder (node *root) { if (root != NULL) { inorder (root->left); printf (%d , root->element); inorder (root->right); } } void preorder (node *root) { if (root != NULL) { printf (%d , root->element); inorder (root->left); inorder (root->right); } }
void postorder (node *root) { if (root != NULL) { inorder (root->left); inorder (root->right); printf (%d , root->element); } }
23 April 2012 Programming and Data Structure 21
A case study :: Expression Tree
* Represents the expression: (a + b) * (c (d + e)) +
Preorder traversal :: * + a b - c + d e Postorder traversal :: a b + c d e + - *
23 April 2012 Programming and Data Structure 22
Binary Search Tree (Revisited)
Given a binary search tree, how to write a program to search for a given element? Easy to write a recursive program.
int search (node *root, int key) { if (root != NULL) { if (root->element == key) return (1); else if (root->element > key) search (root->lptr, key); else search (root->rptr, key); } }
23 April 2012 Programming and Data Structure 23
Some Points to Note
The following operations are a little complex and are not discussed here.
Inserting a node into a binary search tree. Deleting a node from a binary search tree.
23 April 2012
Programming and Data Structure
24
Graph :: another important data structure
Definition
A graph G={V,E} consists of a set of vertices V, and a set of edges E which connect pairs of vertices. If the edges are undirected, G is called an undirected graph. If at least one edge in G is directed, it is called a directed graph.
23 April 2012
Programming and Data Structure
25
How to represent a graph in a program?
Many ways
Adjacency matrix Incidence matrix, etc.
23 April 2012
Programming and Data Structure
26
Adjacency Matrix
e1 e5 e4 e3 3 4 e8 5 e6
1 e2
6 e7
. 1 2 3 4 5 6
23 April 2012
1 0 1 1 0 0 0
2 1 0 0 1 1 1
3 1 0 0 1 0 0
4 0 1 1 0 1 0
5 0 1 0 1 0 1
6 0 1 0 0 1 0
27
Programming and Data Structure
Incidence Matrix
e1 e5 e4 e3 3 4 e8 5 e6
1 e2
6 e7
. 1 2 3 4 5 6
23 April 2012
e1 1 1 0 0 0 0
e2 1 0 1 0 0 0
e3 0 0 1 1 0 0
e4 0 1 0 1 0 0
e5 e6 0 0 1 1 0 0 0 0 0 1 1 0
e7 0 0 0 0 1 1
e8 0 0 0 1 1 0
28
Programming and Data Structure
23 April 2012
Programming and Data Structure
29
