Upload
agmedia95
View
239
Download
0
Embed Size (px)
Citation preview
7/29/2019 rboles Binarios (UQ)
1/28
BinaryTreesAlgorithmsandDataStructures
COMP3506/7505
7/29/2019 rboles Binarios (UQ)
2/28
BinaryTrees
BinaryTreeDefinitionPropertiesofProperBinaryTrees
BinaryTreeADT InorderTraversal
7/29/2019 rboles Binarios (UQ)
3/28
BinaryTreeDefinition
Abinarytreeisatreewiththefollowingproperties:
Eachinternalnodehasatmosttwochildren(exactlytwofor
properbinarytrees)
Anodeschildrenareanorderedpair
Aninternalnodehasaleftchildandarightchild
A
B C
F GD E
H I
Applications: arithmeticexpressions decisionprocesses searching
7/29/2019 rboles Binarios (UQ)
4/28
BinaryTreeRecursiveDefinition
Abinarytreeiseither:
atreeconsistingofasinglenode,or
atreewhoseroothasanorderedpairofchildren,
eachofwhichisabinary
tree
A
B C
F GD E
H I
7/29/2019 rboles Binarios (UQ)
5/28
ArithmeticExpressionTree
Binarytreeassociatedwithanarithmeticexpression internalnodes:operators externalnodes:operands
Example:arithmeticexpressiontreefortheexpression(2(a-1)+(3b))
+
-2
a 1
3 b
7/29/2019 rboles Binarios (UQ)
6/28
Exercise:ArithmeticExpressionTree
Generatethebinarytreeassociatedwiththearithmeticexpression
(a
(4-b)+(7
c))
7/29/2019 rboles Binarios (UQ)
7/28
Exercise:ArithmeticExpressionTree
Generatethebinarytreeassociatedwiththearithmeticexpression
(a
(4-b)+(7
c))+
-a
4 b
7 c
Count the following: Nodes Roots Leaves External nodes Internal nodes
Whats the height of thetree?
Whats the depth of thetree?
7/29/2019 rboles Binarios (UQ)
8/28
Examplesofarithmeticexpressiontrees
(2(a-1)+(3b))
2a-1+3b
(2a-(1+3)b)
+
-2
a 1
3 b
7/29/2019 rboles Binarios (UQ)
9/28
Examplesofarithmeticexpressiontrees
(2(a-1)+(3b))
2a-1+3b
(2a-(1+3)b)
+
-
2 a
1 3 b
7/29/2019 rboles Binarios (UQ)
10/28
Examplesofarithmeticexpressiontrees
(2(a-1)+(3b))
2a-1+3b
(2a-(1+3)b) +
-
2 a
1 3
b
7/29/2019 rboles Binarios (UQ)
11/28
DecisionTree
Binarytreeassociatedwithadecisionprocess internalnodes:questionswithyes/noanswer externalnodes:decisions
Example:diningdecision
Want a fast meal?
How about coffee? On expense account?
Starbucks Spikes Al Forno Caf Paragon
Yes No
Yes No Yes No
7/29/2019 rboles Binarios (UQ)
12/28
PropertiesofProperBinaryTrees
Notationn numberofnodes
e numberofexternalnodes
i numberofinternalnodes
h height
Properties: e=i+1 n=2e-1 hi h(n-1)/2 e2h hlog2e hlog2(n+1)1
Level
0
1
2
7/29/2019 rboles Binarios (UQ)
13/28
BinaryTreeADT
TheBinaryTreeADTextendstheTreeADT,
i.e.,itinheritsallthe
methodsoftheTreeADT Additionalmethods:
positionleft(p) positionright(p) booleanhasLeft(p) booleanhasRight(p)
Updatemethodsmaybedefinedbydata
structuresimplementing
theBinaryTreeADT
7/29/2019 rboles Binarios (UQ)
14/28
LinkedStructureforBinaryTrees
Anodeisrepresentedbyanobjectstoring
Element Parentnode Leftchildnode Rightchildnode
NodeobjectsimplementthePositionADT
B
DA
C E
B
A D
C E
7/29/2019 rboles Binarios (UQ)
15/28
Array-BasedRepresentationofBinaryTrees
Nodesarestoredinanarray
letrank(node)bedefinedasfollows: rank(root)=1 ifnodeistheleftchildofparent(node),
rank(node)=2*rank(parent(node))
ifnodeistherightchildofparent(node),rank(node)=2*rank(parent(node))+1
1
2 3
6 74 5
10 11
A
HG
FE
D
C
B
J
7/29/2019 rboles Binarios (UQ)
16/28
InorderTraversal
Inaninordertraversalanodeisvisitedafteritsleftsubtree
andbeforeitsrightsubtree
Application:Drawabinarytree
x(v)=in-orderrankofv y(v)=depthofv
3
1
2
5
6
7 9
8
4
Algorithm inOrder(v)
ifhasLeft(v) then
inOrder(left(v))
visit(v)
ifhasRight(v) then
inOrder(right(v))
7/29/2019 rboles Binarios (UQ)
17/28
Whatorderwouldyouvisitthenodesinthisbinarytreeusinganinordertraversal?
7/29/2019 rboles Binarios (UQ)
18/28
Whatorderwouldyouvisitthenodesinthisbinarytreeusinganinordertraversal?
7/29/2019 rboles Binarios (UQ)
19/28
PrintArithmeticExpressions
Specializationofaninordertraversal
printoperandoroperatorwhenvisitingnode
print(beforetraversingleftsubtree
print)aftertraversingrightsubtree
+
-2
a 1
3 b((2 (a - 1)) + (3 b))
AlgorithmprintExpression(v)
ifhasLeft(v) thenprint(()
printExpression (left(v))
print(v.element())
ifhasRight(v) thenprintExpression (right(v))
print())
7/29/2019 rboles Binarios (UQ)
20/28
EvaluateArithmeticExpressions
Specializationofapostordertraversal
recursivemethodreturningthevalueofasubtree
whenvisitinganinternalnode,combinethevaluesofthesubtrees
Algorithm evalExpr(v)
ifisExternal(v) then
returnv.element()
else
x evalExpr(leftChild(v))
y evalExpr(rightChild(v))operator stored at vreturnx y
+
-2
5 1
3 2
7/29/2019 rboles Binarios (UQ)
21/28
EulerTourTraversal
Generictraversalofabinarytree Includesaspecialcasesthepreorder,postorderandinordertraversals Walkaroundthetreeandvisiteachnodethreetimes:
ontheleft(preorder)
frombelow(inorder)
ontheright(postorder)+
-2
5 1
3 2
L
B
R
7/29/2019 rboles Binarios (UQ)
22/28
WhatorderwouldyouvisitthenodesinthisbinarytreeusinganEulertourtraversal?
7/29/2019 rboles Binarios (UQ)
23/28
WhatorderwouldyouvisitthenodesinthisbinarytreeusinganEulertourtraversal?
7/29/2019 rboles Binarios (UQ)
24/28
TemplateMethodPattern
Genericalgorithmthatcanbespecializedbyredefiningcertainsteps
ImplementedbymeansofanabstractJavaclass
Visitmethodsthatcanberedefinedbysubclasses
7/29/2019 rboles Binarios (UQ)
25/28
TemplateMethodPattern
Visitmethodsthatcanberedefinedbysubclasses
TemplatemethodeulerTour
Recursivelycalledontheleftandrightchildren
AResultobjectwithfieldsleftResult,rightResultand
finalResultkeepstrackoftheoutputoftherecursivecallstoeulerTour
public abstract class EulerTour {
protected BinaryTree tree;
protected void visitExternal(Position p, Result r) {}
protected void visitLeft(Position p, Result r) {}
protected void visitBelow(Position p, Result r) {}
protected void visitRight(Position p, Result r) {}
protected Object eulerTour(Position p) {
Result r = new Result();
if tree.isExternal(p) {
visitExternal(p, r);
} else {
visitLeft(p, r);
r.leftResult = eulerTour(tree.left(p));
visitBelow(p, r);
r.rightResult = eulerTour(tree.right(p));
visitRight(p, r);
}
return r.finalResult;
}
}
7/29/2019 rboles Binarios (UQ)
26/28
Evaluating an artihmetic expression
7/29/2019 rboles Binarios (UQ)
27/28
SpecializationsofEulerTour
SpecializeEulerTourtoevaluateanarithmetic
expression
Assumptions ExternalnodesstoreIntegerobjects Internalnodesstore
Operatorobjectssupportingmethod
operation(Integer,
Integer)
public class EvaluateExpression extends EulerTour{
protected void visitExternal(Position p, Result r){
r.finalResult = (Integer) p.element();}
protected void visitRight(Position p, Result r){
Operator op = (Operator) p.element();r.finalResult = op.operation(
(Integer) r.leftResult, (Integer) r.rightResult );}
}
7/29/2019 rboles Binarios (UQ)
28/28
LectureSummary
BinaryTreeDefinition PropertiesofProperBinaryTrees BinaryTreeADT
Implementedusinglinksorarray Traversals
InorderEulertour