📄 page297.html
字号:
<HTML>
<HEAD>
<TITLE>Exercises</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html5593" HREF="page298.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page298.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5591" HREF="page250.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page250.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5585" HREF="page296.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page296.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5595" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5596" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION0010700000000000000000">Exercises</A></H1>
<P>
<OL><LI> <A NAME="exercisetreesi"> </A>
For each tree shown in Figure <A HREF="page297.html#figtree18" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page297.html#figtree18"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
show the order in which the nodes are visited during
the following tree traversals:
<OL><LI> preorder traversal,<LI> inorder traversal (if defined),<LI> postorder traversal, and<LI> breadth-first traversal.
</OL>
<P>
<P><A NAME="18571"> </A><A NAME="figtree18"> </A> <IMG WIDTH=575 HEIGHT=201 ALIGN=BOTTOM ALT="figure17918" SRC="img1211.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1211.gif" ><BR>
<STRONG>Figure:</STRONG> Sample trees for Exercise <A HREF="page297.html#exercisetreesi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page297.html#exercisetreesi"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A><BR>
<P><LI>
Write a visitor that prints the nodes of a general tree
in the format of Equation <A HREF="page251.html#eqntreestc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page251.html#eqntreestc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.<LI>
Derive an expression for the total space needed to
represent a tree of <I>n</I> internal nodes
using each of the following classes:
<OL><LI> <tt>GeneralTree</tt> defined in Program <A HREF="page276.html#proggentree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page276.html#proggentree1h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,<LI> <tt>NaryTree</tt> defined in Program <A HREF="page282.html#prognarytree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page282.html#prognarytree1h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>, and<LI> <tt>BinaryTree</tt> defined in Program <A HREF="page289.html#progbintree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page289.html#progbintree1h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
</OL><LI> <A NAME="exercisetreesfullnode"> </A>
A full node in a binary tree is a node with two non-empty subtrees.
Let <I>l</I> be the number of leaf nodes in a binary tree.
Show that the number of full nodes is <I>l</I>-1.<LI>
The generic <tt>DepthFirstTraversal</tt> routine defined in
Program <A HREF="page268.html#progtree1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page268.html#progtree1c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> is a recursive function.
Write a non-recursive depth-first traversal routine
that has exactly the same effect as the recursive version.<LI> <A NAME="exercisetreesprefix"> </A>
Program <A HREF="page296.html#progapp06bc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page296.html#progapp06bc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> defines a visitor that prints
using <em>infix</em> notation
the expression represented by an expression tree.
Write a visitor that prints the same expression
in <em>prefix</em> notation with the following format:
<P> <IMG WIDTH=339 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath64320" SRC="img1212.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1212.gif" ><P><LI>
Repeat Exercise <A HREF="page297.html#exercisetreesprefix" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page297.html#exercisetreesprefix"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
but this time write a visitor that the expression
in <em>postfix</em> notation with the following format:
<P> <IMG WIDTH=288 HEIGHT=12 ALIGN=BOTTOM ALT="displaymath64321" SRC="img1213.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1213.gif" ><P><LI>
The <tt>InfixVisitor</tt> defined in Program <A HREF="page296.html#progapp06bc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page296.html#progapp06bc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
prints many redundant parentheses because it does
not take into consideration the precedence of the operators.
Rewrite the visitor so that it prints
<P> <IMG WIDTH=296 HEIGHT=13 ALIGN=BOTTOM ALT="displaymath64322" SRC="img1214.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1214.gif" ><P>
rather than
<P> <IMG WIDTH=363 HEIGHT=13 ALIGN=BOTTOM ALT="displaymath64294" SRC="img1210.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1210.gif" ><P><LI> <A NAME="exercisetreespostfix"> </A>
Consider postfix expressions involving only binary operators.
Show that if such an expression contains <I>n</I> symbols,
it always has (<I>n</I>-1)/2 operators and (<I>n</I>+1)/2 operands.<LI> <A NAME="exercisetreestotal"> </A>
Prove Theorem <A HREF="page294.html#theoremtreesiv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page294.html#theoremtreesiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.<LI> <A NAME="exercisetreescompare"> </A>
Generalize Theorem <A HREF="page294.html#theoremtreesiv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page294.html#theoremtreesiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> so that it applies to <I>N</I>-ary trees.<LI>
Consider two binary trees,
<IMG WIDTH=149 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64124" SRC="img1189.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1189.gif" > and <IMG WIDTH=152 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64126" SRC="img1190.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1190.gif" > and
the relation <IMG WIDTH=10 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline64352" SRC="img1215.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1215.gif" > given by
<P> <IMG WIDTH=500 HEIGHT=95 ALIGN=BOTTOM ALT="equation18448" SRC="img1216.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1216.gif" ><P>
<P>
If <IMG WIDTH=60 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64354" SRC="img1217.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1217.gif" >,
the trees are said to be <em>isomorphic</em><A NAME=18463> </A>.
Devise an algorithm to test whether two binary trees are isomorphic.
What is the running time of your algorithm?
</OL><HR><A NAME="tex2html5593" HREF="page298.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page298.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5591" HREF="page250.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page250.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5585" HREF="page296.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page296.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5595" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5596" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -