page296.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 74 行
HTML
74 行
<HTML><HEAD><TITLE>Exercises</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html4606" HREF="page297.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4604" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4598" HREF="page295.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4608" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION009700000000000000000">Exercises</A></H1><P><OL><LI> <A NAME="exercisetreesi"> </A> For each tree shown in Figure <A HREF="page296.html#figtree18"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="17887"> </A><A NAME="figtree18"> </A> <IMG WIDTH=575 HEIGHT=204 ALIGN=BOTTOM ALT="figure17233" SRC="img1160.gif" ><BR><STRONG>Figure:</STRONG> Sample trees for Exercise <A HREF="page296.html#exercisetreesi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page252.html#eqntreestc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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> introduced in Program <A HREF="page276.html#proggeneralTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,<LI> <tt>NaryTree</tt> introduced in Program <A HREF="page281.html#prognaryTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, and<LI> <tt>BinaryTree</tt> introduced in Program <A HREF="page287.html#progbinaryTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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> method defined in Program <A HREF="page267.html#progtreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is a recursive method. Write a non-recursive depth-first traversal method that has exactly the same effect as the recursive version.<LI> <A NAME="exercisetreesprefix"> </A> Program <A HREF="page295.html#progexpressionTreeb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="displaymath63651" SRC="img1161.gif" ><P><LI> Repeat Exercise <A HREF="page296.html#exercisetreesprefix"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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=13 ALIGN=BOTTOM ALT="displaymath63652" SRC="img1162.gif" ><P><LI> The visitor defined in Program <A HREF="page295.html#progexpressionTreeb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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=295 HEIGHT=13 ALIGN=BOTTOM ALT="displaymath63653" SRC="img1163.gif" ><P> rather than <P> <IMG WIDTH=363 HEIGHT=13 ALIGN=BOTTOM ALT="displaymath63625" SRC="img1159.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="page293.html#theoremtreesiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> <A NAME="exercisetreescompare"> </A> Generalize Theorem <A HREF="page293.html#theoremtreesiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> so that it applies to <I>N</I>-ary trees.<LI> Consider two binary trees, <IMG WIDTH=151 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63455" SRC="img1135.gif" > and <IMG WIDTH=152 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63457" SRC="img1136.gif" > and the relation <IMG WIDTH=11 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline63683" SRC="img1164.gif" > given by <P> <IMG WIDTH=500 HEIGHT=95 ALIGN=BOTTOM ALT="equation17770" SRC="img1165.gif" ><P><P> If <IMG WIDTH=59 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63685" SRC="img1166.gif" >, the trees are said to be <em>isomorphic</em><A NAME=17785> </A>. Devise an algorithm to test whether two binary trees are isomorphic. What is the running time of your algorithm?</OL><HR><A NAME="tex2html4606" HREF="page297.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4604" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4598" HREF="page295.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4608" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?