📄 binary trees.htm
字号:
thought. </P>
<H3>Exercises</H3>
<OL>
<LI>Classify tree operations (height, weight, min_element, max_element,
flatten, insert, lookup, delete, pre,- in- and post-order traversal) on
unordered binary trees and on search trees as either linear or binary
recursive. Note that a linear-recursive operation may contain two or
more calls on itself but only ever execute at most one of them under the
control of an <STRONG>if</STRONG> statement. Write iterative versions of
one or more of the linear operations.
<LI>Add a full set of operators +, -, *, / to the expression parser.
<LI>Write a routine to traverse the expression parse tree to generate
reverse Polish code. eg. a*b+c*d ---> a b * c d * +
<LI>Write a routine to do symbolic differentiation. Input is the parse
tree of an arithmetic expression which may contain numerals, variables
{x, y, ...}, + and *. Output is the tree of the expression that is the
result of differentiation with respect to a given variable.
<DL>
<DT>Use the rules:
<DD>diff(x, x) = 1
<DD>diff(y, x) = 0 if y is a constant or a variable different from x
<DD>diff(A+B, x) = diff(A,x)+diff(B,x)
<DD>diff(A*B, x) = A*diff(B,x)+diff(A,x)*B </DD></DL>eg. diff(x*x+3*x+4,
x) = x*1+1*x+3*1+0*x+0 = 2*x+3
<LI>Write a routine to <STRONG>free</STRONG> all of the nodes in a
binary tree. Count the number of <STRONG>new</STRONG> and
<STRONG>free</STRONG> operations and check that they are equal.
<LI>Write a routine to collect only the elements in all the leaf nodes
of a binary tree into a list.
<LI>The <EM>path</EM> of a node in a tree is the sequence of elements
contained in nodes from the root, down to and including the node itself.
Give a procedure to print the path of every leaf node in a tree.
<LI>A height-balanced tree is not necessarily full or weight-balanced.
How un-weight-balanced can one be? ie. What is the minimum possible
number `n' of nodes in a height-balanced tree for height h=1, 2, ..., 8.
Is there a pattern? How does n compare with the value 2<SUP>h</SUP>-1
for a full tree?
<LI>(Hard) Implement a <EM>delete</EM> operation for height-balanced
trees. </LI></OL>
<DIV align=right>-- L.A.</DIV></TD>
<TD vAlign=top align=middle width="10%">
<TABLE cellSpacing=0 cellPadding=1 border=1><!-- right column -->
<TBODY>
<TR>
<TD><FONT size=-1>www</FONT><BR>
<TABLE cellSpacing=0 cellPadding=3 width="100%" bgColor=#aaffaa
border=1>
<TBODY>
<TR>
<TD>
<SCRIPT language=JavaScript><!--function locale() { var len=REMOTE_HOST.length; if(len>0 && REMOTE_HOST.lastIndexOf('.')==len-1) REMOTE_HOST=REMOTE_HOST.substring(0,len-1); if(REMOTE_HOST.lastIndexOf('.')==REMOTE_HOST.length-3) return REMOTE_HOST.substring(REMOTE_HOST.length-2); else return 'us'; }//localefunction showAmaz2007(str) { var part = str.split('|'); // part[0] should be kw's var usTemplate = '<' + 'a href="http://www.amazon.com/gp/product/XXX?ie=UTF8&tag=fourwheeldrivein&linkCode=as2&camp=1789&creative=9325&creativeASIN=XXX">YYY<' + '/a><' + 'img src="http://www.assoc-amazon.com/e/ir?t=fourwheeldrivein&l=as2&o=1&a=XXX" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" />', ukTemplate = '<' + 'a href="http://www.amazon.co.uk/gp/product/XXX?ie=UTF8&tag=fourwheeldriv-21&linkCode=as2&camp=1634&creative=6738&creativeASIN=XXX">YYY<' + '/a><' + 'img src="http://www.assoc-amazon.co.uk/e/ir?t=fourwheeldriv-21&l=as2&o=2&a=XXX" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" />'; if(part.length < 4) part[3] = ''; // post link if(part.length < 5) part[4] = ''; // locale var template = usTemplate; if(locale() == 'uk') template=ukTemplate; if(part[4] == 'uk') template = ukTemplate; // overrides if(part[4] == 'us') template = usTemplate; // overrides while(true) { var p=template.indexOf('XXX'); if(p >= 0) template=template.substring(0,p)+part[1]+template.substring(p+3); else break; } while(true) { var p=template.indexOf('YYY'); if(p >= 0) template=template.substring(0,p)+part[2]+template.substring(p+3); else break; } document.writeln(template + '<' + 'BR><' + 'FONT SIZE="-1">' + part[3] +'<' + '/FONT>' ); }//showAmaz2007function doAmaz2007(){var dflt = "xyz,MML,Bioinformatics|0525949607|The Darwin Awards 4:|Intelligent Design|us"; var url=document.URL+"$", items = new Array( "Computing,merton,Images/$,Publication," + dflt, "merton,Images/$,Publication|0143038257|Three Cups of Tea|One Man's Mission to Promote Peace One School at a Time", "/AI/,MML,Learning,Bayes|1584883871|Bayesian Artificial Intelligence|Korb and Nicholson", "AlgDS,Algorithm,Computing|0201485419|The Art of Computer Programming, Vols.1-3|Donald Knuth", "AlgDS,Algorithm,Graph,Computing|0262032937|Introduction to Algorithms|Cormen et al", "AlgDS,Algorithm,BIB,Publications,/C/,Computing|0201657880|Programming Pearls|Jon Bentley", "AlgDS,/C/,Algorithm,Graph|0201756080|Algorithms in C|Sedgwick", "AlgDS,/C/,Lang/$,PL-|0201700735|The C++ Programming Language|Stroustrup", "Bioinf|1584886420|An Introduction to Systems Biology|U.Alon", "Bioinf,Edit|0262101068|An Introduction to Bioinformatics Algorithms|Jones and Pevzner", "Bioinf,Edit|0199277877|Introduction to Bioinformatics|Arthur Lesk", "Bioinf|0805382194|Discovering Genomics, Proteomics and Bioinformatics|Campbell and Heyer", "Computers,Computing,BIB|019284055X|Colossus: The Secrets of Bletchley Park's Code Breaking Computers|Jack Copeland", "Computers,Computing,BIB|0470229055|The Annotated Turing|Charles Petzold", "FP/,Lambda|0691083940|The Calculi of Lambda Conversion|Alonzo Church|us", "FP/$,Lambda,Curried|0954300653|An Introduction To Lambda Calculi|C.Hankin", "FP/,Haskell|0521826144|Haskell 98 Language and Libraries|the Revised Report", "FP/$,Haskell|0521644089|The Haskell School of Expression:|Learning Functional Programming through Multimedia. P.Hudak", "FP/$,Haskell,Types,Curried|0521692695|Programming in Haskell|Graham Hutton", "FP/$,Haskell|0596514980|Real World Haskell|OSullivan et al", "FP/$,Haskell,Types,Curried|0134843460|Introduction to Functional Programming using Haskell|Richard Bird", "FP/$,Haskell,Curried|1740094042|An Introduction to Computing with Haskell|Chakravarty and Keller", "FP/,SML|0137903871|Elements of ML Programming|Ullman", "FP/$,SML,Curried|052156543X|ML for the Working programmer|Larry Paulson", "FP/$,SML|0201398206|Introduction to Programming using SML|Hansen and Rischel", "Java/,AlgDS,Algorithm|0321370139|Data Structures and Algorithm Analysis in Java|M.A.Weiss", "JavaScript,WWW|1565922344|JavaScript, the Definitive Guide|Flanagan", "Lang,PL-,Grammar,Syntax,Compil,Interp|0201100886|Compilers: Principles, Techniques, and Tools|Aho, Sethi and Ullman", "Lang/$,Compil,Grammar,PL-,/C/|1882114396|Using GCC: Reference Manual|Stallman et al", "Lang/$,Compil,Grammar,PL-,Java/|052182060X|Modern Compiler Implementation in Java|Appel and Palsberg", "Logic,Math,Grammar|1930190867|Discrete Mathematics for Computer Science|K.P.Bogart", "Math,Numer,AlgDS,Logic|0201558025|Concrete Mathematics: A Foundation for Computer Science|Graham, Knuth, Patashnik", "MML,MDL,Wallace,Bayes,Ockham,/AI/,Learning,Stat|038723795X|Statistical and Inductive Inference by Minimum Message Length|Chris Wallace", "MML,MDL|0262072815|The Minimum Description Length Principle|Grunwald", "Prolog,Logic|3540629718|Clause and Effect: Prolog Programming|W.F.Clocksin", "Prolog,/AI/,Learning|0201403757|Prolog Programming for Artificial Intelligence|Ivan Bratko", "Propositional,Boolean,Digital,Circuit|013198926X|Logic and Computer Design Fundamentals|Mano and Kime", "Film/$,Movie,witch|B0001V01BQ|Monty Python and the Holy Grail|DVD|uk", "Film,Movie,witch|B000W8AB22|Monty Python, Monster Box Set|DVD|uk", "Film/$,Movie,SciFi|B000HWXQBQ|Dr. Strangelove|DVD|uk", "Film/$,Andromeda|B000JLTE5C|A for Andromeda|BBC DVD|uk", "Film/$,Andromeda|B000FPV8IS|The Andromeda Anthology|(1961) DVD|uk", "Publication,BIB,Seminar,Semantic,Interp,Lambda|0521314232|A Practical Introduction to Denotational Semantics|L.Allison" ); // document.writeln(items.length + "_items"); //debug var i, numMatch = 0, candidate = new Array(); for(i = 0; i < items.length; i++) { var the_item = items[i].split("|"); var keys = the_item[0].split(","); var j; for(j = 0; j < keys.length; j++) { if(url.indexOf(keys[j]) >= 0) { candidate[numMatch]=i; numMatch++; break; } } }//for j, for i // document.writeln(numMatch + "_match"); //debug if(numMatch <= 0) showAmaz2007(dflt); else { var nM=numMatch, nth; for(nth=1; nth <= Math.min((numMatch > 3 ? 3 : 2),numMatch); nth++) { var choice = Math.floor((nM - 0.0001) * Math.random()); // document.writeln(' choice_' + choice ); // debug if(choice < 0) choice = 0; else if(choice >= nM) choice = nM - 1; if(nth>1) document.writeln('<'+'HR SIZE="1" NOSHADE>'); showAmaz2007(items[candidate[choice]]); nM--; candidate[choice]=candidate[nM]; // ! } } document.writeln( ' <' + 'FONT COLOR="#999999" SIZE="1">' + numMatch + locale() + '<' + '/FONT>');}//doAmaz2007doAmaz2007();// --></SCRIPT>
<NOSCRIPT><!-- 9/2007 --><FONT size=+1><A
href="http://www.amazon.com/gp/product/0525949607?ie=UTF8&tag=fourwheeldrivein&linkCode=as2&camp=1789&creative=9325&creativeASIN=0618680004">The
Darwin Awards 4:</A> </FONT>Intelligent Design<BR></NOSCRIPT><!--0525949607 The Darwin Awards 4:, Intelligent Design (2006)0618680004 The God Delusion, Richard Dawkins (2007)--><!-- ====================================================================== --></TD></TR></TBODY></TABLE><BR>
<TABLE cellSpacing=0 cellPadding=3 width="100%" border=1>
<TBODY>
<TR>
<TD><FONT size=-1>free:</FONT><BR><A
href="http://www.linux.org/" target=_top>Linux</A> <FONT
size=-1>operating-sys</FONT><BR><A
href="http://www.openoffice.org/" target=_top>OpenOffice</A>
<FONT size=-1>office-suite, ver. 2.4+</FONT><BR><A
href="http://www.gimp.org/" target=_top>The GIMP</A> <FONT
size=-1>~photoshop</FONT><BR><A href="http://www.mozilla.com/"
target=_top>Firefox</A> <FONT size=-1>web browser</FONT><BR><A
href="http://flashblock.mozdev.org/"
target=_top>FlashBlock</A> <FONT size=-1>flash
on/off</FONT><BR></TD></TR></TBODY></TABLE><!-- check for a recent-enough web-browser version --><B>
<SCRIPT language=JavaScript> <!-- var isOldBrowser = true, versionStr = navigator.appVersion, appCodeName = navigator.appCodeName.toLowerCase(); if( appCodeName.indexOf('mozilla') >= 0 && versionStr != null && versionStr.length > 0 ) { var criticalVersion = 4.7; // recommended by m0n@sh uni .au var version = criticalVersion-0.001, i, numDot = 0, stillOK = true; for( i = 0; i < versionStr.length; i++ ) // seek a number { if( versionStr.charAt(i) == '.' ) { numDot ++ ; stillOK = numDot < 2; } else stillOK = versionStr.charAt(i) >= '0' && versionStr.charAt(i) <= '9'; if( ! stillOK ) break; // ...charAt(i) is bad }//for if( i > numDot ) // i>0, have a valid number in version[0..i-1] version = new Number( versionStr.substring(0,i) ) - 0; isOldBrowser = version < criticalVersion; }//if if( isOldBrowser ) { document.writeln( '<' + 'BR>' ); document.writeln( '<' + 'TABLE BORDER="1" CELLSPACING="0" WIDTH="100%"> ' ); document.writeln( '<' + 'TR><' + 'TD BGCOLOR="#FFCCCC">' ); document.writeln( '<' + 'FONT SIZE="+1">Upgrade your old web ' ); document.writeln( '<' + 'A HREF="http://browsers.net' + 'scape.com/">[browser]<' + '/A>' ); document.writeln( '<' + 'A HREF="http://www.moz' + 'illa.org/">[now]<' + '/A>!<' + '/FONT>' ); document.writeln( '<' + '/TR> <' + '/TD> <' + '/TABLE>' ); }//if // --> </SCRIPT>
</B><!-- Right extras for children NB. relative to children --><!-- Right Extras Here --></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=2 width="100%" border=0>
<TBODY>
<TR>
<TD align=middle>
<HR noShade SIZE=4>
<!-- --------------------------------------subtable--->
<TABLE cellSpacing=0 cellPadding=1 border=0>
<TBODY>
<TR>
<TD><FONT size=-1>
<ADDRESS>© L. Allison <A href="http://www.allisons.org/ll/"
target=_top>http://www.allisons.org/ll/</A> <NOBR>(<U>or as
otherwise indicated</U>),</NOBR><BR>Created with "vi (Linux +
Solaris)", charset=iso-8859-1, <NOBR>fetched Monday,
15-Sep-2008 04:00:55 EST.</NOBR>
</FONT></ADDRESS></TD></TR></TBODY></TABLE>
<HR noShade SIZE=4>
<!-- --------------------------------------subtable---></TD></TR></TBODY></TABLE></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -