英文版数据结构课程关键算法的综合演示系统设计与实现外文翻译资料

8.1 General Trees
Productivity experts say that breakthroughs come by thinking “nonlinearly.” In this chapter, we will discuss one of the most important nonlinear data structures in computing—trees. Tree structures are indeed a breakthrough in data organization for they allow us to implement a host of algorithms much faster than when using linear data structures, such as arrays or linked lists. Trees also provide a natural organization for data, and consequently have become ubiquitous structures in filesystems, graphical user interfaces, databases, websites, and many other computer systems.
It is not always clear what productivity experts mean by “nonlinear” thinking,but when we say that trees are “nonlinear,” we are referring to an organizational relationship that is richer than the simple “before” and “after” relationships between objects in sequences. The relations -hips in a tree are hierarchical, with some objects being “above” and some “below” others. Actually, the main terminology for tree data structures comes from family trees, with the terms “parent,” “child,”,“ancestor,” and “descendant” being the most common words used to describe relationships. We show an example of a family tree in Figure 8.1.

Figure 8.1: A family tree showing some descendants of Abraham, as recorded in Genesis, chapters 25–36.
8.1.1 Tree Definitions and Properties
A tree is an abstract data type that stores elements hierarchically. With the exception of the top element, each element in a tree has a parent element and zero or more children elements. A tree is usually visualized by placing elements inside ovals or rectangles, and by drawing the connections between parents and children with straight lines. (See Figure 8.2.) We typically call the top element the root of the tree, but it is drawn as the highest element, with the other elements being connected below (just the opposite of a botanical tree).

Figure 8.2: A tree with 17 nodes representing the organization of a fictitious corporation. The root stores Electronics Rrsquo;Us. The children of the root store Ramp;D,Sales, Purchasing, and Manufacturing. The internal nodes store Sales, International, Overseas, Electronics Rrsquo;Us, and Manufacturing.
Formal Tree Definition
Formally, we define a tree T as a set of nodes storing elements such that the nodes have a parent-child relationship that satisfies the following properties:
bull; If T is nonempty, it has a special node, called the root of T , that has no parent.
bull; Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w.

Note that according to our definition, a tree can be empty, meaning that it does not have any nodes. This convention also allows us to define a tree recursively such that a tree T is either empty or consists of a node r, called the root of T , and a (possibly empty) set of subtrees whose roots are the children of r.

Other Node Relationships
Two nodes that are children of the same parent are siblings. A node v is external if v has no children. A node v is internal if it has one or more children. External nodes are also known as leaves.
Example 8.1: In Section 5.1.4, we discussed the hierarchical relationship between files and directories in a computerrsquo;s file system, although at the time we did not emphasize the nomenc -lature of a file system as a tree. In Figure 8.3, we revisit an earlier example. We see that the internal nodes of the tree are associated with directories and the leaves are associated with regular files. In the Unix and Linux operating systems, the root of the tree is appropriately called the “root directory,” and is represented by the symbol “/.”

Figure 8.3: Tree representing a portion of a file system.
A node u is an ancestor of a node v if u = v or u is an ancestor of the parent of v. Conversely, we say that a node v is a descendant of a node u if u is an ancestor of v. For example, in Figure 8.3, cs252/ is an ancestor of papers/, and pr3 is a descendant of cs016/. The subtree of T rooted at a node v is the tree consisting of all the descendants of v in T (including v itself). In Figure 8.3, the subtree rooted at cs016/ consists of the nodes cs016/, grades, homeworks/, programs/, hw1, hw2,hw3, pr1, pr2, and pr3.
Edges and Paths in Trees
An edge of tree T is a pair of nodes (u,v) such that u is the parent of v, or vice versa. A path of T is a sequence of nodes such that any two consecutive nodes in the sequence form an edge. For example, the tree in Figure 8.3 contains the path (cs252/, projects/, demos/, market).

Ordered Trees
A tree is ordered if there is a meaningful linear order among the children of each node; that is, we purposefully identify the children of a node as being the first,se

剩余内容已隐藏，支付完成后下载完整资料

8.1 一般的树

效率专家说，“突破是通过lsquo;非线性rsquo;思考实现的”。在这一节，我们要讨论计算机中最重要的非线性数据结构——树。树形结构是数据组织的一项重大突破，因为它允许我们实现一系列比线性结构例如数组和线性表快得多的算法。树形结构也提供了一种数据的自然存储方法，它的出现使得无处不在的结构化文件系统，图形用户界面，数据库和许多其他计算机系统得以形成。

效率专家所说的“非线性”思维并不总是很清楚，但当我们说树是“非线性的”时，我们指的是一种组织关系，它比简单的“前”和“后”的序列中的对象之间的关系更丰富。树的结构关系是层次化的，一些对象属于上层，另一些属于下层。事实上，树形结构中的专业术语来自于“族谱”，用“父”、“子”、“祖先”和“后代”来描述关系。我们在图8.1中展示了一个家族树的例子

图 8.1: Abraham家族的族谱，正如Genesis第25到36章记载

8.1.1 树的定义和属性

树是一种抽象数据类型，它将元素分层存储。除顶部元素外，树中的每个元素都有父元素和零个或者多个子元素。一棵树通常是通过将元素放置于椭圆形或长方形中，并通过绘制父母元素与孩子元素之间的连线来实现可视化。（见图8.2）我们通常称顶端元素为树的根，但它被绘制在最高的地方，而其他的元素被连接在下面（刚好与植物学中的树相反）。

图8.2:这是有17个节点代表一个虚构公司组织的树。根节点存储了Electronics Rrsquo;Us,与根节点相连的节点存储了Ramp;D,Sales, Purchasing, 和Manufacturing。再下一层节点存储了Sales, International, Overseas, Electronics Rrsquo;Us, 和Manufacturing节点。

正规的树的定义

在形式上，我们定义了一个树T存储一组节点，使节点有一个父子关系，满足以下属性：

bull; 如果T是非空的，它有一个特殊的结点，称为T的根结点，根节点没有父母结点。

bull; T中的每个不同的结点v有着唯一的父结点w，父结点是w的节点都是w的子结点

请注意，根据我们的定义，树可以是空的，也就是说它没有任何节点。该约束还允许我们定义一个递归树，树是空的或只包含一个节点r，称为T的根，和一个（可能为空）的子树的根r的孩子

其它的节点关系

两个节点有同一个父节点成为兄弟节点。如果v没有孩子则称节点v是外部节点。如果它有一个或多个孩子则称节点v是内部节点，外部节点也称为叶子。

例 8.1: 第5.1.4节，我们讨论了计算机文件系统中的文件和目录间的层次关系，当时我们并没有强调将文件系统命名为一棵树。在图8.3中，我们重温了之前的例子。我们可以看到树的内部节点可以和目录联系起来，叶子节点可以与常规文件联系起来。在UNIX和Linux操作系统中，树的根被适当地称为“根目录”，并由符号“/”表示。

图8.3: 表示文件系统的树的一部分

如果u=v或者u是v的双亲节点的祖先，那么节点u就是节点v的祖先。反过来说，如果u是v的祖先，那么v是u的后继。例如，在图8.3中cs252/是papers/的祖先，pr3是cs016/的后继。以v作为节点的子树是由T中v的所有后继（包括v自身）组成的。在图8.3中以cs016/作为根节点的树由节点cs016/, grades, homeworks/, programs/, hw1, hw2,hw3, pr1, pr2, 和pr3组成。

树中的边和路径

树T的边是一对结点（u，v）组成的，其中u是v的父节点，反之亦然。T的路径是一个使得序列中任意两个连续的节点形成一个边的节点序列。例如，在图8.3中包含这些边(cs252/, projects/, demos/, market).

有序树

如果每个孩子节点之间有一个有意义的线性序列关系，那么就说树是有序的，也就是说，我们确定这些结点的顺序，比如第一个、第二个、第三个是有目的的。这样的顺序通常通过将它们从左到右分类实现可视化。

例8.2：结构化的文件的构成，例如一本书，由包括部分，章节，节为根，段落，图表，数字等等作为叶子的分层的树形结构组成。（如图8.4）树的根对应书本自身。事实上，我们可以考虑进一步将树扩展，以显示由句子组成的段落，由单词组成的句子和由字符组成的单词。

图8.4：和书相关的有序树

让我们回顾一下迄今为止我们所描述的其他树的例子，并考虑孩子节点的顺序是否重要。家族树描述的代际关系，如图8.1，通常按照兄弟姐妹的出生顺序被建模为一个有序的树。

相比之下，公司的组织结构图，如图8.2所示，通常被认为是无序树。同样，当用树来描述一个在继承层次结构，如图2.7，父类和子类之间的顺序没有特别的意义。最后，我们考虑使用树在计算机的文件系统建模，如图8.3。虽然操作系统经常以特定的顺序显示目录的条目（例如，按字母顺序排列或者时间顺序），但这样的顺序通常不是文件系统固有的表示形式。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[25663]，资料为PDF文档或Word文档，PDF文档可免费转换为Word