page293.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 101 行

HTML
101 行
字号 
<HTML><HEAD><TITLE>Comparing Trees</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="tex2html4576" HREF="page294.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4574" HREF="page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4568" HREF="page292.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html4578" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION009670000000000000000">Comparing Trees</A></H2><P>A problem which is relatively easy to solve is determining if two trees are equivalent.Two trees are<em>equivalent</em><A NAME=16578>&#160;</A><A NAME=16579>&#160;</A>if they both have the same topologyand if the objects contained in corresponding nodes are equal.Clearly, two empty trees are equivalent.Consider two non-empty 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"  >.Equivalence of trees is given by<P> <IMG WIDTH=431 HEIGHT=13 ALIGN=BOTTOM ALT="displaymath63453" SRC="img1137.gif"  ><P>A simple, recursive algorithm suffices to test the equivalence of trees.<P>Since the <tt>BinaryTree</tt> class is ultimatelyderived from the <tt>Object</tt> classintroduced in Program&nbsp;<A HREF="page116.html#progobjecta"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,it must provide a <tt>_compareTo</tt> method to compare binary trees.Recall that the <tt>_compareTo</tt> method iscalled from the <tt>__cmp__</tt> method of the <tt>Object</tt> class.To compare two objects,say <tt>obj1</tt> and <tt>obj2</tt>,the <tt>_compareTo</tt> method is called like this:<PRE>obj1._compareTo(obj2)</PRE>It returns a negative number if  <IMG WIDTH=87 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline63459" SRC="img1138.gif"  >;a positive number if  <IMG WIDTH=87 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline63461" SRC="img1139.gif"  >; andzero if  <IMG WIDTH=87 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline63463" SRC="img1140.gif"  >.<P>So what we need is to define a<em>total order</em><A NAME=16605>&#160;</A>relation on binary trees.Fortunately, it is possible to define such a relation for binary treesprovided that the objects contained in the nodes of the treesare drawn from a totally ordered set.<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremtreesiv">&#160;</A>Consider two binary trees  <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63465" SRC="img1141.gif"  > and  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63467" SRC="img1142.gif"  > andthe relation <I>&lt;</I> given by<P> <IMG WIDTH=525 HEIGHT=88 ALIGN=BOTTOM ALT="equation16609" SRC="img1143.gif"  ><P>where  <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63465" SRC="img1141.gif"  > is either  <IMG WIDTH=6 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63013" SRC="img1069.gif"  > or  <IMG WIDTH=140 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63475" SRC="img1144.gif"  >and  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63467" SRC="img1142.gif"  > is  <IMG WIDTH=142 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63479" SRC="img1145.gif"  >.The relation <I>&lt;</I> is a total order.</BLOCKQUOTE><P>The proof of Theorem&nbsp;<A HREF="page293.html#theoremtreesiv"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is straightforward albeit tedious.Essentially we need to show the following:<UL><LI> For any two distinct trees  <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63465" SRC="img1141.gif"  > and  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63467" SRC="img1142.gif"  >, such that  <IMG WIDTH=59 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline63487" SRC="img1146.gif"  >,	either  <IMG WIDTH=60 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63489" SRC="img1147.gif"  > or  <IMG WIDTH=60 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63491" SRC="img1148.gif"  >.<LI> For any three distinct trees  <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63465" SRC="img1141.gif"  >,  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63467" SRC="img1142.gif"  >, and  <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63497" SRC="img1149.gif"  >,	if  <IMG WIDTH=60 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63489" SRC="img1147.gif"  > and  <IMG WIDTH=60 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63501" SRC="img1150.gif"  > then  <IMG WIDTH=60 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63503" SRC="img1151.gif"  >.</UL>The details of the proof are left asan exercise for the reader (Exercise&nbsp;<A HREF="page296.html#exercisetreestotal"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P>Program&nbsp;<A HREF="page293.html#progbinaryTreed"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives an implementation of the <tt>_compareTo</tt>method for the <tt>BinaryTree</tt> class.This implementation is based on the total order relation <I>&lt;</I> definedin Theorem&nbsp;<A HREF="page293.html#theoremtreesiv"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="16710">&#160;</A><A NAME="progbinaryTreed">&#160;</A> <IMG WIDTH=575 HEIGHT=390 ALIGN=BOTTOM ALT="program16635" SRC="img1152.gif"  ><BR><STRONG>Program:</STRONG> <tt>BinaryTree</tt> class <tt>CompareTo</tt> method.<BR><P><P>The <tt>_compareTo</tt> method compares the two binary trees<tt>self</tt> and <tt>bt</tt>.If they are both empty trees, <tt>_compareTo</tt> returns zero.If <tt>self</tt> is empty and <tt>bt</tt> is not,<tt>_compareTo</tt> returns -1; andif <tt>bt</tt> is empty and <tt>self</tt> is not,it returns 1.<P>Otherwise, both trees are non-empty.In this case, <tt>_compareTo</tt> first compares their respective roots.If the roots are equal, then the left subtrees are compared.Then, if the roots and the left subtrees are equal,the right subtrees are compared.<P>Clearly the worst-case running occurs when comparing identical trees.Suppose there are exactly <I>n</I> nodes in each tree.Then, the running time of the <tt>_compareTo</tt> method is <IMG WIDTH=106 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63513" SRC="img1153.gif"  >,where  <IMG WIDTH=42 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63515" SRC="img1154.gif"  > is the time needed to compare the objects containedin the nodes of the trees.<P><HR><A NAME="tex2html4576" HREF="page294.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4574" HREF="page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4568" HREF="page292.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html4578" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page293.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page293.html 源码文件，采用 HTML 编程语言编写，共 101 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?