BINARY TREE REPRESENTATION.ppt

DATA STRUCTURES & ALGORITHMS

1. TREES-BINARY TREE
REPRESENTATION
BY
D.SEETHALAKSHMI
ASSISTANT PROFESSOR
DEPARTMENT OF COMPUTER
APPLICATIONS
BON SECOURS COLLEGE FOR
WOMEN

2. NON-LINEAR DATASTRUCTURE
•These data structures donot have their
elements in a sequence.
•Trees is an example.
•Trees are mainly used to represent data
containing a hierarchical relationship
between elements, ex : records, family
trees and table of contents.

3. TERMINOLOGY OFTREES
•The boxes on the tree are called nodes
•The nodes immediately below (to the left and right of) a given node
are called its children
•The node immediately above a given node is called its parent
•The (unique) node without a parent is called the root
•A node with no children is called a leaf
•Two children of the same parent are said to be siblings
•A node can be an ancestor (e.g. grandparent) or a descendant
(e.g. great-grandchild)

4. SOME TREETERMINOLOGY
•root: node with no parent
–A non-empty tree has exactly one root
•leaf: node with no children
•siblings: two nodes with the same parent.
•path: a sequence of nodes n
1, n
2, … , n
k such that n
i is the parent of
n
i+1 for 1 i < k
–in other words, a sequence of hops to get from one node to
another
–the length of a path is the number of edges in the path, or 1 less
than the number of nodes in it

5. DEPTH ANDHEIGHT
•depth or level: length of the path from root to the current node
(depth of root = 0)
•height: length of the longest path from root to any leaf
–empty (null) tree's height: -1
–single-element tree's height: 0
–tree with a root with children: 1

6. TREEEXAMPLE

7. TREES
•Tree nodes contain two or more links
–All other data structures we have
discussed only contain one
•Binary trees
–All nodes contain two links
•None, one, or both of which may be NULL
–The root node is the first node in a tree.
–Each link in the root node refers to a child
–A node with no children is called a leaf node

8. BINARYTREES
•Special type of tree in which every node or
vertex has either no children, one child or
two children.
•Characteristics :
•Every binary tree has a root pointer which
points to the start of the tree.
•A binary tree can be empty.
•It consists of a node called root, a left subtree
and right subtree both of which are binary
trees themselves.

9. EXAMPLES : BINARYTREES
X
X
Y
YZ
(2) (3)
X X
Z
A
B
C
(1)
(4)
Root of tree is node having info asX.
(1) Only node isroot.
(2)Root has left child Y.
(3)Root X has right child Z.
(4)Root X has left child Y and right child Z which
is again a binary tree with its parent as Z and
left child of Z is A, which in turn is parent for
left child B and right child C.

10. PROPERTIES OF BINARYTREE
•A tree with n nodes has exactly (n-1) edges or
branches.
•In a tree every node except the root has exactly
one parent (and the root node does not have a
parent).
•There is exactly one path connecting any two
nodes in a tree.
•The maximum number of nodes in a binary tree
of height K is 2
K+1 -1 where K>=0.

11. REPRESENTATION OF BINARYTREE
•Array representation
–The root of the tree is
stored in position 0.
–The node in position p, is
the implicit father of nodes
2p+1 and 2p+2.
–Left child is at 2p+1 and
right at 2p+2.
X
Y
Z
A
B
0 1 2 3 4 5 6 7 8 10
C
11 12
X Y Z A B C
9

12. REPRESENTATION OF BINARYTREE
•Linked List
•Every node will consists of information, and two
pointers left and right pointing to the left and right
child nodes.
struct node
{
int data;
struct node *left; struct node *right;
};
•The topmost node or first node is pointed by a root
pointer which will inform the start of the tree. Rest of
the nodes are attached either to left if less than parent
or right if more or equal to parent.

13. •Diagram of a binarytree
B
A D
C

14. OPERATIONS ON BINARYTREE
•Searching an existingnode.
•Inserting a newnode.
•Deleting an existingnode.
•Traversing thetree.
•Preorder
•Inorder
•Postorder

15. SEARCHPROCESS
•Initializeasearchpointerastherootpointer.
•Allthedataiscomparedwiththedatastoredineach
nodeofthetreestartingfromrootnode.
•Ifthedatatobesearchedisequaltothedataofthe
nodethenprint“successful”search.
•Elseifthedataislessthannode’sdatamovethepointer
toleftsubtree.Elsedataismorethannode’sdatamove
thepointertorightsubtree.
•Keepmovinginthetreeuntilthedataisfoundorsearch
pointercomestoNULLinwhichcaseitisan
“unsuccessful”search.

16. EXAMPLE USED FORSEARCH
21
18
19
7
6 9
8
11
14
13
Root

17. EXAMPLE :SEARCH
•Initializetempasrootpointerwhichisnodehaving21.
•Loopuntiltemp!=NULLorITEMfound
•Compareitem=9withtheroot21ofthetree,since
9<21,proceedtemptotheleftchildofthetree.
•CompareITEM=9with18since9<18proceedtemp
totheleftsubtreeof18,whichis7.
•CompareITEM=9with7since9>7proceedtempto
rightsubtreeofthenodewhichholdsavalue7.
•NowITEM=9iscomparedwiththenodewhichholds
value9andsince9isfoundthesearchingprocess
enshere.

18. INSERTPROCESS
•Fornodeinsertioninabinarysearchtree,initiallythe
datathatistobeinsertediscomparedwiththedataof
therootdata.
•Ifthedataisfoundtobegreaterthanorequaltothe
dataoftherootnodethenthenewnodeisinsertedin
therightsubtreeoftherootnode,elseleftsubtree.
•Nowtheparentoftherightorleftsubtreeisconsidered
anditsdataiscomparedwiththedataofthenewnode
andthesameprocedureisrepeatedagainuntilaNULL
isfoundwhichwillindicateaspacewhenthenewnode
hastobeattached.Thusfinallythenewnodeismade
theappropriatechildofthiscurrentnode.

19. EXAMPLE USED FORINSERT
38
14
23
8
Root
56
82
45
18 70
20

20. EXAMPLE :INSERT
•SupposetheITEM=20isthedatapartofthenewnode
tobeinsertedinthetreeandtherootispointingtothe
startofthetree.
•CompareITEM=20withtheroot38ofthetree.Since20
<38proceedtotheleftchildof38,whichis14.
•Compare ITEM=20 with 14, since 20 > 14 proceed to the
right child of 14, which is 23.
•Compare ITEM=20 with 23 since 20 < 23 proceed to the
left child of 23 which is 18.
•Compare ITEM=20 with 18 since 20 > 18 and 18 does
not have right child, 10 is inserted as the right child of 18.

21. •Treetraversals:
–Inorder traversal –prints the node values in ascendingorder
1.Traverse the left subtree with an inordertraversal
2.Process the value in the node (i.e., print the nodevalue)
3.Traverse the right subtree with an inordertraversal
–Preordertraversal
1.Process the value in thenode
2.Traverse the left subtree with a preordertraversal
3.Traverse the right subtree with a preordertraversal
–Postordertraversal
1.Traverse the left subtree with a postordertraversal
2.Traverse the right subtree with a postordertraversal
3.Process the value in thenode

22. BINARY TREETRAVERSALS
•three common binary tree traversal orderings (each one begins at
the root):
–preorder traversal: the current node is processed, then the
node's left subtree is traversed, then the node's right subtree is
traversed (CURRENT-LEFT-RIGHT)
–in-ordertraversal:thenode'sleftsubtreeistraversed,thenthe
currentnodeitselfisprocessed,thenthenode'srightsubtreeis
traversed(LEFT-CURRENT-RIGHT)
–postorder traversal: the node's left subtree is traversed, then
the node's right subtree is traversed, and lastly the current node
is processed (LEFT-RIGHT-CURRENT)

23. BINARY TREE PREORDER
TRAVERSAL
"G""F"
•order: C F T B R K G
–The trick: Walk around the outside of the tree and emit a node's
value when you touch the left side of the node.
root
"C"
"T"
"R""B"
"K"

24. BINARY TREE IN-ORDERTRAVERSAL
order: B T R F K C G
–The trick: Walk around the outside of the tree and emit a node's value
when you touch the bottom side of the node.
root
"C"
"F"
"T"
"G"
"R""B"
"K"

25. BINARY TREE POSTORDER
TRAVERSAL
order: B R T K F G C
–The trick: Walk around the outside of the tree and emit a node's value
when you touch the right side of the node
root
"C"
"F"
"T"
"G"
"R""B"
"K"

26. DELETEPROCESS
•There are four possible conditions are to be taken into account :
i.No node in the tree holds the specified data.
ii.The node containing the data has no children.
iii.The node containing the data has exactly one child.
iv.The node containing data has two children.
•Condition(i)Inthiscasewesimplyprintthemessagethatthedata
itemisnotpresentinthetree.
•Condition(ii)Inthiscasesincethenodetobedeletedhasno
childrenthememoryoccupiedbythisshouldbefreedandeither
theleftlinkortherightlinkoftheparentofthisnodeshouldbeset
toNULL.WhichoftheseistobesettoNULLdependsupon
whetherthenodebeingdeletedisaleftchildorrightchildofits
parent.

27. CONDITION(III)
•Inthiscasesincethenodetobedeletedhasonechildthesolutionisto
adjustthepointeroftheparentofthenodetobedeletedsuchthatafter
deletionitpointstothechildofthenodebeingdeletedasinthediagram.
18
197
6 9
11
10
24
26
25 30
21 21
18
197
6 11
10
24
26
25 30
Root Root

28. CONDITION(IV)
Inthiscasethenodetobedeletedhastwochildren.Considernode9beforedeletion.Theinordersuccessorofthe
node9isnode10.Thedataofthisinordersuccessorshouldnowbecopiedintothenodetobedeletedandapointer
shouldbesetuppointingtotheinordersuccessor(node10).Thisinordersuccessorwouldalwayshaveoneorzero
child.Itshouldthenbedeletedusingthesameprocedureasfordeletingonechildorazerochildnode.Thus,thewhole
logicofdeletinganodewithtwochildrenistolocatetheinordersuccessor,copyitsdataandreducetheproblemtoa
simpledeletionofanodewithoneorzerochild.Thisisshownintheexample.
18
197
6 9
11
10
24
26
25 30
8
21 21
18
197
6 10
11
Root Root
24
26
25 30
8
Inorder successor of node9

29. DELETION
•Condition (i) Print message data not found.
•Condition (ii) Since no children so free the node
& make either parent->left=NULL or parent-
>right=NULL.
A A
B
Parent Parent
left
right
C X
In the example2,
parent->right==x so free(x)
and make parent-
>right=NULL.
X
In the example1,
parent->left==x so free(x) and
make parent->left=NULL.

30. DELETION
• Condition (iii) Adjust parent to point to the child of the deleted node.
Node deleted(X) has only left child :
If(parent->left==x) parent->left=x->left. If(parent->right==x) parent-
>right=x->left.
I.
1)
2)
A
A
B
Parent
Parent
left right
X
B
C
C
X
left
right

31. DELETION
• Condition (iii) Adjust parent to point to the child of the deleted node.
Node deleted(X) has only right child :
If(parent->left==x) parent->left=x->right. If(parent->right==x) parent-
>right=x->right.
II.
1)
2)
A
A
B
Parent
Parent
left right
X B
C
C
right
X
right

32. DELETION
•Condition(iv)solutionmorecomplexasXhastwochildren,
•FindinordersuccessorofthenodeX.Inordersuccessorofanynodewillbefirstgotorightofthe
nodeandthenfromthatnodekeepgoingleftuntilNULLencountered,thatwillbetheinorder
successor.
•CopydataofinordersuccessortonodeX’sdata.
•Placepointerattheinordersuccessornode.Nowtheinordersuccesorwillhavezerooronechild
only(sothecomplexproblemisreducedtocondition(iii)).
•Deletetheinordersuccessornodebyusinglogicofcondition(ii)ifnochildrenorcondition(iiii)ifone
rightchild.
B
Parent A
left
D
right
X
left
C
left
E
E
Parent A
left
D
right
X
left
C
left
E
Here inorder successor E has
no children condition (ii)

33. DELETION
Parent
X
left
C
left
B
left
E
right
left
G
A
right D
Inorder
Successor
F
right H
Parent
left C
X
left
E
left
E
right
left
G
A
right D
Inorder
Successor
F
right H
Parent A left
E
left right
C D
left
F
left right
G H
Here inorder successor E has
one right child condition (iii)
If(parent->left==x)
parent->left=x->right.

34. APPLICATION OFTREE
•ExpressionTree
•GameTree