Module 3

1
Additional List Operations

typedef struct list_node *list_pointer;

typedef struct list_node {
char data;
list_pointer link;
};

2
Invert Single Linked Lists
Use two extra pointers: middle and trail.
list_pointer invert(list_pointer
lead)
{
list_pointer middle, trail;
middle = NULL;
while (lead) {
trail = middle;
middle = lead;
lead = lead->link;
middle->link = trail;
}
return middle;
}

3
Concatenate Two Lists
list_pointer concatenate(list_pointerptr1, list_pointer ptr2)
{
list_pointer temp;
if (IS_EMPTY(ptr1)) return ptr2;
else {
if (!IS_EMPTY(ptr2)) {
for (temp=ptr1;temp->link;temp=temp->link); temp->link = ptr2;
}
return ptr1;
}
}
O(m) where m is # of elements in the first list
4
Length of Circular Linked List
int length(list_pointer ptr)
{
list_pointer temp;
int count = 0;
if (ptr) {
temp = ptr;
do {
count+
+;
temp =
temp-
>link;
} while
(temp!
=ptr);
}
return count; 5
Sparse Matrices

0 0 11 0 
12 0 0 0 
 0 
0 4 0
 0
0 0  15
inadequates of sequential schemes
(1) # of nonzero terms will vary after some matrix
computation
(2) matrix just represents intermediate results

new scheme
Each column (row): a circular linked list with a head node 6
Revisit Sparse Matrices
# of head nodes = max{# of rows, # of columns}
down head right
Head node
next

down entry row col right

Entry node
value

Set up for aij entry i j

aij aij
7
Linked Representation for
Matrix

8
 Doubly Linked Lists

Move in forward and backward direction.

Singly linked list (in one direction only)

How to get the preceding node during deletion or insertion?
Using 2 pointers

Node in doubly linked list

left link field ( llink )
data field ( item )
right link field ( rlink )

9
 Doubly Linked Lists
typedef struct node *node_pointer;
typedef struct node {
node_pointer llink;
ptr
element item;
= ptr->rlink->llink
node_pointer rlink;
= ptr->llink->rlink
};

10
Empty doubly linked circular list with head
node

11
Insertion into an empty doubly
linked circular list

12
 Insert
void dinsert(node_pointer node, node_pointer newnode)
{
/* insert newnode to the right of node */
(1) newnode->llink = node;
(2) newnode->rlink = node->rlink;
(3) node->rlink->llink = newnode;
(4) node->rlink = newnode;
}

13
Delete
void ddelete(node_pointer node, node_pointer deleted)
{
/* delete from the doubly linked list */
if (node==deleted)
printf(“Deletion of head node not permitted.\n”);
else {
(1) deleted->llink->rlink= deleted->rlink;
(2) deleted->rlink->llink= deleted->llink;
free(deleted);
}
}

14
 Question:
Which code segment below implements the insert operation
correctly for singly linked lists?

(A) void insert (Listitem [Link] new) {

Linstitem next = pre, next;
new. next = null;
prt. next = new;
}

15
(B) void insert (Listitem [Link] new)
{ new. next = [Link];
[Link] = new;
}
(C) void insert (Listitem [Link] new) {
if([Link] == null) [Link] = null;
[Link] = new;
}
(D) void insert (Listitem [Link] new) {
new. Next = [Link];
pre. Next = new;
}

16
 Question:

Given a linked list of values , we want to get a new list of

values that has the set of values in a reverse order. Write
one such algorithm reverse.

17
Ans:
Procedure reverse(L: List pointer)
begin
q = nil; p
= L;
while (p≠nil) do
begin
r = q;
q = p;
p=
p↑.
Lin
k;
q
↑.
Li 18

nk
 Question:

Please write a routine concat(&list1,&list2) the concatnates

two circular list.
Type of node and pointer is
struct node { type def strnct node *Nodeptr;
int info;
struct node *next;
}

19
Ans:
void concat (Nodeptr *plist1, Nodeptr *plist2)
{
Nodeptr*p;
p= plist1→next;
plist1→Next=plist2→Next;
plist2→Next=p;
}

20
 Definition of Tree
 A tree is a finite set of one or more nodes
such that:
 There is a specially designated node called
the root.
 The remaining nodes are partitioned into n>=0
disjoint sets T1, ..., Tn, where each of these
sets is a tree.
 We call T1, ..., Tn the subtrees of the root.

CHAPTER 5 21
 Level and Depth
node (13)
Level
degree of a node
leaf (terminal)
A 1
nonterminal 3 1
parent
children B 2
sibling 2 2 1 C 2 3 D 2
degree of a tree (3)
ancestor
33
E F G H I J
level of a node 2 30 30 31 30 30
height of a tree (4)
K L M 4
0 40 4 0 4

CHAPTER 5 22
 Terminology
 The degree of a node is the number of subtrees
of the node
– The degree of A is 3; the degree of C is 1.
 The node with degree 0 is a leaf or terminal
node.
 A node that has subtrees is the parent of the
roots of the subtrees.
 The roots of these subtrees are the children of
the node.
 Children of the same parent are siblings.
 The ancestors of a node are all the nodes
along the path from the
CHAPTER 5 root to the node. 23
 Representation of Trees

 List Representation
– ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
– The root comes first, followed by a list of sub-trees

data link 1 link 2 ... link n

How many link fields are

needed in such a representation?

CHAPTER 5 24
 Left Child - Right Sibling

data
A left child right sibling

B C D

E F G H I J

K L M

CHAPTER 5 25
 Binary Trees
 A binary tree is a finite set of nodes that is
either empty or consists of a root and two
disjoint binary trees called the left subtree
and the right subtree.
 Any tree can be transformed into binary tree.
– by left child-right sibling representation
 The left subtree and the right subtree are
distinguished.
CHAPTER 5 26
*Figure 5.6: Left child-right child tree representation of a tree (p.191)

E C

F G D
K

H
L

M I

J
 Abstract Data Type Binary_Tree
structure Binary_Tree(abbreviated BinTree) is
objects: a finite set of nodes either empty or
consisting of a root node, left Binary_Tree,
and right Binary_Tree.
functions:
for all bt, bt1, bt2  BinTree, item  element
Bintree Create()::= creates an empty binary tree
Boolean IsEmpty(bt)::= if (bt==empty binary
tree) return TRUE else return FALSE
CHAPTER 5 28
BinTree MakeBT(bt1, item, bt2)::= return a binary tree
whose left subtree is bt1, whose right subtree is bt2,
and whose root node contains the data item
Bintree Lchild(bt)::= if (IsEmpty(bt)) return error
else return the left subtree of bt
element Data(bt)::= if (IsEmpty(bt)) return error
else return the data in the root node of bt
Bintree Rchild(bt)::= if (IsEmpty(bt)) return error
else return the right subtree of bt

CHAPTER 5 29
 Samples of Trees
Complete Binary Tree

A A 1 A

B B 2 B C

C Skewed Binary Tree

3 D E F G
D

4 H I
E 5

CHAPTER 5 30
 Maximum Number of Nodes in BT
 The maximum number of nodes on level i of a
i-1
binary tree is 2i-1, i>=1.
 The maximum nubmer of nodes in a binary tree
of depth k is 2k-1, k>=1.

Prove by induction.
k
 2 i 1
 2 k
1
i 1

CHAPTER 5 31
 Relations between Number of
Leaf Nodes and Nodes of Degree 2
For any nonempty binary tree, T, if n0 is the
number of leaf nodes and n2 the number of nodes
of degree 2, then n0=n2+1
proof:
Let n and B denote the total number of nodes &
branches in T.
Let n0, n1, n2 represent the nodes with no children
single child, and two children respectively.
n= n0+n1+n2, B+1=n, B=n1+2n2 ==> n1+2n2+1= n
n1+2n2+1= n0+n1+nCHAPTER
2 ==>5 n0=n2+1 32
 Full BT VS Complete BT
 A full binary tree of depth k is a binary tree of
k
depth k having 2 -1 nodes, k>=0.
 A binary tree with n nodes and depth k is
complete iff its nodes correspond to the nodes
numbered from 1 to n in the full binary tree of
depth k.
A A

B C B C

D E F G D E F G

H I J K L M N O
H I
Complete binary tree CHAPTER 5 Full binary tree of depth33 4
 Binary Tree Representations
 If a complete binary tree with n nodes (depth =
log n + 1) is represented sequentially, then for
any node with index i, 1<=i<=n, we have:
– parent(i) is at i/2 if i!=1. If i=1, i is at the root and
has no parent.
– left_child(i) ia at 2i if 2i<=n. If 2i>n, then i has no
left child.
– right_child(i) ia at 2i+1 if 2i +1 <=n. If 2i +1 >n,
then i has no right child.
CHAPTER 5 34
 [1] A
Sequential Representation [2] B
[3] C
(1) waste space
(2) insertion/deletion [4] D
A [1] A [5] E
problem
[2] B [6] F
[3] -- [7]
B G
[4] C [8]
A H
[5] -- [9]
C I
[6] --
[7] -- B C
D [8] D
[9] --
. . D E F G
E
[16] E

H
CHAPTER 5
I 35
 Linked Representation
typedef struct node *tree_pointer;
typedef struct node {
int data;
tree_pointer left_child, right_child;
};

data

left_child data right_child

left_child right_child

CHAPTER 5 36
 Binary Tree Traversals
 Let L, V, and R stand for moving left, visiting
the node, and moving right.
 There are six possible combinations of traversal
– LVR, LRV, VLR, VRL, RVL, RLV
 Adopt convention that we traverse left before
right, only 3 traversals remain
– LVR, LRV, VLR
– inorder, postorder, preorder
CHAPTER 5 37
Arithmetic Expression Using BT
+ inorder traversal
A/B*C*D+E
infix expression
* E
preorder traversal
+**/ABCDE
* D prefix expression
postorder traversal
AB/C*D*E+
/ C
postfix expression
level order traversal
A B +*E*D/CAB

CHAPTER 5 38
 Inorder Traversal (recursive version)
void inorder(tree_pointer ptr)
/* inorder tree traversal */
{
A/B*C*D+E
if (ptr) {
inorder(ptr->left_child);
printf(“%d”, ptr->data);
indorder(ptr->right_child);
}
}
CHAPTER 5 39
 Preorder Traversal (recursive version)
void preorder(tree_pointer ptr)
/* preorder tree traversal */
{
+**/ABCDE
if (ptr) {
printf(“%d”, ptr->data);
preorder(ptr->left_child);
predorder(ptr->right_child);
}
}
CHAPTER 5 40
Postorder Traversal (recursive version)
void postorder(tree_pointer ptr)
/* postorder tree traversal */
{
AB/C*D*E+
if (ptr) {
postorder(ptr->left_child);
postdorder(ptr->right_child);
printf(“%d”, ptr->data);
}
}
CHAPTER 5 41
 Iterative Inorder Traversal
(using stack)
void iter_inorder(tree_pointer node)
{
int top= -1; /* initialize stack */
tree_pointer stack[MAX_STACK_SIZE];
for (;;) {
for (; node; node=node->left_child)
add(&top, node);/* add to stack */
node= delete(&top);
/* delete from stack */
if (!node) break; /* empty stack */
printf(“%D”, node->data);
node = node->right_child;
}
}
O(n) CHAPTER 5 42
Trace Operations of Inorder Traversal
Call of inorder Value in root Action Call of inorder Value in root Action
1 + 11 C
2 * 12 NULL
3 * 11 C printf
4 / 13 NULL
5 A 2 * printf
6 NULL 14 D
5 A printf 15 NULL
7 NULL 14 D printf
4 / printf 16 NULL
8 B 1 + printf
9 NULL 17 E
8 B printf 18 NULL
10 NULL 17 E printf
3 * printf 19 NULL

CHAPTER 5 43
 Level Order Traversal
(using queue)

void level_order(tree_pointer ptr)

/* level order tree traversal */
{
int front = rear = 0;
tree_pointer queue[MAX_QUEUE_SIZE];
if (!ptr) return; /* empty queue */
addq(front, &rear, ptr);
for (;;) {
ptr = deleteq(&front, rear);

CHAPTER 5 44
 Threaded Binary Trees
 Two many null pointers in current representation
of binary trees
n: number of nodes
number of non-null links: n-1
total links: 2n
null links: 2n-(n-1)=n+1
 Replace these null pointers with some useful
“threads”.

CHAPTER 5 45
 Threaded Binary Trees (Continued)

If ptr->left_child is null,
replace it with a pointer to the node that would be
visited before ptr in an inorder traversal

If ptr->right_child is null,
replace it with a pointer to the node that would be
visited after ptr in an inorder traversal

CHAPTER 5 46
 A Threaded Binary Tree
root A
dangling
B C

dangling D E F G

inorder traversal:
H I H, D, I, B, E, A, F, C, G

CHAPTER 5 47
 Data Structures for Threaded BT
left_thread left_child data right_child right_thread
TRUE   FALSE

TRUE: thread FALSE: child

typedef struct threaded_tree
*threaded_pointer;
typedef struct threaded_tree {
short int left_thread;
threaded_pointer left_child;
char data;
threaded_pointer right_child;
short int right_thread; };
 Memory Representation of A Threaded BT

root --
f f

f A f

f B f f C f

f D f t E t t F t t G

t H t t I t

CHAPTER 5 49
 Next Node in Threaded BT
threaded_pointer insucc(threaded_pointer
tree)
{
threaded_pointer temp;
temp = tree->right_child;
if (!tree->right_thread)
while (!temp->left_thread)
temp = temp->left_child;
return temp;
} CHAPTER 5 50
Inorder Traversal of Threaded BT
void tinorder(threaded_pointer tree)
{
/* traverse the threaded binary tree
inorder */
threaded_pointer temp = tree;
for (;;) {
temp = insucc(temp);
O(n) if (temp==tree) break;
printf(“%3c”, temp->data);
}
} CHAPTER 5 51
 Inserting Nodes into Threaded BTs
 Insert child as the right child of node parent
– change parent->right_thread to FALSE
– set child->left_thread and child->right_thread
to TRUE
– set child->left_child to point to parent
– set child->right_child to parent->right_child
– change parent->right_child to point to child

CHAPTER 5 52
 Examples
Insert a node D as a right child of B.
root root

A A
(1)
B parent B parent
(3)
child child
C D C D
(2)
empty

CHAPTER 5 53
*Figure 5.24: Insertion of child as a right child of parent in a threaded binary tree (p.217)

(3)

(2) (1)

(4)

nonempty
 Right Insertion in Threaded BTs
void insert_right(threaded_pointer parent,
threaded_pointer child)
{
threaded_pointer temp;
child->right_child = parent->right_child;
(1) child->right_thread = parent->right_thread;
child->left_child = parent; case (a)
(2) child->left_thread = TRUE;
parent->right_child = child;
(3) parent->right_thread = FALSE;
if (!child->right_thread) { case (b)
temp = insucc(child);
(4) temp->left_child = child;
}
}
CHAPTER 5 55