122
Chapter4 Trees
root
. . .
T
1
T
10
T
2
T
4
T
3
Figure4.1 Generictree
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
Figure4.2 Atree
InthetreeofFigure4.2,therootisA.NodeFhasAasaparentandK,L,andM
aschildren.Eachnodemayhaveanarbitrarynumberofchildren,possiblyzero.Nodes
withnochildrenareknownasleaves;theleavesinthetreeaboveareB,C,H,I,P,Q,K,
L,M,andN.Nodeswiththesameparentaresiblings;thus,K,L,andMareallsiblings.
Grandparentandgrandchildrelationscanbedefinedinasimilarmanner.
Apathfromnoden
1
ton
k
isdefinedasasequenceofnodesn
1
,n
2
,...,n
k
suchthatn
i
istheparentofn
i+1
for1≤i<k.Thelengthofthispathisthenumberofedgesonthe
path,namely,k−1.Thereisapathoflengthzerofromeverynodetoitself.Noticethatin
atreethereisexactlyonepathfromtheroottoeachnode.
Foranynoden
i
,thedepthofn
i
isthelengthoftheuniquepathfromtherootton
i
.
Thus,therootisatdepth0.Theheightofn
i
isthelengthofthelongestpathfromn
i
toa
leaf.Thusallleavesareatheight0.Theheightofatreeisequaltotheheightoftheroot.
ForthetreeinFigure4.2,Eisatdepth1andheight2;Fisatdepth1andheight1;the
heightofthetreeis3.Thedepthofatreeisequaltothedepthofthedeepestleaf;thisis
alwaysequaltotheheightofthetree.
Ifthereisapathfromn
1
ton
2
,thenn
1
isanancestorofn
2
andn
2
isadescendantof
n
1
.Ifn
1
=n
2
,thenn
1
isaproperancestorofn
2
andn
2
isaproperdescendantofn
1
.
4.1.1 ImplementationofTrees
Onewaytoimplementatreewouldbetohaveineachnode,besidesitsdata,alinktoeach
childofthenode.However,sincethenumberofchildrenpernodecanvarysogreatlyand
isnotknowninadvance,itmightbeinfeasibletomakethechildrendirectlinksinthedata
Convert pdf pages to powerpoint slides - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf file to powerpoint online; and paste pdf into powerpoint
Convert pdf pages to powerpoint slides - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf file into ppt; convert pdf to powerpoint with
4.1 Preliminaries
123
1
struct TreeNode
2
{
3
Object
element;
4
TreeNode *firstChild;
5
TreeNode *nextSibling;
6
};
Figure4.3 Nodedeclarationsfortrees
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
Figure4.4 Firstchild/nextsiblingrepresentationofthetreeshowninFigure4.2
structure,becausetherewouldbetoomuchwastedspace.Thesolutionissimple:Keep
thechildrenofeachnodeinalinkedlistoftreenodes.ThedeclarationinFigure4.3is
typical.
Figure4.4showshowatreemightberepresentedinthisimplementation.Horizontal
arrows that point downward are
firstChild
links. Arrows that go left to right are
nextSibling
links.Nulllinksarenotdrawn,becausetherearetoomany.
InthetreeofFigure4.4,nodeEhasbothalinktoasibling(F)andalinktoachild
(I),whilesomenodeshaveneither.
4.1.2 TreeTraversalswithanApplication
Therearemanyapplicationsfortrees.Oneofthepopularusesisthedirectorystructurein
manycommonoperatingsystems,including
UNIX
and
DOS
.Figure4.5isatypicaldirectory
inthe
UNIX
filesystem.
The root t of this directory is /usr. (The asterisk k next to o the name indicates s that
/usr is itselfadirectory.)/usrhasthreechildren,mark,alex,andbill,whicharethem-
selvesdirectories.Thus,/usrcontainsthreedirectoriesandnoregularfiles.Thefilename
/usr/mark/book/ch1.risobtainedbyfollowingtheleftmostchildthreetimes.Each/afterthe
firstindicatesanedge;theresultisthefullpathname.Thishierarchicalfilesystemisvery
popularbecauseitallowsuserstoorganizetheirdatalogically.Furthermore,twofilesin
differentdirectoriescansharethesamename,becausetheymusthavedifferentpathsfrom
therootandthushavedifferentpathnames.Adirectoryinthe
UNIX
filesystemisjustafile
withalistofallitschildren,sothedirectoriesarestructuredalmostexactlyinaccordance
C# PowerPoint - How to Process PowerPoint
PowerPoint Document Processing Control in Visual C#.NET of RasterEdge .NET Imaging SDK is a reliable and professional PowerPoint slides/pages editing and
how to convert pdf to ppt using; image from pdf to powerpoint
VB.NET PowerPoint: Sort and Reorder PowerPoint Slides by Using VB.
clip art or screenshot to PowerPoint document slide large amount of robust PPT slides/pages editing methods & profession imaging controls, PDF document, image
pdf to ppt converter; picture from pdf to powerpoint
124
Chapter4 Trees
ch1.r
ch2.r
ch3.r
book*
mark*
course*         junk
cop3530*
fall*
spr*
sum*
syl.r
syl.r
syl.r
/usr*
alex*
bill*
junk         work*
course*
cop3212*
fall*
fall*
grades
prog1.r prog2.r
grades
prog1.r
prog2.r
Figure4.5
UNIX
directory
void FileSystem::listAll( ( int t depth h = = 0 0 ) const
{
1
printName( depth h ); ; // / Print t the e name of the object
2
if( isDirectory( ) ) )
3
for each h file c in this directory y (for r each child)
4
c.listAll( depth + + 1 );
}
Figure4.6 Pseudocodetolistadirectoryinahierarchicalfilesystem
withthetypedeclarationabove.
1
Indeed,onsomeversionsof
UNIX
,ifthenormalcom-
mandtoprintafileisappliedtoadirectory,thenthenamesofthefilesinthedirectorycan
beseenintheoutput(alongwithothernon-
ASCII
information).
Supposewewouldliketolistthenamesofallofthefilesinthedirectory.Ouroutput
formatwillbethatfilesthataredepthd
i
willhavetheirnamesindentedbyd
i
tabs.Our
algorithmisgiveninFigure4.6aspseudocode.
Therecursivefunction
listAll
needs tobestartedwithadepthof0tosignifyno
indentingfortheroot.Thisdepthisan internalbookkeepingvariable,andishardlya
parameterthatacallingroutineshouldbeexpectedtoknowabout.Thus,thedefaultvalue
of0isprovidedfor
depth
.
Thelogicofthealgorithmissimpletofollow.Thenameofthefileobjectisprintedout
withtheappropriatenumberoftabs.Iftheentryisadirectory,thenweprocessallchildren
recursively,onebyone.Thesechildrenareoneleveldeeper,andthusneedtobeindented
anextraspace.TheoutputisinFigure4.7.
Thistraversalstrategyisknownasapreordertraversal.Inapreordertraversal,work
atanodeisperformedbefore(pre)itschildrenareprocessed.Whenthisprogramisrun,
itisclearthatline1isexecutedexactlyoncepernode,sinceeachnameisoutputonce.
Sinceline1isexecutedatmostoncepernode,line2mustalsobeexecutedonceper
1
Eachdirectoryinthe
UNIX
filesystemalsohasoneentrythatpointstoitselfandanotherentrythatpoints
totheparentofthedirectory.Thus,technically,the
UNIX
filesystemisnotatree,butistreelike.
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
add image to slide, extract slides and merge library SDK, this VB.NET PowerPoint processing control powerful & profession imaging controls, PDF document, image
create powerpoint from pdf; how to add pdf to powerpoint
VB.NET PowerPoint: Use PowerPoint SDK to Create, Load and Save PPT
Besides, users also can get the precise PowerPoint slides count as soon as the PowerPoint document has been loaded by using the page number getting method.
how to change pdf to powerpoint; convert pdf file to ppt online
4.1 Preliminaries
125
/usr
mark
book
ch1.r
ch2.r
ch3.r
course
cop3530
fall
syl.r
spr
syl.r
sum
syl.r
junk
alex
junk
bill
work
course
cop3212
fall
grades
prog1.r
prog2.r
fall
prog2.r
prog1.r
grades
Figure4.7 The(preorder)directorylisting
node.Furthermore,line4canbeexecutedatmostonceforeachchildofeachnode.But
thenumberofchildrenisexactlyonelessthanthenumberofnodes.Finally,the
for
loop
iteratesonceperexecutionofline4plusonceeachtimetheloopends.Thus,thetotal
amountofworkisconstantpernode.IfthereareNfilenamestobeoutput,thenthe
runningtimeisO(N).
Anothercommonmethodoftraversingatreeisthepostordertraversal.Inapostorder
traversal,theworkatanodeisperformedafter(post)itschildrenareevaluated.Asan
example,Figure4.8representsthesamedirectorystructureasbefore,withthenumbersin
parenthesesrepresentingthenumberofdiskblockstakenupbyeachfile.
Sincethedirectoriesarethemselvesfiles,theyhavesizestoo.Supposewewouldliketo
calculatethetotalnumberofblocksusedbyallthefilesinthetree.Themostnaturalway
todothiswouldbetofindthenumberofblockscontainedinthesubdirectories/usr/mark
(30),/usr/alex(9),and/usr/bill(32).Thetotalnumberofblocksisthenthetotalinthe
VB.NET PowerPoint: Extract & Collect PPT Slide(s) Using VB Sample
pages of document 1 and some pages of document please read this VB.NET PowerPoint slide processing powerful & profession imaging controls, PDF document, image
change pdf to ppt; image from pdf to ppt
VB.NET PowerPoint: Merge and Split PowerPoint Document(s) with PPT
of the split PPT document will contain slides/pages 1-4 code in VB.NET to finish PowerPoint document splitting If you want to see more PDF processing functions
copying image from pdf to powerpoint; convert pdf into powerpoint
126
Chapter4 Trees
ch1.r(3)ch2.r(2)ch3.r(4)
book*(1)
mark*(1)
course*(1)junk (6)
cop3530*(1)
fall*(1)     spr*(1)        sum*(1)
syl.r(1) syl.r(5) syl.r(2)
/usr*(1)
alex*(1)
bill*(1)
junk (8) ) work*(1)
course*(1)
cop3212*(1)
fall*(1)
fall*(1)
grades(3)prog1.r(4)prog2.r(1)
grades(9)
prog1.r(7)
prog2.r(2)
Figure4.8
UNIX
directorywithfilesizesobtainedviapostordertraversal
int FileSystem::size( ( ) const
{
int totalSize e = = sizeOfThisFile( );
if( isDirectory( ) ) )
for each h file c in this directory y (for r each child)
totalSize += c.size( );
return totalSize;
}
Figure4.9 Pseudocodetocalculatethesizeofadirectory
subdirectories(71)plustheoneblockusedby/usr,foratotalof72.Thepseudocode
method
size
inFigure4.9implementsthisstrategy.
Ifthecurrentobjectisnotadirectory,then
size
merelyreturnsthenumberofblocks
itusesinthecurrentobject.Otherwise,thenumberofblocksusedbythedirectoryis
addedtothenumberofblocks(recursively)foundinallthechildren.Toseethedifference
betweenthepostordertraversalstrategyandthepreordertraversalstrategy,Figure4.10
showshowthesizeofeachdirectoryorfileisproducedbythealgorithm.
4.2 BinaryTrees
Abinarytreeisatreeinwhichnonodecanhavemorethantwochildren.
Figure4.11showsthatabinarytreeconsistsofarootandtwosubtrees,T
L
andT
R
,
bothofwhichcouldpossiblybeempty.
Apropertyofabinarytreethatissometimesimportantisthatthedepthofanaverage
binarytreeisconsiderablysmallerthanN.Ananalysisshowsthattheaveragedepthis
O(
N),andthatforaspecialtypeofbinarytree,namelythebinarysearchtree,theaverage
valueofthedepthisO(logN).Unfortunately,thedepthcanbeaslargeasN−1,asthe
exampleinFigure4.12shows.
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
VB.NET PowerPoint Conversion Control to render and convert target PowerPoint document to various image or document formats, such as PDF, BMP, TIFF
how to convert pdf into powerpoint on; pdf to powerpoint
VB.NET PowerPoint: Convert & Render PPT into PDF Document
Using this VB.NET PowerPoint to PDF converting demo code below, you can easily convert all slides of source PowerPoint document into a multi-page PDF file.
convert pdf to editable ppt; chart from pdf to powerpoint
4.2 BinaryTrees
127
ch1.r
3
ch2.r
2
ch3.r
4
book
10
syl.r
1
fall
2
syl.r
5
spr
6
syl.r
2
sum
3
cop3530
12
course
13
junk
6
mark
30
junk
8
alex
9
work
1
grades
3
prog1.r 4
prog2.r 1
fall
9
prog2.r 2
prog1.r 7
grades
9
fall
19
cop3212
29
course
30
bill
32
/usr
72
Figure4.10 Traceofthesizefunction
root
T
L
T
R
Figure4.11 Genericbinarytree
C# PowerPoint: C# Guide to Add, Insert and Delete PPT Slide(s)
summary> /// Delete pages from PowerPoint view detailed guide for each PowerPoint slide processing powerful & profession imaging controls, PDF document, tiff
pdf to powerpoint converter; and paste pdf to powerpoint
VB.NET PowerPoint: Read, Edit and Process PPTX File
VB.NET PowerPoint: Convert & Render PPTX Slide, VB.NET PowerPoint: Watermark PPTX Slide. How to convert PowerPoint to PDF, render PowerPoint to SVG
change pdf to powerpoint online; convert pdf pages to powerpoint slides
128
Chapter4 Trees
A
B
C
D
E
Figure4.12 Worst-casebinarytree
4.2.1 Implementation
Becauseabinarytreenodehasatmosttwochildren,wecankeepdirectlinkstothem.The
declarationoftreenodesissimilarinstructuretothatfordoublylinkedlists,inthatanode
isastructureconsistingofthe
element
informationplustwopointers(
left
and
right
)to
othernodes(seeFig.4.13).
Wecoulddraw thebinarytreesusingtherectangularboxesthatarecustomaryfor
linked lists,but treesaregenerally drawnas circles connected by lines,becausethey
areactuallygraphs.Wealsodonotexplicitlydraw
nullptr
linkswhenreferringtotrees,
becauseeverybinarytreewithNnodeswouldrequireN+1
nullptr
links.
Binary treeshave many important usesnot associated with searching.Oneofthe
principalusesofbinarytreesisintheareaofcompilerdesign,whichwewillnowexplore.
4.2.2 AnExample:ExpressionTrees
Figure4.14showsanexampleofanexpressiontree.Theleavesofanexpressiontreeare
operands,suchasconstantsorvariablenames,andtheothernodescontainoperators.
Thisparticulartreehappenstobebinary,becausealltheoperatorsarebinary,andalthough
thisisthesimplestcase,itispossiblefornodestohavemorethantwochildren.Itisalso
possibleforanodetohaveonlyonechild,asisthecasewiththeunaryminusoperator.
Wecanevaluateanexpressiontree,T,byapplyingtheoperatorattheroottothevalues
struct BinaryNode
{
Object
element;
// The data in the node
BinaryNode *left;
// Left child
BinaryNode *right;
// Right child
};
Figure4.13 Binarytreenodeclass(pseudocode)
4.2 BinaryTrees
129
Figure4.14 Expressiontreefor(a + + b
*
c) + ((d
*
e + f f )
*
g)
obtained byrecursively evaluatingtheleft and rightsubtrees.Inourexample,theleft
subtreeevaluatesto
a + + (b b * * c)
andtherightsubtreeevaluatesto
((d * * e) ) + + f) * g
.The
entiretreethereforerepresents
(a + (b * c)) + (((d * * e) + + f) ) * * g)
.
Wecanproducean(overlyparenthesized)infixexpressionbyrecursivelyproducinga
parenthesizedleftexpression,thenprintingouttheoperatorattheroot,andfinallyrecur-
sivelyproducingaparenthesizedrightexpression.Thisgeneralstrategy(left,node,right)
isknownasaninordertraversal;itiseasytorememberbecauseofthetypeofexpression
itproduces.
Analternatetraversalstrategyistorecursivelyprintouttheleftsubtree,therightsub-
tree,andthentheoperator.Ifweapplythisstrategytoourtreeabove,theoutputis
a b b c
* + + d d e * f f + + g * +
,whichiseasilyseentobethepostfixrepresentationofSection3.6.3.
This traversalstrategy is generally y known n as a postorder traversal.We haveseen this
traversalstrategyearlierinSection4.1.
Athirdtraversalstrategyistoprintouttheoperatorfirstandthenrecursivelyprint
outtheleftandrightsubtrees.Theresultingexpression,
+ + a
*
b c
*
+
*
d e e f g
,isthe
lessusefulprefixnotation,andthetraversalstrategyisapreordertraversal,whichwehave
alsoseenearlierin Section 4.1.Wewillreturntothesetraversalstrategieslaterin the
chapter.
ConstructinganExpressionTree
Wenowgiveanalgorithmtoconvertapostfixexpressionintoanexpressiontree.Sincewe
alreadyhaveanalgorithmtoconvertinfixtopostfix,wecangenerateexpressiontreesfrom
thetwocommontypesofinput.Themethodwedescribestronglyresemblesthepostfix
evaluationalgorithmofSection3.6.3.Wereadourexpressiononesymbolatatime.Ifthe
symbolisanoperand,wecreateaone-nodetreeandpushapointertoitontoastack.If
thesymbolisanoperator,wepop(pointers)totwotreesT
1
andT
2
fromthestack(T
1
ispoppedfirst)andformanewtreewhoserootistheoperatorandwhoseleftandright
childrenpointtoT
2
andT
1
,respectively.Apointertothisnewtreeisthenpushedonto
thestack.
Asanexample,supposetheinputis
a b b + + c d d e e + * *
130
Chapter4 Trees
Thefirsttwosymbolsareoperands,sowecreateone-nodetreesandpushpointersto
themontoastack.
2
a
b
Next,a
+
isread,sotwopointerstotreesarepopped,anewtreeisformed,andapointer
toitispushedontothestack.
+
a
b
Next,
c
,
d
,and
e
areread,andforeachaone-nodetreeiscreatedandapointertothe
correspondingtreeispushedontothestack.
+
a
b
c
d
e
Nowa
+
isread,sotwotreesaremerged.
2
Forconvenience,wewillhavethestackgrowfromlefttorightinthediagrams.
4.2 BinaryTrees
131
+
a
b
c
+
d
e
Continuing,a
*
isread,sowepoptwotreepointersandformanewtreewitha
*
asroot.
+
a
b
*
c
+
d
e
Finally,thelastsymbolisread,twotreesaremerged,andapointertothefinaltreeisleft
onthestack.
*
+
a
b
*
c
+
d
e
Documents you may be interested
Documents you may be interested