page251.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 82 行
HTML
82 行
<HTML><HEAD><TITLE>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="tex2html4085" HREF="page252.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4083" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4077" HREF="page250.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4087" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION009000000000000000000">Trees</A></H1><P><A NAME="chaptrees"> </A><P>In this chapter we consider one of the most importantnon-linear information structures--<em>trees</em>.A tree is often used to represent a <em>hierarchy</em><A NAME=14101> </A>.This is because the relationships between the itemsin the hierarchy suggest the branches of a botanical tree.<P>For example, a tree-like <em>organization chart</em> is often usedto represent the lines of responsibility in a businessas shown in Figure <A HREF="page251.html#figtree0"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The president of the company is shown at the top of the treeand the vice-presidents are indicated below him.Under the vice-presidents we find the managersand below the managers the rest of the clerks.Each clerk reports to a manager,each manager reports to a vice-president,and each vice-president reports to the president.<P><P><A NAME="14203"> </A><A NAME="figtree0"> </A> <IMG WIDTH=575 HEIGHT=190 ALIGN=BOTTOM ALT="figure14104" SRC="img1036.gif" ><BR><STRONG>Figure:</STRONG> Representing a hierarchy using a tree.<BR><P><P>It just takes a little imagination to see the tree in Figure <A HREF="page251.html#figtree0"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Of course, the tree is upside-down.However, this is the usual way the data structure is drawn.The president is called the <em>root</em> of the treeand the clerks are the <em>leaves</em>.<P>A tree is extremely useful for certain kinds of computations.For example, suppose we wish to determine the total salariespaid to employees by division or by department.The total of the salaries in division Acan be found by computing the sum of the salaries paid in departments A1and A2 plus the salary of the vice-president of division A.Similarly, the total of the salaries paid in department A1is the sum of the salaries of the manager of department A1and of the two clerks below him.<P>Clearly, in order to compute all the totals,it is necessary to consider the salary of every employee.Therefore, an implementation of this computationmust <em>visit</em> all the employees in the tree.An algorithm that systematically <em>visits</em>all the items in a tree is called a <em>tree traversal</em>.<P>In this chapter we consider several different kinds of treesas well as several different tree traversal algorithms.In addition,we show how trees can be used to represent arithmetic expressionsand how we can evaluate an arithmetic expression by doing a tree traversal.<P><BR> <HR><UL> <LI> <A NAME="tex2html4088" HREF="page252.html#SECTION009100000000000000000">Basics</A><LI> <A NAME="tex2html4089" HREF="page256.html#SECTION009200000000000000000"><I>N</I>-ary Trees</A><LI> <A NAME="tex2html4090" HREF="page257.html#SECTION009300000000000000000">Binary Trees</A><LI> <A NAME="tex2html4091" HREF="page258.html#SECTION009400000000000000000">Tree Traversals</A><LI> <A NAME="tex2html4092" HREF="page263.html#SECTION009500000000000000000">Expression Trees</A><LI> <A NAME="tex2html4093" HREF="page267.html#SECTION009600000000000000000">Implementing Trees</A><LI> <A NAME="tex2html4094" HREF="page296.html#SECTION009700000000000000000">Exercises</A><LI> <A NAME="tex2html4095" HREF="page297.html#SECTION009800000000000000000">Projects</A></UL><HR><A NAME="tex2html4085" HREF="page252.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4083" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4077" HREF="page250.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4087" 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 + -
显示快捷键?