�ݺ�ߣ

Tree: A Non-linear Data Structure

January 5, 2013 Programming and 1

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?


Illustration
50 Level 1

30 75 Level 2

12 45 53 80 Level 3

20 35 48 78 85 Level 4


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 Right
subtree subtree


Examples of Binary Trees


Not Binary Trees


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.


Examples

10 50

5 15 30 75

12 20
12 45 53 80

20 35 48 78 85


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 */


An Example
a
• Create the tree 10

b 5 20 c

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


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


Inorder Traversal

• Recursively, perform the following three steps:
– Visit the left subtree.
– Visit the root.
– Visit the right subtree.

LEFT-ROOT-RIGHT


Example:: inorder traversal
10

10 20 30

20 30 40 25 50 60

20 10 30 40 20 25 10 50 30 60


a

b c

d e f

g h i

j k

. d g b . a h e j i k c f


Preorder Traversal

– Visit the root.

ROOT-LEFT-RIGHT


Example:: preorder traversal
10

10 20 30

20 30 40 25 50 60

10 20 30 10 20 40 25 30 50 60


a

b c

d e f

g h i

j k

a b d . g . c e h i j k f


Postorder Traversal

– Visit the root.

LEFT-RIGHT-ROOT


Example:: postorder traversal
10

10 20 30

20 30 40 25 50 60

20 30 10 40 25 20 50 60 30 10


a

b c

d e f

g h i

j k

. g d . b h j k i e f c a


Implementations
void inorder (node *root) void preorder (node *root)
{ {
if (root != NULL) if (root != NULL)
{ {
inorder (root->left); printf (“%d “, root->element);
printf (“%d “, root->element); inorder (root->left);
inorder (root->right); inorder (root->right);
} }
} }

void postorder (node *root)
{
if (root != NULL)
{
inorder (root->left);
inorder (root->right);
printf (“%d “, root->element);
}
}


A case study :: Expression Tree
*

+ - Represents the expression:
(a + b) * (c – (d + e))

a b c +

d e

Preorder traversal :: * + a b - c + d e
Postorder traversal :: a b + c d e + - *


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


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.


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.


How to represent a graph in a program?

• Many ways
– Adjacency matrix
– Incidence matrix, etc.


Adjacency Matrix

e1 e5
1 2 6

e2 e4 e6 e7
e3 e8
3 4 5

. 1 2 3 4 5 6
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


Incidence Matrix

e1 e5
1 2 6

e2 e4 e6 e7
e3 e8
3 4 5

. e1 e2 e3 e4 e5 e6 e7 e8
1 1 1 0 0 0 0 0 0
2 1 0 0 1 1 1 0 0
3 0 1 1 0 0 0 0 0
4 0 0 1 1 0 0 0 1
5 0 0 0 0 0 1 1 1
6 0 0 0 0 1 0 1 0


�ݺ�ߣ

L11 tree

More Related Content

L11 tree